The idea: a tape, a head and a table
A Turing machine is the simplest model of a computer that can run any algorithm. It has three parts: a tape of cells that goes on forever in both directions, a head that sits on one cell, and a finite control: a current state plus a fixed table of rules. Every cell that was never written holds the blank □. The input is written on cells 0, 1, 2, … and the head starts on cell 0 in state q0.
One step is always the same: read the symbol under the head, find the rule for (state, symbol), then write a symbol, move one cell left or right, and switch to the next state. The canvas shows each step in two parts: first the rule lights up in the table, then the write, the move and the new state. Press Step for one rule or Run to go until the machine halts.
The state table is the program
Rows are states, columns are the symbols the head can read, and each cell says write, move, next state. "X R q1" means: write X, move right, go to q1. The table is all there is: no variables, no memory besides the tape. The machine is deterministic: at most one rule per (state, symbol). An empty cell means there is no rule; the machine then halts and rejects. Two states stop the machine on purpose: acc (accept) and halt (done computing; the answer is what is left on the tape).
Computing: adding 1 in binary
The Binary +1 machine has two states. q0 walks right over the digits to the first blank, then turns left into q1. q1 is the carry: a 1 becomes 0 and the carry keeps moving left; the first 0 becomes 1 and the machine halts. 1011 becomes 1100 in 8 steps (Demo: binary +1). If every digit is 1, the carry runs off the left end of the number and writes a 1 on a blank cell: 111 becomes 1000, a number one digit longer (Demo: the carry grows the number). The tape has room because it never ends.
| step | state | reads | rule | tape after |
|---|---|---|---|---|
| 1–4 | q0 | 1, 0, 1, 1 | write the same, move R | 1011 |
| 5 | q0 | □ | □ L q1 | 1011 |
| 6 | q1 | 1 (cell 3) | 0 L q1 | 1010 |
| 7 | q1 | 1 (cell 2) | 0 L q1 | 1000 |
| 8 | q1 | 0 (cell 1) | 1 L halt | 1100 |
Deciding: aⁿbⁿcⁿ, which no pushdown automaton can
The aⁿbⁿcⁿ machine accepts strings like abc and aabbcc: some a's, then the same number of b's, then the same number of c's. It works like crossing off items on paper. Each pass marks one a as X, one b as Y and one c as Z, and q3 walks back left to the last X. When q0 finds a Y instead of an a, every a is used up, and q4 and q5 check that only Y's and Z's are left before the blank. aabbcc is accepted after 23 steps (Demo: aⁿbⁿcⁿ accepts aabbcc). In aabbc the second pass finds a blank where a c should be; the table has no rule for (q2, □), so the machine rejects (Demo: aⁿbⁿcⁿ rejects aabbc).
A finite automaton cannot even check aⁿbⁿ: it has no memory besides its state, so it cannot count up to any n. A pushdown automaton adds one stack and can check aⁿbⁿ (push for each a, pop for each b), but after that check the stack is empty, so it cannot also compare with the c's. The Turing machine can go back and read the tape again, which is exactly what q3 does. That makes it the top of the hierarchy.
| machine | memory | example it handles | languages |
|---|---|---|---|
| finite automaton | the state only | (a|b)*abb | regular |
| pushdown automaton | one stack | aⁿbⁿ, balanced parentheses | context-free |
| Turing machine | a tape it can read, write and reread | aⁿbⁿcⁿ, any algorithm | decidable (if it always halts) |
Machines that never halt
Nothing forces a Turing machine to stop. The Search right for a 1 machine walks right until it reads a 1. On 0001 it halts after 4 steps. On 000 it walks over blanks forever, and the tape window keeps scrolling (Demo: a search that never halts). The page stops each Run after 30 steps so the browser does not hang.
For this tiny machine it is easy to see that it never halts. In general it is not: Turing proved in 1936 that no machine can take any other machine and its input and always answer correctly whether it halts. This is the halting problem. A simulator can only run and wait; it can never be sure that "not halted yet" means "never".
The Church–Turing thesis says that anything a step-by-step procedure can compute, a Turing machine can compute too. Real CPUs are not faster in principle, only in practice: they have random access memory instead of a tape, but each can simulate the other.
See also Regex to NFA to DFA for the finite automata at the bottom of the hierarchy, CYK Parsing for deciding a context-free language with a table, and Finite State Machines for the same state-and-table idea in hardware.
One step down the hierarchy, a machine with only a stack: see Pushdown Automaton.
What the page leaves out
Nondeterministic and multi-tape Turing machines (they compute the same things, only faster), the formal 7-tuple definition, the universal Turing machine that runs a table written on its own tape, the proof of the halting problem by diagonalization, recognizable vs decidable languages, linear bounded automata and context-sensitive languages, time and space complexity (P, NP), and the busy beaver function.
See where this page fits on the Logic, Sets & Counting mind map.