The Turing Machine — Theoretical Foundations of Computer Science

Discovery

Technical Explanation

1. Formal definition — The Turing machine consists of: (a) an infinite tape divided into cells, each containing a symbol from a finite alphabet (including the blank symbol □), (b) a read/write head capable of reading the current symbol, writing a symbol, and moving the tape one cell left or right, (c) a state register containing the current state from a finite set Q = {q₁, q₂, ..., qₙ}, and (d) a transition table δ: Q × Σ → Q × Σ × {L, R} that determines, for each (state, read symbol) pair, the new state, the symbol to write, and the direction of movement.

2. Universal machine — Turing demonstrates that there exists a particular Turing machine U (the universal machine) capable of simulating any other Turing machine M: it suffices to encode M's transition table on U's tape. The universal machine reads this description and executes it step by step. This concept is exactly the principle of the stored-program computer: the same machine runs any program.

3. The halting problem — Turing proves by diagonalization (inspired by Cantor) that no Turing machine can decide, for every machine M and every input x, whether M halts or loops indefinitely on x. The proof: assume such a machine H exists; construct a machine D that, on input M, runs H(M, M) and does the opposite (loops if H says "halts", halts if H says "loops"). What does D(D) do? Contradiction. Therefore H cannot exist.

4. Church-Turing thesis — Turing and Church independently arrive at the same result: any computable function can be computed by a Turing machine. This is not a theorem (it cannot be formally proven), but an empirical thesis: no model of computation conceived since 1936 (lambda calculus, cellular automata, quantum machines) has computed a function that the Turing machine cannot compute. Only computation time differs.

Why It Worked

The context: in 1928, David Hilbert poses the Entscheidungsproblem — is there a mechanical procedure to determine the truth or falsity of any mathematical proposition? To answer, Turing first had to formalize what a "mechanical procedure" is. His abstract machine — of radical simplicity (tape, head, states, table) — captures the essence of all effective computation. The simplicity of the model is its strength: everything that can be added (multiple tapes, random access memory, parallelism) only changes the speed, not the class of computable functions.

The negative result (undecidability) is as fundamental as the positive result (computability). It draws an absolute boundary: certain problems are mathematically proven unsolvable by any machine, present or future.

Causal Chain

Hilbert poses the Entscheidungsproblem (1928) → Gödel proves incompleteness (1931) → Church defines lambda calculus (1936) → Turing formalizes the abstract machine and proves undecidability (1936) → Turing breaks Enigma at Bletchley Park with the Bombe (1939–1945) → von Neumann designs the stored-program architecture EDVAC (1945) → first computers (ENIAC 1945, Manchester Baby 1948) → Turing proposes the artificial intelligence test (1950) → programming languages (Fortran 1957, LISP 1958) → NP-completeness complexity theory (Cook, 1971)

Anecdote

Turing's paper nearly went unpublished: when he submitted it in May 1936, he learned that Church had just published an equivalent result via lambda calculus (April 1936). His lecturer and mentor at Cambridge, M.H.A. Newman — his doctoral supervisor would be Alonzo Church, at Princeton — convinced him to maintain the publication because the machine model — concrete, mechanical, visualizable — was fundamentally more intuitive than Church's abstract formalism. Newman was right: it is the Turing machine, not the lambda calculus, that directly inspired the construction of the first computers.

Sources

References verified during the August 2026 fact-checking audit: these are the pages
against which this bulletin's claims were checked.

1. On Computable Numbers, with an Application to the Entscheidungsproblem (fac-similé)
2. The Annotated Turing (contexte et chronologie) — Princeton University Press
3. Apple reveals M3 Ultra (184 milliards de transistors) — Apple Newsroom