Automata & Formal Languages · Instrument 04 · Turing Machines

The whole of computation

Swap the stack for an unbounded tape the head can read, write, and move across both ways, and you reach the ceiling. A Turing machine can compute anything any computer can — it is the definition of computable. A handful of states, one tape, and the universe of algorithms opens up.

Run
Transition table
Space-time
Busy beaver & limits
Machine
Input
A configuration is the tape, the head position, and the state. Each step reads the symbol under the head, then the transition δ(state, read) = (write, move, next) fires. Halt states (H, accept, reject) stop the machine.
tape
Machine
The transition table is the program. The highlighted row is the rule firing right now — matched on the current state and the symbol under the head.
δ table
Machine
Each row is the tape at one instant, time running downward; the head position is marked. This computation history makes the machine's logic visible — busy beavers trace strikingly intricate patterns before halting.
space-time diagram
The busy beaver function
BB(n) asks: among all n-state machines that halt on a blank tape, what's the most steps (or 1s) any of them takes? The values explode beyond any pattern — and crucially, BB(n) is uncomputable: no algorithm can compute it for all n, because doing so would solve the halting problem.
how fast can small machines run?