June 15, 2020
In 1940 and 1941, German U-boats were decimating Allied supply ships. Thousands of merchant navy vessels were lost during World War Two, and Winston Churchill was to later pen the words: “The only thing that ever really frightened me during the war was the U-boat peril.”
By 1943 the tide had turned – Alan Turing had developed the Naval Bombe, an adaptation of his decryption Bombe device capable of laying bare the secrets of the complex German Naval Enigma. Churchill would later comment that Turing had made the single biggest contribution to Allied victory in the war.
The complexity of the German Enigma – an electromagnetic machine that replaced plain text letters with random letters chosen according to the settings of a series of rotors – lay in the fact that its inner elements could be set in billions of different combinations, meaning it would be virtually impossible to decode text without knowing the original settings. As the war progressed, the German military added more rotors to the machine, making it even more complex.
The Polish Cipher Bureau managed to get hold of an Enigma machine and develop an early prototype of the Bombe. They passed their knowledge on to British intelligence. Turing and his colleague Gordon Welchman built on the Polish machine at Bletchley Park. The machine replicated the rotors of the Enigma and would search through different combinations of rotor positions in order to test potential ciphers.
Turing cracked the system by focusing on the idea of the “crib”. The encrypted German messages often contained predictable words, including the full names and titles of military officers, at the same point in each message. The Enigma would never encipher a letter to itself, therefore Turing could use these terms, or “crib” as a starting point, looking out for where the same letter in a possible crib appeared in the same place in its ciphertext counterpart – much like a codeword puzzle. The machine would automatically search through the possible positions of the Enigma’s wheels, eliminating those combinations ruled out by the crib. Once the mathematical cycle of the rotors relating to the crib was found, it could be used to decipher the rest of the text.
Turing’s design relied heavily on cribs, and it was the follow-up machines developed by peer Gordon Welchman and others that would speed up the process as the war progressed.
__ At the tail-end of World War Two, Turing headed to the country and MI6 research centre Hanslope Park, not far from Bletchley Park. Here, he said, he was “building a brain”; a system so advanced it could calculate entire mathematical scenarios for researchers, rather than aid with the odd equation.
His accurate assumption would lead to a paper on the ACE (Automatic Computing Engine) being put to the National Physical Laboratory (NPL) Executive Committee in 1945, which was cast aside for being too complex and having an estimated cost of ₤11,200.
The team at the NPL instead set about building a smaller version of the complex series of circuits Turing presented, which was put into action only on 10 May, 1950. By this time, Turing had left the NPL and was already working on another computer at Manchester University, Manchester Mark 1. The Pilot Model ACE would be the first electronic computer and one of a handful of stored-program computers to be built in Britain.
It was the fastest computer in the world at the time, despite clocking in at what would today be considered a 1 MHz snail’s-pace. Its memory functioned off mercury delay lines, with each one capable of storing data of up to 32 bits. Thirty Pilot Models were sold, but by 1958 the full-sized model had been built. The basic design of Turing’s ACE would be put to use in the MOSAIC (Ministry of Supply Automatic Integrator and Computer), used to calculate aircraft movements during the Cold War. It was also the basis of the Bendix G-15, considered the first personal computer, which was for sale up until 1970.
Despite perhaps being most well-known today for his contributions to codebreaking, no less important are Turing’s insights into the concept of the Turing machine and universal computability. Without going into too much detail, Turing proposed (in collaboration with his doctoral supervisor Alonzo Church) a hypothetical machine (in 1936) that could be used to simulate any algorithmic computation. More of a thought experiment than something that could be constructed in real life, the Turing machine would be fed by a long piece of tape on which would be written single-character instructions. The machine could read each instruction one at a time, process it according to some predetermined coded algorithm, and then move the tape back or forwards as necessary.
This was groundbreaking in the sense that it was the first proposal for a machine with multiple functions determined by a program held within a memory store, rather than by physically altering the machine’s wiring or structure. Turing machines are still used today in computer science as a research and teaching tool, as it’s a simple way to model what happens in a CPU. Turing and Church together hypothesised the idea of a universal Turing machine, a machine which could read and perform any algorithmic function – that is, a Turing machine that can simulate the algorithmic functions of any other Turing machine. “Turing completeness” is now one of the defining features of modern computers; the only practical limit on a machine’s Turing-completeness is the amount of memory it has.
The first fully digital electronic Turing-complete computer was the US ENIAC in 1946 – however (and rather amazingly) Charles Babbage’s Analytical Engine, first described in 1837 but never built, would theoretically have been Turing-complete.
Turing-completeness has several wide-ranging philosophical ramifications, too – much of the philosophy of the mind over the past few decades has been influences by Turing’s ideas.
Turing’s cracking of the Enigma code wasn’t his only technological breakthrough at Bletchley Park. He also developed a method of securely encoding and decoding telephone conversations in 1944, building on work he had seen at Bell Labs in the US in 1942. Named “Delilah”, it was never used by the government, but Turing fed some of his work back to Bell Labs as they developed SIGSALY – a device which was the first to use many digitally secure speech concepts, and which was used for the most secretive Allied communications.
__ Though he was only just beginning to publish on the subject by the time of his death in 1954 (and it was not until the 1990s that much of his work was finally published), Turing’s contributions to morphogenesis are still relevant to the field today. Morphogenesis is the process by which multi-celled life develops its shape as it grows, and Turing’s 1951 paper The Chemical Basis of Morphogenesis explored how non-uniform biological characteristics (like stripes on a zebra) could arise out of a uniform starting state in the womb. Turing was fascinated his entire life by the structure of plant petals and seeds (phyllotaxis), and how they seemed to adhere to the Fibonacci sequence – especially when it came to sunflowers. You can help complete his unfinished research on this with the Turing’s Sunflowers project, which aims to crowdsource growing thousands of sunflowers around the country in 2012 so we can prove Turing’s thesis once and for all.
Chemistry and physics
Turing’s work on morphogenesis also has applications in chemistry and physics. He was among the first to notice that chemical systems that are otherwise stable become unsettled by diffusion under certain circumstances – in these “reaction-diffusion” systems, diffusion clashes with individual chemical reactions leading to the apparent paradox of the overall system getting more complicated over time. The same process that might lead to spots and patterns on animals also works on the molecular level, and some consider Turing’s work on reaction-diffusion systems to be one of the earliest forays into the field of chaos theory.
Chess computer program
In 1950, Turing wrote the first ever chess computer program as part of his work on artificial intelligence. Calling it “Turbochamp”, he tried to implement it on Manchester University’s Ferranti Mark I without success. Instead, in the summer of 1952, he “played” as the program against his friend and colleague Alick Glennie. Turing would work through each move according to his program on paper, taking around half an hour each time. While it showed that Turbochamp was capable of playing a human at chess, it lost against Glennie in 29 moves. You can watch the game here. It was 1957 before a fully-operational chess program was up and running, created by Alex Bernstein at IBM on an IBM 704.