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

Accept, Reject, or Loop Forever

Guide 2 pinned down the transition that writes a symbol and moves the head. Now we run the machine and meet the strangest new fact about Turing machines: a computation has three possible fates, not two — accept, reject, or never stop at all. That third fate quietly splits one notion of 'the machine knows this language' into two, and that split is the engine of everything to come.

Running the machine: a configuration becomes the next configuration

From guide 2 you already have all the parts: an infinite tape, a read/write head sitting on one cell, a finite control in some state, a tape alphabet that includes the blank symbol, and a transition function delta that, given the current state and the symbol under the head, says 'write this symbol, move left or right, and switch to this state'. Running the machine is nothing more than applying delta over and over. The only honest way to think about what 'running' produces is to track the whole situation at each tick — and that snapshot has a name: the configuration.

A configuration captures everything you would need to resume the machine if you froze it: the current state, the entire tape contents, and exactly where the head is. People write it compactly as the tape string with the state symbol wedged in just before the cell under the head, like 'a a q3 b b'. This reads: the tape holds a a b b, the control is in state q3, and the head is poised over the first b. Because the tape is mostly blanks off to either side, we only write the part that matters and let the rest stay blank. One step of the machine turns one configuration into the next — that step relation is what the transition function really means when you watch it act.

Three fates, not two

Here is the genuinely new thing, the one that has no counterpart in any machine you met earlier on this ladder. A DFA reading a string always finishes — the input runs out and you check whether the final state is accepting. An NFA, a regular expression, even a PDA reading a finite input all terminate by construction. A Turing machine need not. Because it can move left as well as right and rewrite cells, it can wander the tape forever, never reaching a verdict. So a computation on an input has exactly three possible outcomes.

  1. Accept. The machine enters its dedicated accept state. The moment it does, it halts immediately — the run is over and the answer is 'yes, this string is in my language'. It does not matter what is on the tape or how much input is left.
  2. Reject. The machine enters its dedicated reject state. Again it halts at once — the run is over and the answer is 'no, this string is not in my language'. Accept and reject are the two ways a Turing machine can halt.
  3. Loop forever. The machine never enters either halting state. It keeps applying transitions step after step without end — perhaps oscillating in place, perhaps marching off to the right writing symbols forever. It gives no answer because it never stops giving. This is the third fate: loop forever.

Be careful with the word 'loop'. It does not mean the machine is broken or that you wrote a bad program — looping is a perfectly legal outcome of a perfectly valid machine. It also does not mean the machine literally repeats the same configuration over and over; that is one way to loop, but a machine can also run forever while never repeating, because the tape is infinite and the configuration can keep growing. 'Loop forever' is shorthand for the single honest fact: it never halts. And crucially, from the outside you generally cannot tell, after watching for any finite stretch, whether a still-running machine will eventually stop or go on forever. Hold that thought — it is the seed of the halting problem two rungs from now.

Recognizing versus deciding: the split the third fate forces

Now we can say precisely what language a Turing machine 'knows'. The language of a Turing machine M is the set of all strings that M accepts. Notice the asymmetry baked into that definition: a string is in the language exactly when M halts in the accept state. But a string not in the language could fail in two utterly different ways — M might reject it (a clean 'no'), or M might loop forever on it (no answer at all). For deciding membership in the language, looping and rejecting look the same from the inside of the definition: neither one accepts. But for you, waiting at the machine, they are worlds apart.

This is exactly why theorists split one intuitive idea into two crisp ones. A language is Turing-recognizable if some machine accepts every string in it — and on strings not in it, that machine is allowed to reject or to loop forever. A recognizer is a machine that says 'yes' for sure on members, but might leave you waiting eternally on a non-member with no 'no' ever coming. A language is decidable if some machine accepts every string in it and rejects every string not in it, always halting on every input. A machine that always halts is a decider; it is a recognizer that has promised never to loop. Every decidable language is recognizable (a decider is a recognizer with a bonus guarantee), but the converse fails: some languages are recognizable yet not decidable. Turing-recognizable is strictly weaker than decidable.

Machines that compute answers, not just yes/no

So far we have used the machine as a judge that says yes or no. But a Turing machine can do something a DFA or PDA never could: leave a useful answer written on the tape when it halts. Used this way the machine is a transducer — it computes a function. You hand it an input on the tape, it halts (we usually require it to halt for this to count as computing a function), and whatever string is left on the tape is the output f(input). Acceptance is just the special case where the only output that matters is a single bit, yes or no. The richer view — a machine as a calculator of functions — is the bridge from 'recognizing patterns' to 'computing anything at all', which is where the Church-Turing thesis is heading.

Let us make this concrete with the most modest function imaginable: add one to a binary number. Say the tape holds 1 0 1 1 (that is 11 in binary) and we want it to hold 1 1 0 0 (that is 12) when the machine halts. Incrementing is just the schoolbook 'carry' done by a machine that can only see one cell at a time, so it must shuttle its head: walk to the least-significant end, then crawl back flipping bits while a carry is alive.

Increment a binary number (head shuttles right, then back left)
Tape alphabet: 0, 1, _ (blank).  Start at the LEFT end.

  Phase 1  walk RIGHT to find the rightmost bit
           keep moving right until you read a blank, then step left

  Phase 2  add the carry from the low end, moving LEFT
           on a 1 : write 0, keep the carry alive, move left
           on a 0 : write 1, carry is absorbed -> HALT (done)
           on _   : write 1, carry overflowed into a new digit -> HALT

Trace on input  1 0 1 1   (^ marks the head):

   1 0 1 1 _        walk right ...
   1 0 1 1 _
           ^        hit blank, step left onto last bit
   1 0 1 1
         ^   read 1 -> write 0, carry, move left      1 0 1 0
       ^     read 1 -> write 0, carry, move left      1 0 0 0
     ^       read 0 -> write 1, carry absorbed         1 1 0 0   HALT

Result on tape: 1 1 0 0   =  12 .  (11 + 1)
An increment transducer. It shuttles right to the low end, then crawls back left flipping 1s to 0s while carrying, stopping the instant it writes a 1 (or runs off the front, growing the number a digit). The head 'shuttling' back and forth is the everyday Turing-machine technique for jobs a one-pass reader cannot do.

Designing a real machine: a^n b^n c^n with marking

Now let us flex the machine on a language that proved earlier models powerless. The pumping lemma for context-free languages showed that {a^n b^n c^n : n >= 0} — equal blocks of a's, then b's, then c's — is not even context-free: no PDA can recognize it, because a single stack can balance two quantities but not three. A Turing machine handles it with ease, and the reason is exactly that the tape is read and write. The trick is the most important design technique there is: marking symbols. Cross off one a, one b, and one c per round, looping until the tape is exhausted.

  1. Find the leftmost un-marked a. Replace it with a mark (say X). If there is no un-marked a left, you are done with the a's — sweep right and check that no un-marked b's or c's remain; if the tape is all marks, accept, otherwise reject.
  2. Move right to the leftmost un-marked b and mark it (say Y). If you reach the c-block or a blank without finding an un-marked b, the counts cannot match — reject.
  3. Move right to the leftmost un-marked c and mark it (say Z). If you run off the end without finding an un-marked c, reject for the same reason.
  4. Shuttle the head all the way back left to the first un-marked symbol and go to step 1. Each pass cancels exactly one a, one b, and one c, so the loop runs n times and then the step-1 check confirms the blocks were equal and in the right order.

Two things to notice. First, this machine always halts — every pass marks at least one symbol, so it cannot loop forever, which means it is a decider and {a^n b^n c^n} is decidable, not merely recognizable. Second, the same toolkit reappears constantly: marking to remember 'I have already counted this one', and shuttling the head left and right to compare symbols that sit far apart. A close cousin of these tricks is treating the tape as several parallel tracks — imagining each cell as holding a little tuple, so you can scribble bookkeeping above the data without destroying it. Marking, tracks, and shuttling are the bread and butter of every Turing-machine design, and the final guide of this rung traces one end to end.