January 17, 2012
This year marks the centenary of the birth of Alan M. Turing, a mathematician who created the discipline of computer science, built codebreaking machines that helped win World War II, and first explored the idea of machine intelligence in a systematic way. Turing is the Einstein of computer science, and considering the transformational impact of computing on our society, Turing’s influence on today’s world is every bit as important as that of Albert Einstein.
Yet while Einstein lived to old age, venerated around the world, Turing killed himself in his early 40s after being hounded by the British government for his homosexuality. Turing illuminated the very essence of computation and helped to save civilization from the Nazis; yet society could not allow him to live peacefully and openly as a gay man. What a price to pay for bigotry.
Turing made his mark on the world with his foundational paper, “On Computable Numbers, with an Application to the Entscheidungsproblem,” published in the Proceedings of the London Mathematical Society in 1937. In this paper, Turing said that the following question does not have a solution: Could one reduce logical reasoning to a mechanical process? In other words, could one build a machine of some kind that could mechanically settle the truth or falsehood of mathematical theorems? This is the “Entscheidungsproblem,” or “Decision Problem,” of Turing’s title.
But Turing’s contribution is more significant than the actual result he obtained. (In fact, the American logician Alonzo Church had obtained the same result as Turing a little bit earlier.)
What distinguished Turing’s work was his careful analysis of what it means to “compute” something.
In his paper, he describes a very simple machine, a kind of prototypical computer, and argues carefully that something is “computable” exactly when it can be computed on one of these machines.
In making his definition, Turing found the exact balance between power – so that his machines can, indeed, do any procedure we might reasonably call a computation – and simplicity – so that one can reason abstractly about his machines and establish general results about what can be computed.
Everyone who studies computer science or logic in a formal way now begins with Turing Machines. This definition of computation, and the description of what we now call Turing Machines, was the transformational idea in Turing’s paper.
Following his theoretical contribution, Turing made a crucial practical one. As World War II began, the British government obtained information from the Polish Secret Service about the German cipher machine called Enigma – which was used by all branches of the German military, especially the U-Boats. The British brought together a fascinating assortment of scientists, including Turing, linguists, chess and bridge players, and other polymaths, and gave them the job of breaking the Enigma. Turing built a special purpose computing machine designed to crack the Enigma cipher on an industrial scale. The resulting intelligence, called Ultra, provided a key strategic asset in WWII, especially during the battle of the North Atlantic against the U-Boats.
After the war, Turing continued to blend his theoretical insights into computation with his goal to actually build a working computer. But his third decisive contribution was more philosophical. He published the paper “Computing Machinery and Intelligence” in the journal Mind, asking the question, “Can machines think?” His answer was “yes, eventually,” and he introduced the famous “Turing Test” for determining if a machine has crossed the boundary into intelligence. (While Turing’s Entscheidungs problem paper is technical, his Mind paper is very readable, and a lot of fun.)
A hero of the war; inventor of a new discipline; and a provocative philosopher, Turing should have commanded the respect of the general public and the admiration of the scientific community.
But Turing was gay, and obliged under the social norms of the time to keep that fact quiet. When a man with whom he was having a relationship robbed him, and Turing naively reported the robbery to the police, Turing found himself being prosecuted for indecency. He was required to undergo hormone treatments under the bizarre notion that his sexual orientation could be corrected. Depressed and alone, he killed himself with cyanide in 1954, a few weeks before his 42nd birthday.
Turing’s work, like Einstein’s, is a powerful example of how even the most abstract and theoretical contributions can prove transformational in society. Amidst the constant demands that research be tied to specific economic payoffs, it’s always worth bearing in mind that we need to leave space for the truly new and original, and that we can’t know where the next real breakthrough might come from.
But there’s another lesson I draw from Turing’s life. Our society cannot afford to continue to parse the phrase “equal protection under the law.” We should stand by our belief that each of us enjoys the inalienable right to the pursuit of happiness. We should end all forms of legal discrimination based on sexual preference. That would be a fitting memorial for this “Turing Year.”
To learn more about Alan Turing’s life and work, I recommend Alan Hodges’ biography,Alan Turing: The Enigma. Turing was also portrayed by Derek Jacobi in the play Breaking the Code. For an accessible technical introduction to the theory of computability and its applications in logic, I recommend Martin Davis’s book Computability and Unsolvability.