Turing machine

Parent: logic

The formal model of "algorithm." (Why it looks exactly this way → history; classic machines → examples, busy-beaver.)

Turing machine

A 7-tuple (Q, Γ, b, Σ, δ, q₀, F):

• Q — a finite set of states; q₀ ∈ Q the start, F ⊆ Q the halting states;
• Γ — a finite tape alphabet; b ∈ Γ the blank symbol; Σ ⊆ Γ∖{b} the input alphabet;
• δ : (Q∖F) × Γ → Q × Γ × {L,R} — the transition function. Plus a two-way-infinite tape of cells (each holding a symbol of Γ) and a head on one cell.

Run. A configuration is (state, tape contents, head position). Each step: read the scanned symbol a; if δ(q,a)=(q',a',D), write a', move the head one cell D∈{L,R}, and enter state q'. Halt on reaching F (or where δ is undefined). M computes f if, started with x on the tape, it halts with f(x) on the tape.

Essentials

• Robust to variants. Multi-tape, 2-D tape, k-symbol, nondeterministic — all compute the same class (mutual simulation, at worst polynomial overhead). This robustness is why the model is the definition, not an arbitrary choice.
• Universal machine. There is a single TM U that, given a description ⟨M⟩ and input x, simulates M(x). Data = program — the germ of the stored-program computer.
• Decide vs recognize. M decides a set if it halts on every input with yes/no; it recognizes (semi-decides) a set if it halts exactly on the yes-instances. That one-sided gap is where undecidability lives (halting is recognizable, not decidable).

Children

• history — the definition was forced: Hilbert's Entscheidungsproblem → Turing's analysis of a human calculator → Church/Kleene → the Church–Turing thesis.
• halting-problem — the first undecidable problem (diagonalization); Rice; reductions.
• examples — small concrete machines you can trace by hand (successor, 0ⁿ1ⁿ, universal).
• famous-machines — busy-beaver, smallest-universal, Langton's ant, Rule 110, foundational (ZFC/Goldbach/Riemann) machines.