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

Decidable vs Recognizable

The Turing-machine rung handed you a machine with three fates: accept, reject, or loop forever. This guide turns that third fate into the single most important dividing line in the whole subject — between languages a machine can always settle, and languages it can only confirm when the answer is yes.

Two words that look alike and mean very different things

You arrived here knowing that a Turing machine — the endless notebook you can read, erase, and rewrite — has exactly three possible fates on any input: it may halt and accept, halt and reject, or run on forever and never stop. The first two are tidy; the third is the troublemaker, and this whole rung is built around it. The question is simple to ask and deep to answer: when we say a machine 'solves' the membership problem for a language, do we mean it always gives us an answer, or merely that it answers when the true answer happens to be yes? Those two readings split every language in the universe into two overlapping piles, and the words for them are decidable and recognizable.

A language L is Turing-recognizable if some Turing machine M accepts exactly the strings in L. The catch is in what M does on strings NOT in L: it is allowed to reject them, OR to loop forever — either is fine. So if you feed M a string and it accepts, you have learned 'yes, this is in L'. But if M is still running after a million steps, you cannot conclude anything: maybe it is about to reject, maybe it will reject on step a billion, maybe it will never stop at all. A recognizer is an optimist who shouts 'yes!' the moment a yes is true, but who may simply never speak when the answer is no. The synonym you will see in older books is recursively enumerable, usually abbreviated r.e.

A language L is Turing-decidable (older books say recursive) if some Turing machine — now called a decider — accepts every string in L AND rejects every string not in L, always halting on EVERY input. The forbidden third fate is gone: a decider never loops. It is not an optimist but a referee who, on any input whatsoever, eventually blows the whistle one way or the other. Deciding is what we usually mean, in everyday speech, by 'having an algorithm' for a yes/no question — a procedure guaranteed to terminate with the correct verdict. Recognizing is the weaker, slipperier cousin.

The loophole is exactly the looping

Here is the heart of the difference, and it is worth saying slowly: every decidable language is recognizable, but not the other way around. The easy direction first. If you have a decider, you already have a recognizer — a referee who always answers yes-or-no is, in particular, a machine that accepts the yes-instances. Throwing away the guarantee 'and it also halts on the no-instances' only weakens the promise; it never breaks it. So decidable is a SUBSET of recognizable. The whole drama lives in whether that subset is proper — whether there is anything recognizable but not decidable. Spoiler from the next rung: yes, and the famous witness is the halting problem.

Why can a recognizer fail to be a decider? Picture two machines hunting for a string in a language. The decider is searching a finite room: it can sweep every corner and, finding nothing, declare 'not here'. The recognizer is searching an endless corridor: if the thing is there it will eventually trip over it and shout, but if it is NOT there, the recognizer just keeps walking, and at no finite moment can it honestly say 'I have now checked everywhere'. That inability to ever conclude 'no' is not laziness or slowness — it is a logical wall. The looping is not a bug we could patch with a faster computer; for some languages, the looping is unavoidable, and proving that is the bombshell of the rung after this one.

Flip the answers: co-recognizable languages

If a recognizer is good at confirming yes-answers, what about a machine good at confirming no-answers? That is exactly the idea of a co-recognizable language. A language L is co-recognizable when its COMPLEMENT — the set of all strings over the alphabet Sigma (written Σ, the set of allowed symbols) that are NOT in L — is recognizable. Equivalently, there is a machine that halts and accepts precisely on the strings OUTSIDE L, and may loop on the strings inside L. It is the mirror-image optimist: it shouts 'no!' the instant a no is true, but stays silent (or loops) when the answer is yes.

Hold the two pictures side by side and a beautiful symmetry appears. A recognizer is a yes-detector that may never fire on a no. A co-recognizer is a no-detector that may never fire on a yes. Each alone is half-blind. The obvious next thought — and it is the right one — is: what if you had BOTH, for the same language, at the same time? If you could run a yes-detector and a no-detector together, then on any input one of them is guaranteed to eventually fire (the true answer is, after all, either yes or no), and the moment it does, you have your verdict and you halt. That partnership is the bridge from recognizing back to deciding, and it is the subject of the central theorem you will meet next in this rung.

The theorem and the closure rules it explains

Here is the central result of the rung, stated cleanly so it can guide you even before the full proof in a later guide: a language L is decidable if and only if L is BOTH recognizable AND co-recognizable. This is the famous decidable = recognizable + co-recognizable characterization, and it captures the partnership exactly. One direction is the easy one we already saw: a decider gives a recognizer (and, by also halting on no-instances, a co-recognizer too). The other direction is the clever one, and the trick is to run the two machines TOGETHER rather than one then the other.

  1. Suppose L is recognizable by a machine M (fires on yes) and L is co-recognizable, meaning its complement is recognizable by a machine N (fires on no). We want to build a decider D for L.
  2. On input w, D simulates M and N IN PARALLEL — run one step of M, then one step of N, then the next step of each, alternating forever. (Naively running M to completion first would risk looping before N ever gets a turn.)
  3. If M ever accepts, then w is in L, so D halts and ACCEPTS. If N ever accepts, then w is in the complement, so D halts and REJECTS.
  4. Since every w is either in L or in its complement, exactly one of M, N is guaranteed to accept eventually. So D always halts with the correct verdict — D is a decider, and L is decidable.

This theorem also explains a closure rule that surprises beginners. The recognizable languages are closed under union and intersection — run two recognizers in parallel and accept when appropriate — but they are NOT closed under complement. If they were, every recognizable language would automatically be co-recognizable too, hence (by the theorem) decidable, and we know that is false. So 'recognizable, complement it, still recognizable?' must fail for some language — and indeed the complement of the halting problem's language is the standard example of a language that is co-recognizable but NOT recognizable. By contrast, the decidable languages ARE closed under complement: flip a decider's accept and reject states and you get a decider for the complement, no loop to worry about, because a decider never loops.

The enumerator view, and problems we can always decide

There is a second, equally vivid way to picture recognizability that explains the old name 'recursively enumerable'. Instead of a machine that takes a string and answers, imagine a machine with no input that just PRINTS, one after another, the strings of a language — an enumerator, a tireless lister. A language is recognizable exactly when some enumerator can eventually print every one of its members (in any order, possibly with repeats). And here is the subtle part: to list a language whose members come from infinitely many candidate machines or computations, you cannot run each computation to completion before starting the next — one of them might loop and freeze the whole list. The fix is dovetailing: interleave the computations like shuffling a deck, doing step 1 of job 1; then step 1 of jobs 1 and 2; then step 1 of jobs 1, 2, 3; and so on, so every computation gets unboundedly many steps without any single one blocking the rest.

DOVETAILING the jobs J1, J2, J3, ... (each Ji may loop):

  round 1:   J1 step1
  round 2:   J1 step2   J2 step1
  round 3:   J1 step3   J2 step2   J3 step1
  round 4:   J1 step4   J2 step3   J3 step2   J4 step1
   ...

  - whenever some Ji ACCEPTS / produces output, record it.
  - no single looping Ji ever starves the others of attention.
  - every Ji eventually receives any finite number of steps you like.
Dovetailing interleaves infinitely many possibly-looping computations so each makes progress; it is the engine behind 'enumerable = recognizable' and behind running parallel machines without one loop freezing the rest.

After all this talk of machines that might loop forever, it is a relief to end on solid ground: a great many natural questions are flatly, reliably DECIDABLE. About finite automata especially, almost everything is decidable, because a DFA is a finite, fully-mappable object. 'Does this DFA accept string w?' (the acceptance question) is decided by simply running the DFA on w — it has no loops, so it always halts. 'Is the language of this DFA empty?' is decided by checking whether any accept state is reachable from the start state, a finite graph search. 'Do these two DFAs accept the same language?' (equivalence) is decided by building a DFA for the symmetric difference and testing IT for emptiness — if nothing is in the difference, the two are equal. Even for context-free grammars, membership ('does this grammar generate w?') and emptiness ('does it generate anything at all?') are decidable, though equivalence of two grammars is not.

Notice the pattern, and carry it up the ladder: the LOWER a model sits in the Chomsky hierarchy, the more we can decide about it. Finite automata are so constrained that emptiness, equivalence, and membership are all decidable. Grammars give up equivalence but keep membership and emptiness. And the all-powerful Turing machine — precisely because it can do anything a computer can — gives up the most: even asking 'does THIS machine ever halt on THIS input?' turns out to have no decider at all. Power and predictability trade against each other. That trade is the cliff-edge you will walk up to in the very next rung, and the decidable/recognizable distinction you now hold is the map you will read it by.