The third outcome changes everything
In the previous guide you met the three things a Turing machine can do on an input: enter its accept state, enter its reject state, or run forever without ever halting. That third outcome is brand new. A DFA always reads the input and stops; a PDA may have a few empty-stack dead ends but still cannot run on a finite input forever; the moment we gave the head a tape it can rewrite and a head that need never fall off the end, we also gave the machine the power to spin in place forever. Everything in this guide flows from that one fact: halting is now something a machine might fail to do.
So we have to be careful about what 'the machine accepts a string' really means versus 'the machine rejects it'. Accepting is a positive, observable event: the machine eventually halts in its accept state, and you see it happen. Rejecting splits into two very different situations. The machine might halt in its reject state — a clean, observable 'no'. Or it might simply never halt — and from the outside, a machine that has run for a billion steps and a machine that will loop forever look exactly the same. You cannot tell, by watching, whether the next step brings an answer or whether you are waiting for one that never comes.
Recognizing: yes is reliable, no may never arrive
A Turing machine M recognizes a language L when, for every string, M accepts it if and only if the string is in L. Read that carefully. On a string that IS in L, M is required to halt and accept. On a string that is NOT in L, M is allowed to do either of the wrong-for-rejection-but-still-correct things: halt and reject, or loop forever. A language is Turing-recognizable (the older name is recursively-enumerable) exactly when some machine recognizes it. The recognizer is a faithful 'yes'-detector and an unreliable 'no'-detector.
The everyday picture: a recognizer is a search that you set running and that promises to ring a bell the moment it finds what it is looking for — but makes no promise about telling you when it will never find it. Imagine a program that, given a number, searches for a proof of a conjecture and accepts if it finds one. If a proof exists, it eventually finds it and rings the bell. If no proof exists, it just keeps searching, forever, silent. You learn 'yes' for sure; you never get a definite 'no'. That asymmetry — guaranteed yes, possibly-silent no — is the whole personality of recognizing.
One subtle point worth nailing down: 'recognizable' does not mean 'easy' or 'small', any more than regular meant 'finite' back on the DFA rung. A recognizable language can be enormous and intricate; the only guarantee is that membership eventually shows up for members. And the language of a Turing machine M — written L(M) — is by definition the set of strings M accepts, gathering both the strings it halts-and-accepts and ignoring entirely the strings on which it loops. The loopers are not in L(M), but the machine never told you so.
Deciding: a machine that always halts
Now demand more. A Turing machine is a decider if it halts on every input — it never loops, on any string at all. A language is decidable (older name: recursive) when some decider recognizes it: the machine accepts every string in L, rejects every string not in L, and crucially always reaches one of those two verdicts in finite time. Deciding upgrades the unreliable 'no' of a recognizer into a reliable one. Both 'yes' and 'no' now come back, guaranteed, on every input.
halts & accepts halts & rejects loops forever x in L (a member) REQUIRED no no x not in L (non-member) no ok for BOTH ok ONLY for recognizer DECIDER = recognizer that NEVER loops -> every cell is a halt -------------------------------------------------------------------- decidable ==> recognizable (a decider is also a recognizer) recognizable =/=> decidable (recognizing is strictly weaker)
Every decidable language is recognizable, because a machine that always halts is in particular a machine that accepts exactly the right strings — a decider is just a well-behaved recognizer. The deep and surprising fact, which the halting problem will prove a couple of rungs up, is that the reverse fails: there are languages that are recognizable but not decidable. For those, you can build a machine that rings the bell on every member, yet no machine can be built that always halts with the correct yes-or-no. The gap between recognizing and deciding is not a temporary engineering limitation; it is a permanent feature of the mathematical landscape.
From yes/no to computing functions
Deciders answer yes/no questions, but a Turing machine can do more than vote — because its tape is read AND write, the contents left on the tape when it halts can be an answer, not just a verdict. A machine used this way is a transducer: it computes a function. Start with the input written on the tape, run, and when the machine halts the string remaining on the tape is the output f(input). If the machine halts on every input, it computes a total function; the connection to deciding is exact — a decider for L is just a transducer that computes the function returning 'accept' or 'reject', the characteristic function of L.
Here is the smallest honest example: a machine that increments a binary number. Input is a binary string with the least significant bit at the right end. The machine shuttles its head to the rightmost bit and walks left, turning 1s into 0s as it goes (those are the carries) until it meets a 0 or a blank, which it turns into a 1 and halts. Trace 0 1 1 (which is 3): rightmost 1 -> 0 (carry), next 1 -> 0 (carry), then the 0 -> 1, halt, leaving 1 0 0 (which is 4). It always halts because the head only moves left a bounded number of steps, so increment is a total computable function. This is the same shuttling-and-rewriting muscle you will flex on the next guide to build a^n b^n c^n and a string copier.
Two workhorse techniques make these designs manageable, and both reappear constantly. Marking means overwriting a symbol with a decorated version of itself — turning an 'a' into a crossed-out 'a' bar in the tape alphabet — so the head can remember 'I already handled this one' without any extra state. Tracks means treating one tape as several parallel lanes by enlarging the tape alphabet so each cell secretly holds a tuple, letting the machine keep a counter or a copy alongside the input. With marking, tracks, and patient left-right shuttling, surprisingly little machinery decides surprisingly much.
Putting it together: the boundaries you now command
Step back and see what the deciding/recognizing distinction has bought you. The languages split into three nested zones. Innermost: the decidable languages, where some machine always halts with the right answer — this is the honest meaning of 'a problem a computer can solve'. Around them: the recognizable languages, where a machine can confirm members but might loop on non-members. Outside even that: languages no Turing machine can recognize at all. The famous undecidable problems live in the ring between decidable and recognizable, and the truly hopeless ones live beyond recognizable.
- To prove a language is decidable, exhibit a decider: a machine, plus a clear argument that it halts on every input (a strictly decreasing quantity, a bounded search, a finite table to fill).
- To prove a language is recognizable, exhibit a recognizer: a machine that halts-and-accepts on every member; you are allowed to let it loop on non-members, so the halting argument is weaker.
- Remember the inclusions: every decidable language is recognizable, but not conversely. 'Recognizable but not decidable' is a real, populated category — its first inhabitant is the language of the halting problem, coming up soon.
- Never conflate 'loops forever' with 'slow' or 'hard'. A decidable language can take astronomically long yet still be decidable; an undecidable language is not slow, it is provably beyond any always-halting machine.
Why does this single distinction carry so much weight? Because it is the dividing line between what algorithms can and cannot do, full stop. Under the Church-Turing thesis, 'decidable by a Turing machine' is taken to mean 'solvable by any algorithm whatsoever' — so when we eventually prove some language is not decidable, we are not saying our particular machine is too weak; we are saying no algorithm, in any language, on any hardware we know how to build, will ever solve it with a guarantee to finish. Holding the deciding/recognizing line clearly in mind is what makes those later impossibility results land as the genuine surprises they are.