As part of our (very) occasional series of biographies of mathematicians, we’d like to tell you a bit about the man who did more than anyone to end WWII. Today is the 100th anniversary of Alan Turing‘s birth. His math ability was recognized at an early age (he proved the central limit theorem when he was a student!) and was granted a faculty position at Cambridge when he was just 22.
In 1936 (when he was just 24!) he defined what is now known as the Turing Machine. Nowadays it doesn’t seem like a big deal: it’s a hypothetical machine which has an infinitely long paper tape on which the machine can read or write one symbol at a time on the paper tape. There is a finite alphabet of allowed symbols, a “state register” which stores the current state of the machine (there are finitely many allowed states), and a finite table of “actions” which tell the machine “if you are in this state, then do this next (read/write, move left/right along the paper tape, etc.)”.
In modern language, the paper tape acts as a hard drive, the alphabet is the basic pieces of the machine’s programming language, the state register acts as the machine’s memory, and the table of actions is the operating system.
The point, of course, is that none of these things existed like they do now! Turing was able to envision what exactly was needed as the necessary and sufficient ingredients to build a computer. So much so, he was also able to show that one could make an appropriate choice of alphabet, list of states, and table of actions to create a universal Turing machine (UTM). A UTM is a Turing Machine which can do any possible computation any other Turing Machine is capable of doing. As Turing said in his paper:
It is possible to invent a single machine which can be used to compute any computable sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D [“standard description” of an action table] of some computing machine M, then U will compute the same sequence as M.
— Turing’s 1926 paper.
This is exactly what a modern computer is, a universal Turing Machine! You can program it to do anything you like (do an integral, translate from German to Portuguese, play Cut the Rope, …).
Here’s a real life Turing Machine (sans infinite paper tape, of course) in action:
A programming language is called Turing Complete if it can be used to simulate a universal Turing Machine. That is, you can write any program you like without limit using that language. Amusingly, it was rumored that the reason Apple wouldn’t approve a LaTex app which compiles on your iDevice was because LaTex is Turing Complete. Summer project: write an iOS emulator within LaTex :-).
Why did Turing invent the Turing Machine if they didn’t have the technology to build one?
Because he was interested in the problem of computability. What does it mean to be able to “compute” something? To make that idea precise, Turing invented the Turing Machine. Something was computable if you could create a Turing Machine which could compute it. More specifically, Turing proved that any mathematical computation which could be theoretically done via an algorithm could be done on a Turing Machine.
In 1928 the famous German mathematician David Hilbert had asked about the Entscheidungsproblem (decision problem). the Entscheidungsproblem asked for an algorithm to decide whether a given statement is provable from the axioms using the rules of logic. That is, you input a statement and after some finite amount of time the algorithm spits out a YES or NO answering whether that statement is a theorem in the system of logic.
As we mentioned, Turing proved that anything which could be done by an algorithm could be done on a Turing Machine. He proved that there was no solution to the Entscheidungsproblem by showing that it is not always possible to decide whether a given Turing machine will ever halt.
Turing Machines are a fundamental tool in theoretical computer science. They provide the precise definition for what it means to compute something.
Now of course most mathematicians would be happy to have answered one of Hilbert’s problems and revolutionize/invent a whole new area of study. Not Turing!
During WWII Turing was a leading participant in the breaking of German codes at the British codebreaking group at Bletchley Park. He played an absolutely key role in breaking German codes. Hugh Alexander, the eventual head of Turing’s division wrote:
There should be no question in anyone’s mind that Turing’s work was the biggest factor in Hut 8’s success…. The pioneer’s work always tends to be forgotten when experience and routine later make everything seem easy and many of us in Hut 8 felt that the magnitude of Turing’s contribution was never fully realized by the outside world.
— from Turing’s wikipedia page
He also came up with the famous Turing Test, the LU decomposition of matrices (where you write a matrix as the product of a Lower triangular matrix and an Upper triangular matrix), and numerous other important results.
In 1948 Turing and David Champernowne (inventor of the hysterical Champernowne constant) wrote the first ever chess program. Amusingly, since computers barely existed then, no computer was powerful enough to actually run the program. Undaunted, Turing played a game in which he simulated the computer, taking about half an hour per move. The program lost to Turing’s colleague Alick Glennie. You can see the game here.
Sadly, this story has a tragic end. In 1952 he was convicted of “gross indecency” (ie. being gay) and given the choice between imprisonment or probation along with estrogen treatments designed to reduce libido. He accepted the chemical castration.
The treatment left him miserable and his conviction meant he lost his top secret clearance and job working on cryptography for the British government. Two years later at age 42 he died of cyanide poisoning. Although officially ruled an accident, it’s widely believed to have been a suicide.
Just three years ago the British Prime Minister Gordon Brown finally issued a formal apology for the government’s treatment of Turing.
Sadly, during February of, this, the Alan Turing year, the British government decided against granting a posthumous pardon to Alan Turing.
Radiolab has a wonderful 25 minute podcast about Alan Turing. Check it out here: