JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Decidable Equals Recognizable Plus Co-Recognizable

The first two guides split the world into machines that always halt and machines that may loop forever. This one names the exact missing ingredient: a language is decidable precisely when both it AND its complement are recognizable. We will prove the both-directions theorem, run two recognizers in parallel to see it work, and learn why the recognizable languages are not closed under complement.

Picking up the thread: the two fates and the one missing piece

By now you carry two facts from this rung. First, a decidable language has a machine — a decider — that ALWAYS halts: on every input it eventually stops and says yes or no, and never gets stuck spinning. Second, a merely recognizable language has a machine that says yes on every string in the language, but on a string OUTSIDE the language it is allowed to do something weaker than say no: it may loop forever. That loophole — the silence of a machine that never halts — is the whole gap between deciding and recognizing, and guide 2 dwelt on exactly why a recognizer is permitted to stay silent rather than reject.

So a natural question hangs in the air. If a recognizer's only weakness is that it can be silent on non-members, what would it take to plug that hole and upgrade a mere recognizer into a full decider? You might guess 'just add a timer', but that fails: there is no general way to know how long is long enough, because a machine that has not halted yet might halt on the very next step, or never. The real answer is surprisingly clean, and it is the subject of this guide: a language is decidable exactly when it AND its complement are both recognizable. We call this the decidable-iff-recognizable-and-co-recognizable theorem.

What 'co-recognizable' means

First, the complement. The complement of a language L over an alphabet Σ (sigma, the fixed set of allowed symbols) is the set of ALL strings over Σ that are NOT in L, written as 'not-L' or with an overbar. If L is 'all C programs that compile', its complement is 'all strings that are not a compiling C program' — which includes every gibberish string too, not just broken programs. A language is called co-recognizable when its COMPLEMENT is recognizable. So 'co-recognizable' is not a new machine; it is simply the statement 'there is a recognizer for the strings NOT in L'.

Read the two halves side by side and the picture sharpens. A recognizer for L is a machine that is GOOD AT SAYING YES: it halts-and-accepts on exactly the members of L, and is allowed to loop on non-members. A recognizer for not-L is a machine that is GOOD AT SAYING NO about L: it halts-and-accepts on exactly the NON-members of L (and loops on the members). One machine reliably confirms 'in L', the other reliably confirms 'out of L'. Each alone is half-blind; the question is what you get when you own both at once.

The theorem, and the parallel-run trick that proves it

The claim has two directions, and a clean theorem proves both. EASY DIRECTION: if L is decidable, then both L and not-L are recognizable. This is almost free — a decider for L always halts with yes/no, so it is in particular a recognizer for L; and to recognize not-L, run the same decider and FLIP its answer. A halting machine flipped is still a halting machine, so not-L is even decidable. Decidable languages, then, are trivially both recognizable and co-recognizable. The interesting content is the other direction.

HARD DIRECTION: if L is recognizable AND co-recognizable, then L is decidable. Here is the worry that makes it non-obvious. You hold machine M1 that recognizes L and machine M2 that recognizes not-L. Given an input w, why not run M1 first, and if it rejects, run M2? Because M1 might LOOP on w forever — you would wait at M1's door eternally and never even reach M2. Running them one after another inherits the very looping disease we are trying to cure. The fix is to run them BOTH AT THE SAME TIME, taking turns, so neither can trap you.

  1. Build a new decider D for L. Its input is a string w.
  2. D simulates BOTH machines on w in lockstep: do one step of M1, then one step of M2, then the next step of M1, and so on, alternating forever — this interleaving is the same parallel idea you will meet again as dovetailing in the next guide.
  3. Exactly one of two things must eventually happen. If M1 halts-and-accepts, then w is in L, so D halts and says YES.
  4. If instead M2 halts-and-accepts, then w is in not-L, so w is NOT in L, and D halts and says NO.
  5. D ALWAYS halts. Why? Every w is in exactly one of L or not-L, so one of M1, M2 is guaranteed to accept w. Running both in parallel means we never get stuck waiting on the one that loops — the one destined to accept gets its turn after finitely many steps.

That is the entire proof, and the engine of it is the parallel simulation trick: alternate steps so a looping machine can never starve its halting partner. The deep reason D is total — halts on all inputs — is the logical fact that 'w in L OR w in not-L' is ALWAYS true. Membership in L is a genuine yes-or-no question; we just lacked a way to FORCE one of the two recognizers to commit in finite time, and running them together does exactly that. Notice no timer and no bound on running time were ever needed.

Closure: where the symmetry holds and where it breaks

The theorem reorganizes everything into a tidy three-region map. The DECIDABLE languages sit in the middle, the calm core where machines always halt. Around them, the RECOGNIZABLE languages bulge out on the 'yes side', and the CO-RECOGNIZABLE languages bulge out on the 'no side'. The theorem says the OVERLAP of those two bulges is exactly the decidable middle — neither more nor less. This is the decidable / recognizable / co-recognizable picture, and it is worth fixing firmly in your mind, because the next rung populates each region with named examples.

Now the closure properties, which is where a beautiful asymmetry shows up. The DECIDABLE languages are closed under complement: just flip a decider's answer, as we saw, and you still always halt. They are also closed under union and intersection — run two deciders, both finish, and combine their verdicts with OR or AND. So decidable languages form a comfortable, symmetric world: every Boolean combination of decidable languages is decidable. This is the closure behaviour you would intuitively hope for.

The RECOGNIZABLE languages are different. They ARE closed under union and intersection — run two recognizers in parallel (union: accept if EITHER accepts; intersection: accept only if BOTH accept, running them one after another is fine here since both must halt to accept). But the recognizable languages are NOT closed under complement. If they were, then every recognizable L would have a recognizable complement too, making EVERY recognizable language co-recognizable — and by the theorem we just proved, that would make every recognizable language decidable. We will see in a later guide that some recognizable languages are provably undecidable (the acceptance problem A_TM is the famous one). So complement-closure cannot hold; assuming it leads straight to a contradiction.

The enumerator view, and a one-line sanity check on DFAs

There is a second, equally vivid way to picture 'recognizable', and the next guide develops it fully. Imagine a machine that, instead of being asked about one string, just sits there and PRINTS OUT, one by one, all the strings in L — a kind of tireless list-maker called an enumerator. A language is recognizable exactly when some enumerator can print every one of its members (in any order, possibly with repeats, taking as long as it likes). 'Co-recognizable' then means there is an enumerator that lists everything NOT in L. Owning both lists is, intuitively, owning the complete answer key — which is again why both together give you decidability.

It is easy to come away thinking 'recognizable but not decidable' is the normal case, so let us anchor the other extreme with something concrete and reassuring. Take any ordinary question about a fixed deterministic finite automaton — say, the emptiness problem for a DFA: does this DFA accept NO strings at all? You can settle it with a plain finite procedure that always halts: from the DFA's start state, mark every state reachable by following transitions (a graph search); the DFA's language is empty if and only if NO accept state ever gets marked. There is no input string to loop on — the automaton itself is the whole finite input — so this problem is flatly decidable.

EMPTINESS of a DFA  (does it accept nothing?)
  input: a DFA M = (Q, Sigma, delta, q0, F)
  1. mark q0
  2. repeat until no change:
        if state q is marked and delta(q, x) = p,
        then mark p     (for every symbol x in Sigma)
  3. if NO state in F got marked  -> ACCEPT  (L(M) is empty)
     else                        -> REJECT  (L(M) is nonempty)
  This loop must stop: there are only finitely many states
  to mark, so it always halts. A genuine DECIDER, no looping.
Emptiness for a DFA is decidable by a finite reachability search: mark states reachable from the start, accept iff no accept state is ever reached. It always halts because there are finitely many states.

This is the calm heart of the map, and the next two guides explore its outskirts. Carry the central equation with you: decidable = recognizable AND co-recognizable. It tells you that the gap between merely recognizing and truly deciding is precisely a missing complement-recognizer — and that running two ordinary recognizers in parallel, never letting either loop block the other, is enough to close that gap. The honest caution to keep: this does NOT make every recognizable language decidable. Many languages are recognizable while their complements are not, and those stubborn one-sided languages are exactly where the next rung finds the limits of computation.