Climbing off the top of the stack
You have spent several rungs handing machines just a little more memory and watching their power grow. A DFA remembers only its current state — a turnstile that knows nothing of where it has been. A pushdown automaton bolted on one stack, enough to count matched nesting like a^n b^n but still blind to everything except the top plate. Each time, a stubborn language slipped just out of reach: a DFA cannot do a^n b^n, and a PDA cannot do a^n b^n c^n (three quantities to keep in step is one stack too few). The obvious next question of this rung: what memory is enough to compute anything computable at all?
The answer, found by Alan Turing in 1936, is almost embarrassingly simple. Take away the restrictions on the memory. Instead of a stack you can only touch on top, give the machine a long strip of paper — a tape divided into cells, one symbol per cell — and a movable head parked over one cell. The head may read the symbol under it, erase it and write a new one, and then step one cell left or right. That is the whole upgrade. The picture to hold in your mind is an endless notebook: you can scan back to anything you wrote earlier, cross it out, and rewrite it. Nothing is locked away; nothing is forced off the top.
Why a notebook is the right picture
Three freedoms separate the tape from every memory you have met. First, it is read AND write: the input is not a stream that flows past once, it is written on the tape, and the machine may overwrite it as it works (a DFA could never alter what it read). Second, the head moves both directions: it can shuttle back to re-examine a symbol it passed long ago, where a stack hides everything beneath the top. Third, the tape is unbounded: it has a left end where the input sits but stretches off to the right forever, so the machine never runs out of room. To the right of the input lie infinitely many cells holding a special blank symbol (written ⊔ or B), the tape's way of saying "nothing written here yet."
Where the symbols live: two alphabets and a snapshot
Just as a PDA kept its input alphabet Σ separate from its stack alphabet Γ, a Turing machine works with two alphabets that you must keep apart. The input alphabet Σ (Sigma) holds the symbols an input string may contain. The tape alphabet Γ (Gamma) is a strictly larger set that the machine may write onto the tape: it contains all of Σ, plus the blank symbol, plus any private bookkeeping symbols the machine invents — for example a marked 'a' written as X to mean "this 'a' has already been counted." The blank symbol lives in Γ but never in Σ, so an input string itself can never contain a blank.
Back with a PDA, you learned that one number — the current state — was no longer enough to describe the situation; you needed a snapshot of (state, remaining input, stack). A Turing machine needs the same kind of complete photograph, called a configuration. To know exactly where a TM stands you need three things: (1) its current state, (2) the entire contents of the tape, and (3) the position of the head. Capture those three and you can resume the computation from nothing else — the configuration is the machine's total situation at one instant, the way an instantaneous description was for a PDA.
One move: read, write, step
A DFA's rule read a symbol and changed state. A PDA's rule read three things and rebuilt the stack top. A Turing machine's single rule, its transition function, does the most of all in one tick. Its shape is delta(q, a) = (p, b, D): when in state q with the head reading symbol a, the machine moves to state p, overwrites a with symbol b in that same cell, then steps the head one cell in direction D, where D is either L (left) or R (right). Read the cell, write the cell, take one step — that is the entire instruction set, and every Turing computation is just this triple repeated.
Notice three honest details. The machine must write something on each move — to leave a cell unchanged it simply writes back the same symbol it read (b = a), exactly as a PDA could pop X and push X to stand still. The head can write a blank, effectively erasing a cell. And because the rule reads the symbol under the head and may rewrite the whole tape, a TM can mark a symbol, march far away, do work, and shuttle back to read its own note — the move that finally cracks a^n b^n c^n. That shuttling is impossible for a stack, and it is the heart of why this model is stronger.
Marking off matched pairs for a^n b^n on a Turing machine
(input alphabet Sigma = {a, b}; tape alphabet Gamma = {a, b, X, B}; B = blank)
Idea: cross off the leftmost a (write X), shuttle right to cross off the
leftmost remaining b (write X), return left, repeat. Accept when none left.
Configuration shown as: ...tape..., ^ marks the cell under the head
start [ a a b b B ] input aabb on the tape
^
mark a [ X a b b B ] write X over first a, walk RIGHT past a's
^
[ X a b b B ] keep stepping right over a, then over b...
^
find b [ X a X b B ] write X over first b, now walk LEFT
^
back left [ X a X b B ] step left until an X, then onto the next a
^
mark a [ X X X b B ] cross the next a ... walk right to next b
^
find b [ X X X X B ] cross the last b
scan [ X X X X B ] no a, no b left -> ACCEPT (counts matched)
If an a is left with no b (or a b with no a), the scan finds a leftover
letter -> REJECT. The X's are the machine's private notes, never input.Three endings, and a machine that also computes
When a DFA finished, it had simply run out of input and you checked whether its state was accepting. A Turing machine ends differently, because it controls its own head and need not march steadily toward an end of input. A TM run reaches one of three outcomes. It can halt in a designated accept state (success). It can halt in a designated reject state (failure). Or — the genuinely new possibility — it can loop forever, never halting at all, the head shuttling endlessly while no accept or reject state is ever entered. This third ending has no analogue downstairs: a DFA always stops, a Turing machine need not.
That third outcome forces a distinction this whole rung will hinge on, so meet it now in plain words. A language is recognized by a TM if the machine accepts exactly the strings in the language — but on a string NOT in the language it is allowed to reject or to loop forever. A language is decided by a TM if the machine is a halting one: it always stops, accepting members and rejecting non-members, never looping. Deciding is the gold standard — a definite yes-or-no every time — while recognizing tolerates a machine that may run off into an endless computation and never give you an answer. Guides 3 and 4 of this rung are devoted to exactly this gap; for now, just file away that looping is real and that it splits these two words apart.
One last reframing keeps this model from feeling narrow. We have spoken of a TM as a yes/no machine for a language, but the very same hardware computes functions. Start with an input on the tape; if and when the machine halts, whatever string is left on the tape is the output. So a TM with input the binary number 1011 can halt with 1100 on its tape — it has computed an increment. Copying its input to produce two side-by-side copies, or adding two numbers, works the same way: write, mark, shuttle, rewrite. A Turing machine is therefore not just a more powerful recognizer than a PDA; it is a full-blown, if exquisitely simple, computer — the reason it became the very definition of what "computable" means.