What was the imaginary machine Alan Turing described in 1936?

Alan Turing imagined a machine that exists only on paper, and it became the standard model of what a computer does. In 1936, he described what he called an 'a-machine': a device that reads and writes symbols on an endless tape, one cell at a time, following a simple table of rules. Despite how basic that sounds, Turing's model is capable of implementing any computer algorithm: with it, Turing formalised the very ideas of algorithm and computation.

The machine itself has almost no moving parts in the usual sense. It has a tape of cells, each holding a symbol, a head that reads and writes one cell at a time, and a state chosen from a finite list. At every step, it reads the symbol under the head, then, based on that symbol and its current state, writes a new symbol, moves the head one step left or right, or halts. That's the whole mechanism, and it's enough to implement any computer algorithm.

Turing went further: he showed that a single machine could simulate any other Turing machine if you just fed it the right description on the tape. This 'universal machine' is considered by some to have been the fundamental theoretical breakthrough behind the idea of the stored-program computer, where one machine runs whatever program it is given instead of being rebuilt for each task.

Turing didn't just theorize. During World War II his codebreaking helped the Allies decipher Germany's Enigma-encrypted messages, and afterward he designed the Automatic Computing Engine, an early stored-program computer, turning his abstract tape machine into real hardware. But Britain repaid him badly: in 1952, after acknowledging a relationship with another man, he was prosecuted for gross indecency and given probation conditional on chemical castration. He died in 1954, aged 41; the inquest ruled his death a suicide. After a 2009 campaign, the prime minister officially apologised, and a royal pardon followed in 2013.