Alan Turing

Alan Mathison Turing (1912–1954) was a British mathematician, logician, and codebreaker who founded theoretical computer science with the abstract "Turing machine," helped break German Enigma ciphers in World War II, and pioneered the conceptual foundations of artificial intelligence and mathematical biology. Key result: he proved (1936) that there exist well-defined mathematical questions no algorithm can decide, formalizing the very notion of "computation." Where it applies: computability theory, cryptanalysis, AI, morphogenesis. When: principally 1936–1952.

Alan Turing was an English mathematician whose 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem" introduced a precise, mechanical definition of an algorithm — the Turing Machine — and used it to demonstrate fundamental limits on what can be computed. His work supplied a rigorous answer to David Hilbert's question of whether mathematics is "decidable": it is not. During World War II he led pivotal cryptanalytic work at Bletchley Park, designing the electromechanical Bombe that mechanized the breaking of Enigma. After the war he contributed to early stored-program computer design, proposed the Turing Test as an operational criterion for machine intelligence, and developed a chemical theory of biological pattern formation. A surprising fact: the same 1936 argument that bounded mathematics also defined, decades before working hardware existed, the universal machine — the theoretical ancestor of every general-purpose computer.

The Core Insight

A single, simple, idealized device — reading and writing symbols on a tape according to a finite table of rules — captures everything that can be mechanically computed. From this one abstraction follow both the universality of computers (one machine can simulate any other) and hard limits (some problems have no algorithmic solution at all). Computation, intelligence, and even biological form can be analyzed as rule-governed symbol or state manipulation.

Formal Statement

Turing Machine

A Turing machine is a 7-tuple $M = (Q, Σ, Γ, δ, q_{0}, q_{accept}, q_{reject})$ where:

$Q$ — finite set of internal states,
$Σ$ — finite input alphabet (with blank $⊔ \in / Σ$ ),
$Γ$ — finite tape alphabet, $Σ \subseteq Γ$ , $⊔ \in Γ$ ,
$δ : Q \times Γ \to Q \times Γ \times {L, R}$ — the transition function,
$q_{0} \in Q$ — start state,
$q_{accept}, q_{reject} \in Q$ — halting states.

The machine operates on an infinite tape divided into cells, with a head scanning one cell at a time.

The transition rule applied at each step is:

δ (q, a) = (q^{'}, b, D), D \in {L, R}

⟳read symbol

a

in state

q

, write

b

, move head one cell in direction

D

, enter state

q^{'}

— this is the entire dynamics.

A function $f : N \to N$ is Turing-computable when some machine, started with $n$ encoded on its tape, halts with $f (n)$ written:

M (⟨ n ⟩) ↓ = ⟨ f (n)⟩ for all n

⟳

↓

denotes halting;

⟨ \cdot ⟩

denotes a fixed binary/unary encoding. Computability means halting with the correct output on every input.

Existence of a Universal Turing Machine

There exists a single Turing machine $U$ that, given an encoding $⟨ M ⟩$ of any Turing machine $M$ together with an input $w$ , simulates $M$ on $w$ :

U (⟨ M, w ⟩) = M (w)

⟳encode

M

's transition table as data on

U

's tape;

U

reads the current simulated state and scanned symbol, looks up the encoded rule, and updates the simulated configuration step by step.

Undecidability of the Halting Problem

There is no Turing machine $H$ that decides, for every $⟨ M, w ⟩$ , whether $M$ halts on $w$ . Formally the language

HALT = {⟨ M, w ⟩ : M halts on w}

is not decidable.

⟳the set is recognizable (simulate and accept if it halts) but not decidable — proven by diagonalization below.

A consequence is the negative answer to Hilbert's Entscheidungsproblem:

No algorithm decides validity in first-order logic.

⟳reduce HALT to logical validity — a halting computation can be encoded as a first-order sentence, so deciding validity would decide halting.

Why It Holds / Derivation

Halting Problem is Undecidable — Diagonalization

Step 1. Assume for contradiction a total machine

H

exists with

H (⟨ M, w ⟩) = {accept reject M halts on w otherwise.

Step 2. Build a machine

D

that takes a single input

⟨ M ⟩

and runs

H

⟨ M, ⟨ M ⟩⟩

(machine fed its own description). Then

D

does the opposite of what

H

predicts:

if $H$ says " $M$ halts on $⟨ M ⟩$ ," then $D$ loops forever;
if $H$ says " $M$ does not halt," then $D$ halts.

Step 3. Feed

D

its own description: run

D (⟨ D ⟩)

. Step 4. Consider the two cases:

If $D$ halts on $⟨ D ⟩$ , then by construction $H$ must have predicted "does not halt" — contradiction.
If $D$ loops on $⟨ D ⟩$ , then $H$ predicted "halts" — also contradiction.

Step 5. Both branches are impossible, so

H

cannot exist. Hence HALT is undecidable.

■

Alan Turing | 1912–1954

Born in Maida Vale, London, on 23 June 1912, Turing showed early mathematical brilliance, entering King's College, Cambridge in 1931 and being elected a Fellow at 22 for work on the central limit theorem. His 1936 computability paper, written before he turned 24, redefined the foundations of mathematics. He earned a PhD at Princeton (1938) under Alonzo Church, served as the leading scientific mind at Bletchley Park during the war, and afterward worked on the ACE computer at the National Physical Laboratory and the Manchester Baby/Mark I. Prosecuted in 1952 under Britain's anti-homosexuality laws and subjected to chemical "treatment," he died on 7 June 1954 of cyanide poisoning, ruled a suicide. He received a posthumous royal pardon in 2013.

Building Intuition

Think of a Turing machine as the most patient clerk imaginable: an infinitely long ledger (tape), a pencil, and a tiny rulebook taped to the desk. The clerk reads the current symbol, consults the rule for "(my mood, this symbol)," writes something, shuffles one space left or right, and changes mood. Nothing else is allowed — no intuition, no creativity, no memory beyond the current mood and the marks on the ledger. The astonishing claim (the Church–Turing thesis) is that anything any human or machine could ever compute by a definite procedure can be done by this clerk. The universal machine is then a clerk whose ledger contains a description of another clerk's rulebook — software running on hardware. And the halting argument shows that no clerk, however clever the rulebook, can reliably foresee whether an arbitrary fellow clerk will ever finish.

A Turing machine: finite control reading and writing a symbol on the tape

Worked Examples

A Turing machine that increments a unary number

Given: a number

n

represented in unary as

n

consecutive 1's, e.g.

n = 3 \mapsto 111

. We want a machine that outputs

n + 1

(i.e.

1111

). Construction. States

Q = {q_{0}, q_{accept}}

, alphabet

Γ = {1, ⊔}

. Start at the leftmost 1.

$δ (q_{0}, 1) = (q_{0}, 1, R)$ — scan right across all 1's.
$δ (q_{0}, ⊔) = (q_{accept}, 1, R)$ — at the first blank, write a 1 and accept.

Trace for $n = 3$ (tape $111$ ):

$q_{0}$ reads 1, move R (×3 times), now scanning the blank after the last 1.
$q_{0}$ reads $⊔$ : write 1, enter $q_{accept}$ .

Tape now reads $1111$ .

Number of steps:

n + 1 = 4

transitions.

Output = 1111 = (3 + 1) in unary, steps = 4

Counting the configurations of a small machine

Given: a Turing machine with

∣ Q ∣ = 5

states and tape alphabet

∣Γ∣ = 3

, restricted to a tape window of

L = 10

cells. How many distinct configurations (instantaneous descriptions) exist? Reasoning. A configuration is specified by:

the current state: $∣ Q ∣ = 5$ choices,
the head position: $L = 10$ choices,
the tape contents over $L$ cells: $∣Γ ∣^{L} = 3^{10}$ choices.

Configurations = ∣ Q ∣ \cdot L \cdot ∣Γ ∣^{L} = 5 \cdot 10 \cdot 3^{10} .

Compute:

3^{10} = 59049

, so

5 \cdot 10 \cdot 59049 = 50 \cdot 59049 = 2, 952, 450

# configurations = 2, 952, 450

Interpretation: if the machine runs longer than this many steps without halting on this bounded tape, it must have repeated a configuration and is therefore looping — a finite, decidable check for bounded space, in sharp contrast to the unbounded halting problem.

Common Misconceptions

"Turing proved that some math problems are too hard for computers — meaning they need more time/memory." No. Undecidability is not about resources; HALT cannot be solved by any algorithm with any finite amount of time or memory. It is a logical impossibility, distinct from the complexity questions (like P vs NP) about how much time a solvable problem needs. "The Turing Test defines what intelligence is." Turing proposed the imitation game as an operational replacement for the vague question "can machines think?" — a behavioral criterion, deliberately sidestepping metaphysics. It is a practical test, not a definition of consciousness or understanding, as Searle's Chinese Room argument later stressed.

One might hope that every function with a clear definition is computable. The Busy Beaver function $Σ (n)$ — the maximum number of 1's a halting $n$ -state Turing machine can print — is perfectly well-defined yet not computable. If we could compute $Σ (n)$ , we could solve the halting problem (run each $n$ -state machine for at most $Σ (n)$ -related bounds and detect non-halting), which is impossible. $Σ (n)$ also grows faster than any computable function. This is a concrete, finite-flavored function that defeats all algorithms.

Connections

Turing's machine is provably equivalent in power to Alonzo Church's Lambda Calculus and to Kurt Gödel's General Recursive Functions — the convergence of these independent formalisms is the empirical backbone of the Church–Turing Thesis. The undecidability of HALT is the computational mirror of Gödel's Incompleteness Theorems: both use diagonalization to expose limits of formal systems. Turing's hierarchy of oracle machines launched Computability Theory and the study of Turing Degrees, while bounding the time of computable problems leads into Computational Complexity Theory and the P versus NP Problem.

Real-World Applications

General-purpose computers. The universal Turing machine is the conceptual blueprint for the stored-program architecture — code and data sharing memory — realized in von Neumann machines and every modern CPU.
Cryptanalysis at Bletchley Park. Turing's Bombe mechanized the search for Enigma settings; his statistical method Banburismus applied sequential analysis to naval Enigma, materially shortening WWII.
Compiler and program-analysis limits. Rice's theorem (a generalization of Turing's result) shows no compiler can perfectly decide all nontrivial semantic properties (e.g., "does this program ever crash?") — automated verification is fundamentally bounded.
Artificial intelligence benchmarks. The Turing Test framed decades of AI research and inspires modern conversational-agent evaluation.
Mathematical biology / morphogenesis. Turing's 1952 reaction–diffusion model explains animal coat patterns (spots, stripes) and is used in developmental biology and pattern-formation chemistry.
Cryptographic security proofs. The notion of a computable (and efficiently computable) adversary, rooted in the Turing model, underpins modern definitions of security.
Formal verification & undecidability awareness. Static analyzers, type checkers, and theorem provers are designed around what is and isn't decidable, a direct legacy of Turing's boundary results.

Historical Development

1928 — David Hilbert poses the Entscheidungsproblem: is there a procedure to decide the truth of any mathematical statement?
1931 — Kurt Gödel proves his incompleteness theorems, showing no consistent rich formal system can prove all truths about arithmetic.
1936 — Turing publishes "On Computable Numbers," defining the Turing machine and proving the Entscheidungsproblem unsolvable; Alonzo Church independently reaches the same conclusion via lambda calculus.
1938 — Turing completes his Princeton PhD under Church, introducing oracle machines and relative computability.
1939–1942 — At Bletchley Park, Turing designs the Bombe and develops Banburismus to break naval Enigma.
1945–1948 — Turing writes the design report for the ACE stored-program computer at the National Physical Laboratory.
1950 — "Computing Machinery and Intelligence" introduces the imitation game (Turing Test) in the journal Mind.
1952 — Turing publishes "The Chemical Basis of Morphogenesis," founding mathematical biology of pattern formation.
1954 — Turing dies on 7 June; he is later honored by the ACM Turing Award (1966, computing's highest prize) and a UK royal pardon (2013).

Subtleties & Limits

The Church–Turing thesis is a definition-grade conjecture, not a theorem: it asserts that "effectively computable" equals "Turing-computable," but "effectively computable" is informal, so it cannot be proved — only supported by the equivalence of all known models. Two live frontiers extend it. The physical Church–Turing thesis asks whether physically realizable processes (quantum computers, relativistic or analog devices, hypothetical hypercomputation) could compute non-Turing-computable functions; this remains open and tied to deep physics. Separately, while what is computable is settled, how efficiently is not — the P versus NP problem, the central open question of complexity theory, asks whether every efficiently checkable problem is efficiently solvable, and remains unresolved.