How the Turing machine was forced (history)

Parent: turing-machines

The machine isn't invented, it's distilled from "what a human following rules can do." The history shows why every feature is there.

1. The motivation: Hilbert's Entscheidungsproblem (1928)

Hilbert asked for a definite method that, given any first-order statement, decides whether it's provable. To answer it — especially to prove no such method exists — you must first define "algorithm / effectively calculable" mathematically. Before 1936, "algorithm" was only intuitive. That gap is the motivation.

2. Three independent formalizations (1934–36)

Gödel–Herbrand (1934): general recursive functions — defined by systems of equations; = primitive recursion + Kleene's μ-operator (unbounded search, "least n such that…"), which is what escapes the always-halting primitive-recursive world.
Church (1936): λ-calculus — "effectively calculable" ⟺ "λ-definable"; used to show the Entscheidungsproblem is unsolvable.
Turing (1936): the machine — same class, but reached by analysing computation itself.

3. Turing's analysis (why the machine looks like that)

Turing asked: what does a human computer — a person doing a calculation by fixed rules — actually do? Each real limitation becomes a machine feature:

Deriving the machine from a human calculator

Symbols on paper → idealize to a one-dimensional tape of squares.

Finite attention → a finite alphabet, one square read at a time.

Next action depends on the symbol seen and a "state of mind" that must be finite (only boundedly many distinguishable mental states).

Each step: from (state, symbol) → write/erase, move one square left/right, change state.

That is all a mechanical step can be — which is why the resulting machine is convincing as the definition of algorithm. Gödel, unconvinced by λ-calculus and by his own recursion equations, accepted Turing's analysis as decisive.

4. The Church–Turing thesis

Turing and Kleene proved λ-definable = general recursive = Turing-computable — three unrelated starting points, one class. Kleene built recursion theory (μ-recursion, normal-form, s-m-n, the recursion/fixed-point theorem) and coined "Church's thesis."

Church–Turing thesis

"Effectively calculable" = "Turing-computable." A thesis, not a theorem — it identifies an informal notion with a formal one; its evidence is the collapse of all independent formalizations into the same class.

5. The payoff: halting, and back to Hilbert

The universal machine lets a machine talk about machines. Diagonalizing on it gives the halting-problem — no machine decides whether an arbitrary (M,x) halts. Reducing halting to provability then answers Hilbert: the Entscheidungsproblem is unsolvable — the first natural undecidable problem, and the Turing/Gödel threshold of recursion-is-a-phase-transition.