THE TURING MACHINE a tape, a head, a table of rules; all of computation
A finite table of rules, a head that reads and writes one cell, and an unbounded tape — that is the whole machine, and it is enough to compute anything computable. Turing built it in 1936 not to make a computer but to prove a limit: the halting problem is undecidable, so the Entscheidungsproblem has no algorithm. Every real CPU is a bounded approximation of this one idea.
THE TECHNIQUE read, write, move, change state
A tiny Turing machine that increments a binary number: start at the right, flip 1→0 and carry left, until a 0→1 stops it. Watch the head sweep and the tape change — 1011 (11) becomes 1100 (12): live demo
HISTORY & CREDIT Alan Turing, 1936
“Turing invented the Turing machine as a design for a computer.” — no. He built it to prove an impossibility (the Entscheidungsproblem has no decision procedure); the term “Turing machine” was coined by Church (1937), and the equivalent λ-calculus is Church’s — together the Church-Turing thesis. cited
1936 · Alan Turing — “On Computable Numbers, with an Application to the Entscheidungsproblem” (Proc. London Math. Soc.): the a-machine, the universal machine, and the undecidability of halting. 1936 · Alonzo Church — the λ-calculus reaches the same limit independently; Church names the model “Turing machine” in his 1937 review. thesis · the Church-Turing thesis: every effectively-calculable function is Turing-computable — a claim about the reach of computation, not a theorem.
The universal Turing machine — one machine that reads another machine’s table off the tape and simulates it — is the stored-program computer in embryo, thirteen years before ENIAC. Turing, 1936
RECOMMEND FOR I-13 the tape, computed
The increment machine runs on the canonical compiler — a tape array, a head index, native recursion:
$ i13 run tm.i13 # binary-increment TM: flip 1->0 carrying left, until 0->1
tape 1011 (11) -> 1100
val = 12 -- the head swept left over three 1s, flipped them, set the 0 to 1
Recommend: the Turing machine is LIT on I-13 — the increment machine runs as a tape array with a head index and a rule table, verified 1011 (11) → 1100 = 12. I-13 is itself a bounded Turing machine (finite tape: the 4096-frame recursion limit and the array bound), which is the honest frame for the whole language: it computes anything computable within its bounds, and the bounds are declared, not hidden. This dart opens THE AUTOMATON (batch 28) — the theory the compiler front-end (batches 22–23) rests on — and its restriction to a stack (175) or to no memory (a DFA) is the rest of the hierarchy.