Recognizers, Dovetailing, and Complement Asymmetry

Three machine behaviours are worth keeping apart. A decider halts on every input and always answers. A recognizer halts with acceptance on every string in its language and either halts with rejection or runs forever on every string outside it. A co-recognizer for a language halts with acceptance on every string outside that language, and either halts with rejection or runs forever on every string inside it — equivalently, it is a recognizer for the complement. Decidable languages are exactly those with both a recognizer and a co-recognizer, and that characterisation is the cleanest way to see what closure under complement really requires.

The three-way distinction, stated operationally

Fix a language L over a finite alphabet and a machine M. The definitions differ only in which halting behaviours are permitted on which strings, and the differences are not cosmetic. Write the behaviour on a string as one of three outcomes: halt-accept, halt-reject, or loop.

A decider for L produces halt-accept on every string in L and halt-reject on every string not in L, with no third outcome anywhere. A recognizer for L produces halt-accept on every string in L and may produce halt-reject or loop on strings outside L. Note what a recognizer is forbidden to do: it may never halt-reject a string that belongs to L, and it may never loop on one. Both requirements are about the yes-side only, which is why the class is sometimes called recursively enumerable — the strings can be enumerated, though not necessarily in order and not necessarily all at once.

The asymmetry is not a defect of any particular machine. It follows from the shape of the acceptance condition. Acceptance is an existential claim: there exists a finite number of steps after which the machine enters an accepting state. That claim can be verified by search. Non-acceptance is a universal claim: for all step counts, the machine is not in an accepting state. Verifying a universal claim by search requires exhausting an infinite domain, and no finite prefix of the run settles it.

Why complement is not free

Take a recognizer M for L and swap its accept and reject states. Call the result M′. On a string in L, M halts and accepts, so M′ halts and rejects. On a string outside L, M may halt and reject — in which case M′ halts and accepts — or M may loop, in which case M′ loops identically. So M′ accepts some strings outside L, but it also loops on others. It is not a recognizer for the complement, because a recognizer must halt-accept every string in its language, and M′ fails on the ones where M loops.

There is no repair. The state swap cannot conjure halting out of a computation that never halts, and every transformation that preserves the step-by-step behaviour of M inherits M’s divergence. To recognize the complement, a machine must determine non-membership, which requires deciding something about the whole run rather than watching a prefix of it. This is why closure under complement fails for recognizers while closure under union and intersection succeeds.

Union is easy: run two recognizers in parallel on separate tapes and accept when either accepts. Both are guaranteed to halt on their respective yes-instances, so at least one halts whenever the input belongs to either language. Intersection is equally easy: accept when both accept, and note that on a string in the intersection both machines halt, so the combined machine halts. Both constructions inherit the possibility of looping on strings outside the combined language, which is exactly what the class permits.

Dovetailing as a scheduling problem

The naive way to run two machines in parallel is round-robin: one step of A, one step of B, repeat. For two machines whose halting is all that matters, that is enough, since each gets a step in every round and any machine that would halt does so. The scheme breaks as soon as the number of machines is unbounded and the machine to run is chosen by a search. A fixed share per machine is zero when the machines are pulled from an infinite list, and running each of the first k machines in turn, for growing k, gives the early machines finite attention while the machine that would halt may sit arbitrarily far down the list.

Dovetail instead: on round k, run one step of each of the first k machines. Machine i receives one step in every round k ≥ i, so it receives infinitely many steps overall. Formally, machine i’s step j is executed at round i + j, so if machine i halts after t steps the combined simulation observes it at round i + t, which is finite. Every machine that would halt on its own does halt under dovetailing. The price is that every round of the simulation repeats the work of earlier rounds, so the number of steps executed to complete k rounds is quadratic in k.

The standard application is recognition of the union of a computable sequence of languages. If L = ⋃ᵢ Lᵢ and the map i ↦ (a description of a recognizer for Lᵢ) is computable, then L is recognizable: on input w, dovetail over i, running recognizer i on w for one more step each round, and accept if any accepts. No bound on which i will succeed is needed, and none is available.

def dovetail(machine_factories, word, max_rounds=10_000):
    """machine_factories: an iterator of callables, each word -> generator.
    Each generator yields None while the machine keeps running, and yields
    'accept' when it accepts; exhausting the generator means it halted
    without accepting, so that machine can be dropped from the rotation.
    Returns True on acceptance, None if nothing accepted within max_rounds,
    which refutes nothing."""
    live, pending = [], iter(machine_factories)
    for k in range(max_rounds):
        while len(live) <= k:          # round k must touch at least k+1 machines
            factory = next(pending, None)
            if factory is None:
                break                  # the program has produced no more machines
            live.append(factory(word))
        survivors = []
        for g in live[:k + 1]:
            try:
                r = next(g)
            except StopIteration:
                continue               # finished without accepting: drop it
            if r == 'accept':
                return True
            survivors.append(g)
        live = survivors + live[k + 1:]
    return None

Two details carry the construction. A machine that halts without accepting is removed from the rotation rather than retried, because it will never do anything else. And new machines are pulled lazily, one per round, because the union construction derives machine i from a program that is only partially available at any finite time.

The None return is the honest part. A bounded dovetail that finds nothing has established nothing, because the accepting machine may be further down the list or need more steps. Any implementation that returns False after a fixed budget is reporting a decision the mathematics does not support.

Enumerating a recognizable language

A recognizer can be converted into an enumerator: a machine that writes strings on an output tape, one after another, and whose output is exactly L in some order, possibly with repeats. The construction dovetails over strings in shortlex order rather than over a fixed string. Run M on the first string for one step, then on the first string for a second step and the second string for its first, then three steps for the first, two for the second and one for the third, and so on. Each string therefore receives unboundedly many steps, and whenever M accepts the string that attempt completes and the string is emitted. Every string in L appears, because the diagonal of the schedule eventually gives it enough steps; no string outside L is ever emitted, because M never accepts one. The order is not the input order and the same string may be emitted more than once across different schedules, which is why the definition of an enumerator allows both.

The converse holds too: if L is enumerated by some machine, it is recognizable, by running the enumerator and comparing each emitted string to the input. This equivalence is the reason the term recursively enumerable is used interchangeably with recognizable, and it gives a second, independent handle on the class.

The complement criterion

L is decidable if and only if both L and its complement are recognizable. One direction is immediate: a decider for L, with accept and reject swapped, decides the complement, and every decider is a recognizer.

For the other direction, suppose M₁ recognizes L and M₂ recognizes its complement. Run both on the input in parallel, one step at a time. The input lies in exactly one of the two languages, so exactly one of the machines halts and accepts, and it does so after finitely many steps. Accept if M₁ wins, reject if M₂ wins. The combined machine halts on every input, hence decides L.

The proof is short and the conclusion is sharp. Since acceptance is recognizable but not decidable, the complement of acceptance cannot be recognizable. If it were, the criterion would produce a decider, contradicting the result in Encoding Turing Machines and the Undecidability of Acceptance. So the halting set is recognizable and its complement is not: the complement is co-recognizable by definition, yet it has no recognizer of its own. That is the asymmetry made concrete, rather than an abstract possibility. Asking instead which sets are recognizable relative to the complement produces a whole classification: the alternating levels described in The Arithmetical Hierarchy and the Turing Jump are what this single failure of complement closure grows into.

What the asymmetry means for search

The practical reading is about the direction in which a search can terminate. A recognizer is a semi-decision procedure: it can say yes, and it can run forever, and running forever is indistinguishable from “not yet”. Programs that search for a witness — a proof, a satisfying assignment, a counterexample to a conjecture — have this shape. Finding the witness terminates the search with a yes. Not finding it produces no information at any finite time, and no amount of additional waiting converts the absence of a witness into a proof of absence.

The complement criterion says that a problem is decidable exactly when both the search for a witness and the search for a counter-witness can be run and one of them is guaranteed to terminate. Where only one direction has a terminating search, the problem is recognizable on one side and not the other. The halting problem sits there, and every problem that reduces to it inherits the same one-sidedness.