Alan Turing

Hilbert's Program and the Entscheidungsproblem (1900–1935)

At the 1900 International Congress of Mathematicians in Paris, David Hilbert outlined his vision to provide a secure, complete foundation for all mathematics: 1. Consistency (Widerspruchsfreiheit): Proving that no contradiction could ever be derived from the formal axioms of mathematics. 2. Completeness (Vollständigkeit): Proving that every true mathematical proposition can be derived within the system. 3. Decidability (Entscheidungsproblem): Devising a definite, mechanical algorithm that, given any well-formed formula in the first-order predicate calculus, decides in a finite sequence of operations whether it is logically valid.

Kurt Gödel’s Incompleteness Theorems (1931) dismantled the first two aspirations by demonstrating that any consistent formal system capable of expressing arithmetic contains true statements that cannot be proven within the system, and cannot prove its own consistency. However, the Entscheidungsproblem remained open: could an effective decision procedure exist for the remaining fragments of logic?

The Pre-Machine Definition of "Computer"

Before 1936, the noun "computer" designated a human being performing numerical calculations according to prescribed rules. Calculation was circumscribed by physical instruments: * Logarithm and Trigonometric Tables: Prone to typographical, copying, and transcription errors. * Mechanical Adding Machines: Babbage’s Difference Engine, the Millionaire Calculator, and Marchant/Monroe electromechanical calculators used mechanical gears, stepping drums, and pinwheels to compute addition, subtraction, multiplication, and division. * Lack of Formal Abstraction: Mathematicians lacked an axiomatic definition of what constituted an "effective mechanical method." Without a formalization of an algorithm, it was impossible to prove a negative result—that no algorithm could exist for a specific problem.

2.1 Formal Definition of the Turing Machine

In his 1936 paper, "On Computable Numbers, with an Application to the Entscheidungsproblem", Turing formalized the intuitive concept of effective calculability via an abstract automaton.

Formally, a deterministic, single-tape Turing Machine is a 7-tuple: $$M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$$

Where: * $Q$ is a finite, non-empty set of internal states of mind. * $\Gamma$ is a finite, non-empty set of tape symbols. * $b \in \Gamma$ is the blank symbol. * $\Sigma \subseteq \Gamma \setminus \{b\}$ is the set of input symbols. * $\delta: (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L, R\}$ is the partial transition function mapping the current state and scanned symbol to a next state, a written symbol, and a tape head movement (Left or Right). * $q_0 \in Q$ is the initial start state. * $F \subseteq Q$ is the set of halting (accepting) states.

Instantaneous Description (Configuration)

A configuration of $M$ at time step $t$ is an element of $\Gamma^* \times Q \times \Gamma^*$, conventionally denoted: $$u \, q \, v$$ where $u \in \Gamma^*$ is the tape content to the left of the head, $q \in Q$ is the current state, and $v \in \Gamma^*$ is the tape content from the scanned cell to the end of the non-blank tape.

The step relation $\vdash_M$ defines the deterministic state evolution: $$u a \, q \, b v \vdash_M \begin{cases} u \, q' \, a c v & \text{if } \delta(q, b) = (q', c, L) \\ u a c \, q' \, v & \text{if } \delta(q, b) = (q', c, R) \end{cases}$$

2.2 The Universal Turing Machine ($U$)

Turing proved that the transition function table of any machine $M$ can be mapped injectively onto a finite string over an alphabet $\Sigma_U = \{0, 1\}$ via Gödel-style enumeration: $$\text{Code}(M) = \langle M \rangle \in \{0, 1\}^*$$

A Universal Turing Machine $U$ accepts as input the concatenation of a description $\langle M \rangle$ and an input word $w \in \Sigma^*$: $$U(\langle M, w \rangle) = M(w)$$

$U$ simulates each discrete step of $M$ on $w$ by maintaining two regions on its work tape: one representing the simulated state and tape of $M$, and the other tracking the current configuration marker. This established the stored-program architecture: programs are computationally identical to data.

2.3 The Undecidability of the Halting Problem

Turing resolved the Entscheidungsproblem by proving that the Halting Problem ($H$) is undecidable.

Let: $$H = \{ (\langle M \rangle, w) \mid M \text{ halts on input } w \}$$

Proof by Contradiction (Diagonalization)

Assume there exists a total computable decision machine $H_{\text{dec}}$ such that: $$H_{\text{dec}}(\langle M \rangle, w) = \begin{cases} \text{ACCEPT} & \text{if } M(w) \text{ halts} \\ \text{REJECT} & \text{if } M(w) \text{ loops indefinitely} \end{cases}$$

Construct an adversarial machine $D$ that accepts as input a machine description $\langle M \rangle$: $$D(\langle M \rangle) = \begin{cases} \text{LOOP FOREVER} & \text{if } H_{\text{dec}}(\langle M \rangle, \langle M \rangle) = \text{ACCEPT} \\ \text{HALT} & \text{if } H_{\text{dec}}(\langle M \rangle, \langle M \rangle) = \text{REJECT} \end{cases}$$

Now evaluate the behavior of $D$ when provided with its own encoding $\langle D \rangle$: * If $D(\langle D \rangle)$ halts, then by construction $H_{\text{dec}}(\langle D \rangle, \langle D \rangle) = \text{ACCEPT}$, which implies $D(\langle D \rangle)$ must loop forever (contradiction). * If $D(\langle D \rangle)$ loops forever, then $H_{\text{dec}}(\langle D \rangle, \langle D \rangle) = \text{REJECT}$, which implies $D(\langle D \rangle)$ must halt immediately (contradiction).

Therefore, $H_{\text{dec}}$ cannot exist. Because any algorithm deciding valid formulas in first-order logic could be used to solve the halting problem, the Entscheidungsproblem is uncomputable.

3.1 The Turing Machine Geometry

                 Finite State Controller [ State: q ∈ Q ]
                                   │
                                   ▼
... ───┬───────┬───────┬───────┬───────┬───────┬───────┬─── ...
       │ s_i-2 │ s_i-1 │  s_i  │ s_i+1 │ s_i+2 │ s_i+3 │     Tape Γ* (Infinite)
... ───┴───────┴───────┴───────┴───────┴───────┴───────┴─── ...
                           ▲
                           │ Read/Write Head [ Action: Write s', Move {L, R}, State q' ]

3.2 The Bletchley Park Bombe Cycle

flowchart TD
    Intercept[Intercepted Enigma Ciphertext] --> Crib[Known Plaintext Crib: Wetterbericht]
    Crib --> Graph[Construct Menu Graph: Letters as Nodes, Enigmas as Edges]
    Graph --> Bank[Setup Synchronized Scrambler Drums: 3 x 12 Banks]
    Bank --> TestVoltage[Inject Electrical Test Voltage at Hypothetical Bus]
    TestVoltage --> Feedback{Check Current Loop}
    Feedback -- Current on 25 paths --> Contradiction[Hypothesis Refuted: Advance Rotor by 1 step]
    Feedback -- Current on 1 path --> Stop[BOMBE STOP: Plausible Rotor Configuration Found]
    Contradiction --> Bank
    Stop --> Verify[Manual Verification on Typex / Hand Decryption]

4.1 Cryptanalysis of Naval Enigma: Banburismus & Decibans

At Bletchley Park, Turing developed Banburismus to determine the identity of the right-hand and middle rotors of German Naval Enigma (M3/M4) without exhaustive physical searching on the Bombes.

Bayes Factor and Information Measurement

Turing defined the "weight of evidence" for hypothesis $H$ given observation $E$ as the logarithm of the odds factor: $$W(H : E) = \log_{10} \frac{P(E \mid H)}{P(E \mid \neg H)}$$

He defined the units: * Ban: A weight of evidence of factor 10 ($W = 1$). * Deciban ($db$): A weight of evidence of factor $10^{0.1} \approx 1.259$: $$\text{Score in } db = 10 \log_{10} \frac{P(E \mid H)}{P(E \mid \neg H)}$$

The Index of Coincidence

For two ciphertexts aligned with an offset of $k$ characters, Turing measured the coincidence count $C_k$ of identical letters: $$\mathbb{E}[C_k \mid \text{Same Rotors}] \approx \sum_{i=1}^{26} p_i^2 \approx 0.067 \quad (\text{German text redundancy})$$ $$\mathbb{E}[C_k \mid \text{Different Rotors}] \approx \frac{1}{26} \approx 0.038 \quad (\text{Random noise})$$

When the accumulated evidence reached $+20\text{ to }+25\,db$ (odds of $\approx 300:1$), the rotor hypothesis was accepted and scheduled for confirmation on the Bombe.

4.2 Morphogenesis: Chemical Reaction-Diffusion Systems (1952)

In "The Chemical Basis of Morphogenesis" (Phil. Trans. R. Soc. B, 1952), Turing demonstrated how spatial pattern emerges spontaneously from a homogeneous chemical state.

Two-Component Reaction-Diffusion Partial Differential Equations

Let $u(\mathbf{x}, t)$ and $v(\mathbf{x}, t)$ denote the concentrations of an activator and an inhibitor morphogen: $$\begin{aligned} \frac{\partial u}{\partial t} &= D_u \nabla^2 u + f(u, v) \\ \frac{\partial v}{\partial t} &= D_v \nabla^2 v + g(u, v) \end{aligned}$$

Where: * $D_u, D_v$ are molecular diffusion constants. * $\nabla^2 = \frac{\partial^2}{\partial x^2} + \frac{\partial^2}{\partial y^2}$ is the spatial Laplacian operator. * $f(u, v), g(u, v)$ represent non-linear reaction kinetics.

Turing Instability Conditions

A uniform steady state $(u_0, v_0)$ where $f(u_0, v_0) = g(u_0, v_0) = 0$ is stable to spatially uniform perturbations if: $$\text{Tr}(\mathbf{J}) = f_u + g_v < 0, \quad \det(\mathbf{J}) = f_u g_v - f_v g_u > 0$$

However, spatial diffusion induces instability (Turing bifurcation) if the inhibitor diffuses significantly faster than the activator: $$D_v \gg D_u$$ $$D_v f_u + D_u g_v > 2 \sqrt{D_u D_v (f_u g_v - f_v g_u)}$$

Under these conditions, small thermal fluctuations are amplified into stationary, periodic standing waves of chemical concentration, mathematically predicting leopard spots, zebra stripes, and drosophila body segmentation decades before molecular morphogens were physically isolated.

5.1 Rice’s Theorem & Semantic Incomputability (1953)

The Halting Problem is not an isolated singularity. Formulated by Henry Gordon Rice, Rice's Theorem generalizes Turing's result: $$\text{Any non-trivial semantic property of partial computable functions is undecidable.}$$ Let $\mathcal{P}$ be a set of computable functions. If $\mathcal{P} \neq \emptyset$ and $\mathcal{P} \neq \text{All computable functions}$, then the language: $$L_\mathcal{P} = \{ \langle M \rangle \mid M \text{ computes a function in } \mathcal{P} \}$$ is undecidable. Software verification cannot determine whether an arbitrary program produces correct outputs, leaks memory, or behaves securely.

5.2 The Busy Beaver Function $\Sigma(n)$

Turing's uncomputability gives rise to functions that grow faster than any conceivable computable sequence. The Busy Beaver function $\Sigma(n)$, introduced by Tibor Radó, defines the maximum number of non-blank symbols a halting $n$-state, 2-symbol Turing Machine can print onto a blank tape: * $\Sigma(1) = 1$ * $\Sigma(2) = 4$ * $\Sigma(3) = 6$ * $\Sigma(4) = 13$ * $\Sigma(5) \ge 4098$ * For any computable total function $f(n)$, there exists $N$ such that $\forall n > N$: $$\Sigma(n) > f(n)$$

5.3 Physical Tape Constraints & Spatial Locality

The Turing Machine assumes an infinite, uniform tape with $\mathcal{O}(1)$ random access cost per cell. In physical space: * Bremermann's Limit: The maximum computational speed of a self-contained system in the physical universe is governed by quantum limits: $$c_{\text{max}} = \frac{2mc^2}{\pi \hbar} \approx 1.36 \times 10^{50} \text{ bits/second/kilogram}$$ * Bekenstein Bound: The maximum information $I$ stored within a sphere of radius $R$ and energy $E$ is bounded by gravitational event horizons: $$I \le \frac{2 \pi R E}{\hbar c \ln 2}$$ The ideal abstract tape of Turing violates general relativity when scaled to infinite memory density.

(Badge Key: V Verified Verified Primary Source; C Corroborated Corroborated Multi-Source; S Single-Source Single Source; I Interpretation Critical Interpretation).

1. Turing, Alan M. (1936–1937). "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society, Series 2, Vol. 42, pp. 230–265; Correction in Vol. 43, pp. 544–546. * Archival Role: The foundational paper of computer science. Introduces the Turing machine, the Universal Turing Machine, and the undecidability of the Halting Problem.
2. Turing, Alan M. (1939). "Systems of Logic Based on Ordinals." Proceedings of the London Mathematical Society, Series 2, Vol. 45, pp. 161–228. (Ph.D. Dissertation under Alonzo Church at Princeton). * Archival Role: Investigated transfinite hierarchies of Turing machines equipped with oracles ($\mathcal{O}$-machines) to analyze Gödel incompleteness beyond arithmetic.
3. Turing, Alan M. (1940). Treatise on the Enigma (The "Prof's Book"). Bletchley Park Internal Wartime Technical Report. Declassified by GCHQ and released to the UK National Archives (HW 25/3). * Archival Role: Detailed mathematical theory of the Enigma rotor permutation group, the Bombe menu logic, and Banburismus.
4. Turing, Alan M. (1945). Proposed Electronic Calculator. Executive Committee of the National Physical Laboratory (NPL), Report E.882. * Archival Role: Complete blueprint for the Automatic Computing Engine (ACE). Preceded the EDVAC report; detailed micro-code concepts, floating point representation, and subroutine call stacks.
5. Turing, Alan M. (1950). "Computing Machinery and Intelligence." Mind, Vol. 59, No. 236, pp. 433–460. * Archival Role: The philosophical foundation of Artificial Intelligence. Articulates the Imitation Game, analyzes the theological, mathematical, and neurological objections to thinking machines, and proposes machine learning from childhood states.
6. Turing, Alan M. (1952). "The Chemical Basis of Morphogenesis." Philosophical Transactions of the Royal Society of London, Series B, Biological Sciences, Vol. 237, No. 641, pp. 37–72. * Archival Role: Founded mathematical developmental biology. Demonstrates how two interacting, diffusing chemicals generate standing spatial waves that dictate biological organism form.