Turing machines — worked examples

Parent: turing-machines

Concrete machines you can trace by hand. Each child gives its machine as the full 7-tuple (Q, Γ, b, Σ, δ, q₀, F), then traces the tape step by step, naming which component acts.

Examples

• binary-successor — n ↦ n+1, traced bit by bit against the 7-tuple (the clearest first trace).
• anbn-recognizer — recognize { 0ⁿ1ⁿ } by crossing off pairs; uses the tape as unbounded memory (a finite automaton can't).
• universal-machine — U(⟨M⟩, x): the transition table lives on the tape — data = program.