[Alan Turing's admission photo at Princeton University]

Alan Turing is considered by many the father of modern computer science. There are many reasons for this, but the big points in his history were the construction of computability theory, his dream of human-like artificial intelligence, and his role in breaking the German Enigma codes in World War II.

His story ended in tragedy and self-harm, but his life is remembered as one of heroism, and British society has progressed in his name to prevent further tragedy, as we'll get to at the end of this lesson.

Turing was born in 1912, in London, and would go on to his education at Sherborne School. In his youth, Turing was often discouraged by his classes. The school system in this part of Britain was a strict and rigid system with little opening for creativity. As a result, he often would seek out new things to learn that were off the beaten path of his expected education, figuring out such concepts as Einstein's relativity while still a teenager. This, and his thoughts on the nature of consciousness, would drive his studies and curiosity for the rest of his life.

During his time in Cambridge, he gained a Fellowship at age 22, being very well respected in the field of pure mathematics. A short time later, in 1936, he constructed the first formal description of a universal computer, what is now considered to be a "Turing machine." This is a device with a memory on a "tape" of arbitrary length, and instructions that are performed based on the current symbols on the current position of the tape. These instructions could move the "head" along the tape, write a symbol to the tape, and read from the tape, and had rules about which instruction set to switch to depending on the symbol currently under the head when the instructions end. There were also instructions to "halt" and thus stop running the program. This general computer can theoretically do anything that any ordinary digital computer can do.

[An attempt at a physical Turing machine by Mike Davey, 2010.]

In the same paper, Turing explained that there were certain things that could never be decided by any means, and these problems were thus "incomputable." These problems could be reduced to a simple question: how do you devise a program that can test any other general program, and determine for a given input if that program will halt, or will run forever?

If it's possible to create such a program, it's possible to make one that works in a strange, "opposite" fashion, such that if the program being tested halts, the test program runs forever, and vice versa. But what then happens if you run that program on itself as input? If the program would halt, it testing its own code as input would run forever, and vice versa, but that's impossible because it can't both halt and run forever on the same input! Because of this, it's impossible to make a program that can test all programs ever to see if they halt or run forever on a given input. Thus, some problems, like the halting problem, can never be decided by computation.

After producing these wonders for mathematics (and what would later be called Computer Science), and going through a rapid graduate student program at Princeton University in New Jersey, Turing went on to help the war effort against the German Enigma cryptograms. Using a physical model Polish efforts had seized and analyzed, Turing and his team put together an electro-mechanical computer to break it. The Enigma machine was based on a set of wired wheels and motors, which would change their positions every time a new letter was entered. The letter entered at the end depends both on the letter the operator typed and the positions of the wheels, and a key sequence would determine the starting position of those wheels.

[British Bombe replica in Bletchley Park Museum, Bletchley, Milton Keynes, UK, date and photographer unknown]

The Enigma device used three wheels to achieve this, with a later version adding a fourth wheel when the Germans realized their original cipher had been cracked. The cryptanalysis machine Turing designed determined the key based off of known "crib" sequences placed in certain messages, which could be guessed if the message content were known. Because of this, it needed a much larger number of wheels, as seen above. The keys were identical for all messages sent by a given force during a given day. The British codename for the device was the Bombe, a nod to the earlier Polish device, the Bomba, which used a different approach to breaking Enigma that had since become obsolete.

There were multiple Bombe machines constructed or modified over time, some to aid in breaking more codes in parallel, others being upgraded to help break more complex versions of the cipher. While many were British, some were American made, as the war effort crossed the Atlantic.

After the war, Turing would go on to invent the first general electronic computer, the Automatic Computing Engine, described in detail in 1946. Following this, in 1950, he would formalize the idea of the "imitation game" to test an artificial intelligence. The goal was to create an AI that human testers could communicate with, and not be able to determine if there was a human on the other end, or an AI. This would be termed the "Turing test," though Alan Turing may have objected to the label.

Unfortunately, his life would be cut short by misguided law. In January of 1952, he released information to police about a robbery, which included an admission that the thief was his boyfriend. Homosexuality was illegal in the UK until 1967, the punishment requiring use of hormone treatments that caused sterility in men. Turing committed suicide in 1954, likely as a result of the emotional pain resulting from this.

It took until 2013 for Alan Turing to be posthumously pardoned by Queen Elizabeth, over 60 years after his conviction of a "crime" that had no reality in modern law or society. Three years later, in 2016, the British government produced "Turing's law" which pardoned thousands of other gay and bisexual men, dead or alive, who were convicted during the time the old law had been in effect.

Sources:

Dr. Andrew Hodges, Alan Turing: Creator of Modern Computing, BBC 2017, Retrieved from http://www.bbc.co.uk/timelines/z8bgr82 on May 19, 2017

Crypto Museum editors, Bombe: Breaking the Enigma cipher, Crypto Museum, 10 Sept 2016, Retrieved from http://www.cryptomuseum.com/crypto/bombe/ on May 19, 2017

Biography.com editors, Alan Turing Biography.com, A&E Television Networks, October 21, 2016, Retrieved from http://www.biography.com/people/alan-turing-9512017 on May 19, 2017

Randal C. Nelson, Undecidability, University of Rochester, Retrieved from https://www.cs.rochester.edu/~nelson/courses/csc_173/computability/undecidable.html on May 19, 2017

Exercise: Quiz Yourself (Turing)

After reading the above history (or reviewing again now), ask yourself the following questions about what you read, and make sure you know how to answer correctly.

1. What was Turing's universal computer description, in brief?

2. What was the advantage of having this universal computer description?

3. What was the consequence of the "halting problem?"

4. What kind of machine did Turing and his team use to break the German Enigma cryptograms? (Not just its name)

5. What method did that cryptanalysis machine use to speed its calculations?

6. What was the name of the British Enigma cracking device?

7. What was the "imitation game" that Turing invented?

8. For what reason was Turing convicted of crime, punished, and later pardoned posthumously over 60 years later? (It has not been a crime in the UK for decades)