The Universal Machine

In 1936 a twenty-three-year-old Cambridge mathematician answered a question about the foundations of logic, and in the process described a machine.

It has an endless paper tape, a head that reads and writes one symbol at a time, and a table of rules. That is all. Every computer you have ever used is a version of it.

Three years later he was applying the same mind to a cipher with a hundred and fifty-nine million million million possible settings.

Sixteen years after that, his own government prosecuted him for being gay.

In 1928 David Hilbert asked whether there is a definite procedure that could take any mathematical statement and decide whether it follows from the axioms.

It sounds like a question about mathematics. It is really a question about machinery: is there a method, a set of mechanical steps, that always terminates with the right answer?

To prove that no such method exists, you first have to say exactly what a method is. Nobody had.

Turing’s answer was to invent the simplest possible machine that could carry out any method at all, and then show that there are things it cannot do.

Turing was born in London in 1912 and educated at a school that disapproved of his interest in science.

He went to King’s College, Cambridge, and was elected a Fellow at twenty-two on the strength of a dissertation in probability theory.

He was a serious athlete, running marathon distances at close to Olympic standard, and used to run the sixty-odd kilometres to London for meetings rather than take the train.

He was also gay, which under British law at the time was a criminal offence punishable by imprisonment.

Here is the machine. A tape divided into squares, a head sitting over one square, and a table of instructions.

At each tick the head reads the symbol under it. Depending on that symbol and the machine’s current state, it writes a symbol, moves one square left or right, and switches to a new state.

That is the whole specification. There is nothing else in it.

Turing argued that anything a human being could do by following a fixed procedure, this machine can do too. Press the buttons and run one.

Two things follow, and they are the foundations of computing.

First: you can write a machine’s rule table onto a tape as data, and build a single machine that reads that description and behaves exactly like the machine described. One machine that can be any machine. That is a computer, and the description is software.

Second: there is no machine that can look at any program and say whether it will eventually stop.

Suppose there were. Then you could build a program that asks the oracle about itself and does the opposite: halts if told it loops, loops if told it halts. It cannot exist.

And that answers Hilbert. No procedure decides every mathematical question.

Turing reported to Bletchley Park the day after Britain declared war.

Enigma looks like a typewriter. Press a key and current runs through a plugboard, three rotating wheels and a reflector, and back out to light a lamp with a different letter.

After every single keystroke a rotor steps, so pressing the same key twice gives two different letters. That is what makes it strong.

But the reflector that makes decryption easy also guarantees that no letter is ever enciphered as itself. Press the keys and watch.

That one guarantee is the crack the whole attack goes through.

Count the settings. Three rotors chosen from five and placed in order: sixty ways. Each rotor can start at any of twenty-six positions: seventeen and a half thousand combinations.

And the plugboard, which swaps ten pairs of letters before and after the rotors, has about a hundred and fifty million million arrangements.

Multiply: roughly one and a half times ten to the twenty. Trying them all is not an option, and the settings changed every midnight.

It is also worth saying clearly that Britain did not start from nothing. Polish cryptanalysts, led by Marian Rejewski, had been breaking Enigma since 1932 and handed over everything they had in July 1939.

The attack starts with a guess. German operators were disciplined and predictable: weather reports, formulaic greetings, the same opening words.

So you assume a stretch of known text, a crib, sits at a particular place in the message. Because no letter can encipher to itself, most alignments are instantly impossible — that alone eliminates a lot.

Then you follow the chain. If this letter maps to that one at this rotor position, then the plugboard must connect those two, which forces another connection, which forces another.

Go round a loop in the chain and you often arrive back at a contradiction. The Bombe is a machine for spinning through rotor positions and detecting those contradictions electrically — about twenty settings a second, per drum bank.

Run it and watch the possibilities collapse.

Turing led Hut 8, the section attacking naval Enigma — the hardest variant, used by the U-boats that were sinking the convoys keeping Britain fed.

Alongside the Bombe he invented Banburismus, a statistical method for ranking which rotor orders were worth testing, which saved an enormous amount of machine time.

Thousands of people worked at Bletchley, the majority of them women operating the machines and processing the traffic, and every one of them was bound to silence.

Estimates of how much the work shortened the war vary, with two to four years commonly cited. It stayed secret until the 1970s, so Turing got no public credit while he was alive.

After the war Turing designed the Automatic Computing Engine, one of the first complete designs for a stored-program computer — the universal machine, in hardware.

The project moved slowly, and he left for Manchester, where one of the first working stored-program machines was running by 1948.

He wrote some of the earliest programs, worked on a chess-playing routine before there was a machine fast enough to run it, and started asking a question that nobody had asked carefully.

If a machine can imitate any machine, can it imitate a mind?

In 1950 Turing published a paper asking whether machines can think, and then refused to answer it, on the grounds that the question is too vague to be useful.

He replaced it with a game. A judge holds a typed conversation with two hidden participants, one human and one machine, and has to say which is which. If the machine is not reliably identified, then arguing about whether it really thinks is a matter of definition.

He also predicted that by the end of the century people would casually talk about machines thinking without expecting to be contradicted.

He was right about that, and the paper is still where the argument starts.

In January 1952 Turing’s house was burgled. He reported it, and in the course of the investigation told the police, straightforwardly, that he had been in a relationship with a man.

He was charged with gross indecency under an 1885 statute, convicted, and given a choice between prison and hormone treatment designed to suppress libido. He took the treatment.

He lost his security clearance and his consultancy with the government, and was barred from the United States.

In the same year he published a paper showing how two reacting, diffusing chemicals can spontaneously generate spots and stripes — a founding document of mathematical biology.

On the eighth of June 1954 he was found dead at home. The inquest recorded suicide by cyanide poisoning. He was forty-one.

Almost everything in the 1936 paper is still load-bearing.

Your phone is a universal machine. The apps are machine descriptions written as data. The halting problem is why no tool can perfectly tell you whether your program will hang, and it generalises to a wide class of questions about software that cannot be answered in general.

His last paper, on how reacting chemicals generate patterns, is now used to explain the spots on a leopard and the spacing of fingers.

In 2009 the British government apologised. In 2013 he received a royal pardon. In 2017 the law that pardoned tens of thousands of other men was named after him.

Turing worked for about eighteen years and changed the shape of the twentieth century twice: once in logic, once in a wooden hut nobody could talk about.

The secrecy meant he could not be publicly credited for the war work. The law meant that the same state he had served prosecuted him for his private life, and the treatment he accepted to avoid prison was a chemical punishment.

He died at forty-one.

The chapter stills in this film are AI-generated. The photograph of Turing, the Enigma machine and the rebuilt Bombe are real. Sources are listed below.