Alan Turing

Alan Turing

Mathematician, cryptanalyst and computing researcher · 1912–1954 · United Kingdom

Turing's work makes a precise distinction between a machine's individual execution and a method that answers questions about every possible execution. The same career also includes practical cryptanalysis, computer design and mathematical models of biological pattern formation. Each contribution has its own evidence and limits.

A documented career

Born in London in 1912, Turing studied at Cambridge and became a King's College fellow in 1935. After his work on computability, he completed a Princeton doctorate under Alonzo Church in 1938. During the war he worked at Bletchley Park; afterward he designed the ACE at the National Physical Laboratory and moved to Manchester in 1948. These projects involved many other researchers and engineers. A single line from mathematical paper to every later computer is an inadequate engineering history. Andrew Hodges's scholarly biography.

Turing was convicted in 1952 for a sexual relationship with another man and subjected to hormonal treatment as a condition of probation. He died of cyanide poisoning in 1954; the inquest returned a suicide verdict. The persecution is documented. Speculation about his final thoughts or a symbolic poisoned apple should not be presented as established fact. His ongoing scientific work also resists the simplistic account that he ceased to function intellectually after prosecution.

What a machine model specifies

A Turing machine has a finite description: a finite set of states, a finite alphabet, and rules that inspect the scanned symbol, write a symbol, move the head and select a next state. Its tape is unbounded in the mathematical model, although any finite execution visits only finitely many cells. Actual hardware has finite resources.

Turing's 1936–37 paper analyzed effective calculation and the decision problem for first-order logic. It introduced a universal machine that interprets descriptions of other machines. Its original undecidability arguments concern, among other things, whether a machine produces infinitely many output figures and whether it ever prints a designated symbol. The familiar modern halting proof is closely related but should not be represented as a verbatim version of his historical argument. Original paper, sections 1–2, 6 and 8–11.

Formal equivalence between machine models is a theorem. Identifying these models with every effective symbolic procedure is a thesis about the informal notion of procedure. Neither licenses an unsupported claim that a theorem about Turing machines has settled every conceivable question about physical law or consciousness.

Worked mechanism: unary increment

Here is an original teaching machine, not Turing's historical example. A nonnegative integer n is encoded by n consecutive 1s followed by a blank. The head starts on the first 1, or on the blank when n = 0. In state S, reading 1 means leave it unchanged, move right and stay in S. Reading blank means write 1 and enter halt state H without moving.

Step	Relevant tape	Head position	State
0	111 blank	0	S
1	111 blank	1	S
2	111 blank	2	S
3	111 blank	3	S
4	1111 blank	3	H

The invariant is that scanned 1s remain unchanged and the head advances toward the first blank. With the stipulated finite input, a blank is reached after n moves. One additional transition writes the increment. The proof depends on the input convention; an infinite tape of 1s would not satisfy it.

Why a universal termination checker fails

Assume H(p,x) is a program that always halts and correctly reports whether program p halts on input x. Construct D(p): run H(p,p), then loop forever if the answer is yes, and halt if it is no. D has a finite program description d. If H(d,d) says yes, D(d) loops; if it says no, D(d) halts. Either case contradicts H's promised correctness.

This does not prove that no particular termination question can be answered. Unary increment has a straightforward proof. Bounded model checking, type systems and proof assistants can establish many useful properties by restricting programs, accepting incompleteness, or using human-supplied invariants. The impossible combination is automatic termination decision, correctness and termination of the checker for every unrestricted program and input.

Cryptanalysis and experimental questions

Turing's work on the British Bombe used relationships between guessed plaintext, or cribs, and encrypted messages to eliminate inconsistent Enigma settings. Gordon Welchman's diagonal-board improvement, earlier Polish cryptanalysis, engineering teams and operators were crucial parts of the history. Bombes were electromechanical search devices; Colossus addressed a different cipher system. Exact statements that one researcher shortened the war by a specified number of years are counterfactual judgments, not measured results. Bombe reconstruction guide, museum account.

In his 1950 paper Turing replaced an underspecified question about thinking with an imitation-game discussion and considered objections and learning machines. He offered arguments and experimental proposals, not a mathematical proof that conversational success establishes consciousness. Tests need a protocol: who judges, for how long, with what information, and against which comparison group. Computing Machinery and Intelligence.

A second worked mechanism: diffusion can destabilize

Turing's 1952 paper showed how interacting, diffusing substances can amplify spatial disturbances under particular conditions. It did not prove that every stripe or embryonic structure follows one mechanism. The Chemical Basis of Morphogenesis.

Consider an original linear teaching example with two chemical deviations u and v. Local reactions have matrix J = [[1,−2],[2,−3]]. Its trace is −2 and determinant 1, so both eigenvalues are −1 and small local disturbances decay. For two coupled cells, suppose diffusion rates are 0.1 for u and 2 for v. An antisymmetric disturbance has opposite signs in the cells, giving effective matrix J−2D = [[0.8,−2],[2,−7]]. Its determinant is −1.6, so one eigenvalue is positive: a spatial difference can grow even though an isolated cell is stable.

These are dimensionless illustrative coefficients, not measured biology. Linear growth describes the onset of instability. Nonlinear effects, boundary conditions and experimentally identified substances are needed to explain an actual mature pattern.

Exercises

1. Trace unary increment for n = 0 and n = 2. State an invariant and a decreasing quantity that prove termination for every valid input. Explain why testing ten inputs is weaker than this proof.
2. Someone proposes a halting checker that simulates a program for one million steps and returns “never halts” if it has not stopped. Construct a counterexample. Then explain which assumption in the diagonal argument is avoided by a checker allowed to answer “unknown.”
3. Keep J above but give both substances diffusion rate 0.5. Compute the antisymmetric matrix, trace and determinant. Does diffusion create the same instability? Explain why neither calculation by itself proves the origin of a real animal's markings.

Compare your reasoning with the worked solutions

1. For zero, S reads a blank immediately, writes one 1 and halts in one transition. For two, it crosses positions 0 and 1, then writes 1 at position 2 and halts in three transitions. The unchanged input prefix is an invariant. The number of input 1s remaining before the first blank decreases with each move and cannot decrease forever. One final transition completes the operation. Finite tests show only those executions; the invariant argument covers every valid finite n.

2. A program that performs 1,000,001 counted iterations before halting defeats the proposed timeout rule, with its loop arranged so each iteration requires at least one simulated step. A timeout is a resource limit, not evidence of nontermination. A three-answer checker avoids promising a correct yes/no answer on every input. It can be sound on the answers it supplies while leaving difficult cases unresolved; the assumed total Boolean decider H is absent.

3. The new matrix is J−I = [[0,−2],[2,−4]], with trace −4 and determinant 4. Its eigenvalues are both −2, so antisymmetric disturbances decay; there is no corresponding diffusion-driven instability. The earlier calculation required unequal rates and suitable reaction coupling. Both are local mathematical models, lacking empirical identification of chemicals, realistic geometry, nonlinear saturation and experimental perturbation tests. Matching an attractive pattern is not enough to establish its biological cause.