Turing Machine Execution
Watch a machine cross off matching pairs on its tape — writing is what makes it stronger than a stack.
Skip to the animationA Turing machine is a finite control with a head that can read, write and move in both directions along an unbounded tape — and by the Church-Turing thesis, that is everything any computer can do.
What writing changes
A finite automaton reads its input once and cannot record anything. A PDA gets a stack, but only its top is reachable and popping destroys what was there. A Turing machine can write on its input, move back over it, and read what it wrote.
That is the entire upgrade, and it is enough for everything. The machine in the animation uses it to cross off matched pairs: mark the leftmost 0 as X, scan right for a 1 and mark it Y, rewind, repeat. The tape holds the record of which symbols are already accounted for — something no stack could keep, because checking would consume it.
A missing rule is a rejection. Like a DFA with an absent arrow, the machine simply halts with no move available.
Reading the transitions
A label 0→X, R means: seeing 0, write X and move right. Each state has a single job, which is how these machines stay comprehensible:
| State | Job |
|---|---|
| q0 | find the leftmost unmarked 0 and mark it X |
| q1 | scan right past 0s and Ys for a 1, mark it Y |
| q2 | rewind left to the last X |
| q3 | everything is marked — check only Ys remain |
| qa | accept |
Variants that change nothing
Every plausible extension turns out to add no power at all. Each of these can be simulated by the basic model, usually with a polynomial slowdown:
- Multiple tapes — simulable on one tape by interleaving the tracks.
- Two-way infinite tape — fold it in half and use two tracks.
- Nondeterminism — simulable by breadth-first search over the computation tree, at exponential cost in time but no gain in what is computable.
- A bigger alphabet, or a two-dimensional tape — encodable in the basic one.
This robustness is the evidence for the Church-Turing thesis: every model of computation anyone has proposed — lambda calculus, recursive functions, cellular automata, your laptop — computes exactly this same class. The thesis is not a theorem, because "effectively computable" is not a formal notion, but nothing has ever contradicted it.
And the catch
The machine may never halt. That single possibility is what separates decidable languages, where some machine always halts with the right answer, from merely recognisable ones, where it halts and accepts on members but may run forever on non-members. The halting problem lives in exactly that gap.
Advantages and disadvantages
Advantages
- Computes everything that is computable, by any known model.
- Simple enough to reason about formally — a handful of rules and a tape.
- Robust: every variant anyone has tried is equivalent to the basic version.
Disadvantages
- Absurdly slow as an actual model of execution — everything is sequential head movement.
- May not halt, which is the root of every undecidability result.
- Writing even a small machine by hand is laborious and error-prone.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.