Alan Turing and the Mathematical Birth of Computing

Before there were electronic computers, a 24-year-old Cambridge mathematician described, on paper, a machine that could carry out any calculation that can be done by following rules. Alan Turing's imaginary machine became the blueprint for every computer that followed, and his later code-breaking work helped shorten the Second World War.

A Restless, Brilliant Student

Alan Mathison Turing was born on 23 June 1912 in Maida Vale, London. His father worked for the Indian Civil Service, and Alan and his brother spent much of their childhood in the care of foster families in England. At Sherborne School his interest in science and mathematics was not always appreciated by teachers who valued the classics.

He studied mathematics at King's College, Cambridge, from 1931, graduated with distinction and was elected a Fellow of King's in 1935, aged 22, for a dissertation proving a version of the central limit theorem in probability, without realising it had already been proved.

The 1936 Paper: What Can Be Computed?

In 1928 David Hilbert had posed the Entscheidungsproblem (decision problem): is there a mechanical procedure that can decide, for any mathematical statement in formal logic, whether it is provable? To answer "no," someone first had to define precisely what a mechanical procedure is.

In his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem," Turing imagined a human "computer" (in those days, a person who calculates) reduced to the simplest possible actions. This became the Turing machine:

• an infinitely long tape divided into cells, each holding a symbol such as 0, 1 or blank;
• a head that reads one cell at a time, writes a symbol and moves one step left or right;
• a finite set of states and a table of rules: "in state \(q\), reading symbol \(s\), write \(s'\), move left or right, and switch to state \(q'\)."

Turing then showed that a single universal machine could imitate any other Turing machine if given a description of it on its tape. This is exactly the idea of a stored-program computer: one machine, many programs.

At almost the same time in Princeton, Alonzo Church reached the same conclusion about the decision problem using a different system, the lambda calculus. The claim that Turing machines capture everything that is effectively computable is now called the Church–Turing thesis. Turing went to Princeton and completed a PhD under Church in 1938.

Worked Example 1: A Turing Machine That Adds 1

Task. The tape holds a binary number with the head on its rightmost digit. Add 1.

Rules (state "carry"):

1. Reading 1: write 0, move left, stay in "carry."
2. Reading 0: write 1, halt.
3. Reading blank: write 1, halt.

Trace on the input 1011 (eleven).

• Head on the last digit, a 1: write 0, move left. Tape: 1010.
• Head on the third digit, a 1: write 0, move left. Tape: 1000.
• Head on the second digit, a 0: write 1, halt. Tape: 1100.

Check: \(1100_2 = 8 + 4 = 12 = 11 + 1\). Correct.

Trace on 111 (seven). Each 1 becomes 0 as the head moves left, giving 000; then the head reads a blank and writes 1, producing 1000. Check: \(1000_2 = 8 = 7 + 1\). Correct.

With such simple tables, Turing machines can perform any algorithm a modern computer can, just much more slowly.

The Halting Problem

Turing then proved that some questions can never be answered by any machine. The halting problem asks: given a program and its input, will it eventually stop or run forever?

The proof is a diagonal argument, inspired by Georg Cantor. Suppose a machine \(H\) could always answer correctly. Build a new machine \(D\) that takes a program \(P\), asks \(H\) whether \(P\) halts when given its own description, and then does the opposite: loops forever if \(H\) says "halts," and halts if \(H\) says "loops." Now ask what \(D\) does when given its own description. If it halts, it must loop; if it loops, it must halt. This contradiction shows \(H\) cannot exist. As a consequence, Hilbert's decision problem has no general solution.

Bletchley Park and Enigma

In September 1939, as war began, Turing reported to Bletchley Park, Britain's code-breaking centre. The German military used the Enigma machine, in which rotating wheels and a plugboard scrambled each letter differently every time a key was pressed.

Polish mathematicians, led by Marian Rejewski, had broken earlier Enigma systems in the 1930s and built a device called the bomba, sharing their work with Britain and France in July 1939. Building on this, Turing designed the British Bombe (with an important improvement by Gordon Welchman), an electromechanical machine that rapidly tested rotor settings against guessed fragments of plaintext called "cribs." More than 200 Bombes were in use by the end of the war. Turing also led Hut 8, which attacked the especially difficult German naval Enigma, vital to the Battle of the Atlantic, and devised the statistical method called Banburismus.

Worked Example 2: How Many Enigma Settings?

Consider the standard army Enigma with 3 rotors chosen from 5 and a plugboard with 10 cables.

Step 1: Rotor order. Choose and arrange 3 of 5 rotors:

$$ 5 \times 4 \times 3 = 60 $$

Step 2: Starting positions. Each rotor has 26 positions:

$$ 26^3 = 17{,}576 $$

Step 3: Plugboard. The number of ways to pair 20 of the 26 letters into 10 unordered pairs is

$$ \frac{26!}{6! \times 10! \times 2^{10}} = 150{,}738{,}274{,}937{,}250 $$

Here \(6!\) accounts for the 6 unplugged letters, \(10!\) for the order of the cables, and \(2^{10}\) for the two ends of each cable.

Step 4: Multiply.

$$ 60 \times 17{,}576 \times 150{,}738{,}274{,}937{,}250 \approx 1.59 \times 10^{20} $$

That is about 159 billion billion settings (more if ring settings are included). Checking a million settings per second would take around 5 million years, which is why brute force was hopeless and Turing's logical shortcuts were essential.

After the War: Computers and Intelligence

In 1945–46, at the National Physical Laboratory, Turing produced a detailed design for the Automatic Computing Engine (ACE), one of the first complete designs of a stored-program computer. In 1948 he moved to the University of Manchester, where he wrote programming manuals for the Ferranti Mark 1, one of the earliest commercial computers.

In 1950 his paper "Computing Machinery and Intelligence" asked, "Can machines think?" He proposed the imitation game, now called the Turing test: if a judge chatting by text cannot reliably tell a machine from a human, we should credit the machine with intelligence. In 1952 he published a pioneering paper on morphogenesis, using differential equations to explain how patterns such as animal stripes and spots might form.

That same year Turing was prosecuted for homosexuality, then a crime in Britain, and accepted chemical castration instead of prison. He died of cyanide poisoning on 7 June 1954 at his home in Wilmslow, aged 41; the inquest ruled suicide, though some have questioned it. In 2009 the British Prime Minister issued a public apology, and in 2013 Turing received a posthumous royal pardon.

Did You Know?

• The Turing Award, often called the Nobel Prize of computing, has been given annually since 1966.
• Turing was an excellent long-distance runner; he recorded a marathon time of 2 hours 46 minutes in 1947.
• Since 2021, Turing's portrait has appeared on the Bank of England £50 note.

Key Takeaways

• Turing's 1936 paper defined computation using the Turing machine and showed a universal machine can run any program.
• The halting problem proves some questions can never be decided by any algorithm.
• At Bletchley Park his Bombe and statistical methods helped break Enigma, building on Polish work.
• He designed the ACE computer, proposed the Turing test and pioneered mathematical biology.

For step-by-step help with discrete mathematics, logic, combinatorics or computing assignments, reach Amathify's subject experts and PhD scholars through WhatsApp or the Ask a Question form.