In 1936, a 24-year-old British mathematician named Alan Mathison Turing set out to resolve David Hilbert’s remaining foundational challenge: the Entscheidungsproblem (the Decision Problem). To determine whether there exists an algorithmic procedure capable of deciding the truth of any first-order mathematical statement, Turing had to first invent the theoretical definition of mechanical computation itself. The result was the Turing Machine, the Church-Turing Thesis, and the proof that the Halting Problem is fundamentally unsolvable.
1. The Formal Architecture of a Turing Machine
Turing abstracted the human computer into a physical automaton operating on discrete symbols. Formally, a deterministic Turing Machine (TM) is a 7-tuple:
[
M = langle Q, Sigma, Gamma, delta, q_0, q_{text{accept}}, q_{text{reject}} rangle
]
- $Q$ is a finite set of internal control states.
- $Sigma$ is the finite input alphabet not containing the blank symbol $sqcup$.
- $Gamma$ is the finite tape alphabet containing $Sigma cup {sqcup}$.
- $q_0 in Q$ is the start state.
- $q_{text{accept}}, q_{text{reject}} in Q$ are distinct halting states.
- $delta: Q times Gamma to Q times Gamma times {L, R}$ is the deterministic transition function. Given the current state and symbol under the read/write head, $delta$ specifies the next state, the symbol to write, and whether the head moves Left ($L$) or Right ($R$).
The tape is semi-infinite or bi-infinite, divided into discrete cells, serving as unbounded physical memory.
2. The Church-Turing Thesis
Between 1934 and 1936, three radically different formalisms for “effective calculability” were invented:
- General Recursive Functions (Gödel, Herbrand, Kleene)
- $lambda$-Calculus (Alonzo Church)
- Turing Machines (Alan Turing)
Remarkably, Church and Turing proved that all three formalisms are extensively mathematically equivalent: a function is $lambda$-definable if and only if it is general recursive if and only if it is computable by a Turing machine.
The Church-Turing Thesis
Any algorithmic procedure that can be carried out by a human mathematician following mechanical rules—or by any physically realizable digital computing device—can be simulated by a universal Turing Machine.
3. Turing Decidability vs Turing Recognizability
Languages (problems) fall into fundamental complexity classes:
- Turing-Decidable (Recursive, $mathcal{R}$): There exists a machine $M$ that halts on all inputs, accepting strings in $L$ and rejecting strings not in $L$.
- Turing-Recognizable (Recursively Enumerable, $mathcal{RE}$): There exists a machine $M$ that halts and accepts if $w in L$. If $w notin L$, $M$ may either reject or loop infinitely.
4. The Halting Problem & Diagonalization Proof
The Halting Problem asks: given the description of a Turing machine $langle M rangle$ and an input $w$, does $M$ halt on input $w$?
[
A_{text{TM}} = { langle M, w rangle mid M text{ is a TM and } M text{ accepts } w }
]
[
H_{text{TM}} = { langle M, w rangle mid M text{ is a TM and } M text{ halts on } w }
]
Turing’s Theorem: The Halting Problem is Undecidable
$H_{text{TM}}$ is not Turing-decidable ($H_{text{TM}} notin mathcal{R}$).
Proof (Cantor’s Diagonalization):
- Suppose for contradiction that $H_{text{TM}}$ is decidable by a machine $H$. When given $langle M, w rangle$, $H$ halts and outputs ACCEPT if $M$ halts on $w$, and outputs REJECT if $M$ loops infinitely.
- Construct a new adversary machine $D$ that takes as input the code of a machine $langle M rangle$:
- $D$ runs $H$ on the input $langle M, langle M rangle rangle$.
- If $H$ says ACCEPT ($M$ halts on its own description), $D$ enters an infinite loop!
- If $H$ says REJECT ($M$ loops on its own description), $D$ immediately halts and accepts!
- Now, what happens if we feed the machine $D$ its own description $langle D rangle$?
- By construction:
[
D(langle D rangle) text{ halts} iff H(langle D, langle D rangle rangle) text{ rejects} iff D(langle D rangle) text{ loops infinitely!}
] - This is a flat logical contradiction! $D$ halts if and only if it does not halt.
- Therefore, the decider $H$ cannot exist! The Halting Problem is strictly undecidable. $blacksquare$
5. Resolution of Hilbert’s Entscheidungsproblem
Turing reduced the Halting Problem directly to first-order provability. For any machine $M$ and input $w$, one can write a first-order formula $phi_{M, w}$ that asserts: “Machine $M$ reaches state $q_{text{accept}}$ on input $w$.”
If an algorithm existed that could decide first-order validity $vDash phi_{M, w}$, it could decide whether $M$ halts on $w$. Since the Halting Problem is undecidable, no decision algorithm for first-order logic can ever exist. Hilbert’s dream of an algorithmic oracle for mathematics was officially dissolved forever.
