In honor of Alan Turing's 104th birthday Chris Bernhardt, author of Turing's Vision: The Birth of Computer Science, discusses the pioneer's groundbreaking research paper and how it shaped modern computing.
On June 23, 1912, one of the founders of computer science, Alan Turing was born. He is now famous, having been portrayed on stage by Derek Jacobi and in film by Benedict Cumberbatch. He is well known for his work during the Second World War on code breaking that was pivotal in the Allied powers’ victory, and also for his test to determine whether human intelligence is distinguishable from that of machine intelligence. We all know of his arrest and prosecution for being gay, and for the chemical castration that followed, and we know of his tragic death by cyanide poisoning. But not many people outside of computer science are aware of the groundbreaking paper he published in 1936.
This paper, with the somewhat uninviting title, On Computable Numbers with an Application to the Entscheidungsproblem, is now recognized as one of the foundations of theoretical computer science. Indeed, it is one of the reasons that computer science became a separate discipline. This paper is without question Turing’s most important intellectual achievement, and is why the highest award in computer science is named after him.
At the turn of the twentieth century, the great German mathematician David Hilbert gave a list of what he considered the most important mathematical problems for the upcoming century. These problems had a significant influence on mathematics. If you could solve one of them, your future in mathematics was certain. You would become famous—at least in mathematical circles!
In 1935, after Turing finished his undergraduate degree in mathematics at Cambridge University, he was elected as a Fellow—a research position. Turing was young and ambitious. He wanted to tackle an important problem and make a name for himself. A few years before, Hilbert stated his Entscheidungsproblem. The actual problem is a little technical. He was asking for an algorithm that takes certain logical statements as input and tells whether the statement is universally valid. Turing, among others, did not believe that such an algorithm could be found. He believed that Hilbert’s view of algorithms was wrong—that the power of algorithms was much more limited. He set out to prove this.
Unknown at the time to Turing, the established Princeton logician Alonzo Church was also tackling the same problem. Both Church and Turing succeeded in showing that no algorithm could solve the Entscheidungsproblem. Unfortunately for Turing, Church published first.
However, all was not lost. They had tackled the problem in completely different ways. To begin their proofs both Church and Turing had to give a formal definition of algorithm. Algorithms have always been used in mathematics, but if you are going to prove things about them, then you need to have a precise definition of exactly what they are. Church was a logician and his definition involved a formal logical system. It was complicated. The great logician Kurt Gödel studied Church’s definition and wasn’t entirely persuaded that it was correct. Turing, on the other hand, approached the problem in a startling simple and original way. Gödel was thoroughly convinced that Turing was correct. (Turing showed that his definition of algorithm was equivalent to that of Church, and so Gödel realized that Church had also been right.) Turing’s paper was published not so much for the result as for the brilliant ideas he used to obtain it.
At that time, computers referred to people who did computations, not machines. Turing analyzed what computers did step by step. In this way he broke computations down to their atomic components. He then showed that each of these basic steps could be performed by a theoretical machine; a machine that we now call a Turing machine. He gave a convincing argument that given any algorithm, a Turing machine can be designed that will carry out the algorithm. This meant that algorithms could be defined as computations carried out by Turing machines.
Once Turing machines were defined, he showed that it was possible to construct one machine that could emulate any other Turing machine. You don’t need different machines for different algorithms. One suffices. This universal machine could carry out any algorithm. It was here that Turing invented the stored-program concept—that programs could be stored in memory—an idea that would be important in the design of the modern computer.
Turing then went on to consider the limitations of computers. He first defined computable numbers. These are numbers that can be generated by algorithms. Computable numbers include all of the whole numbers and fractions—the rational numbers. They also include certain irrational numbers like the square root of 2, pi and e. He proved that there was a way of pairing computable numbers with whole numbers in such a way that each computable number was partnered with a unique whole number and, conversely, each whole number was partnered with a unique computable number. He then borrowed a clever argument from Georg Cantor to show that although there were ways of pairing the computable numbers with the whole numbers, there was no way that a computer can find a pairing—there is no algorithm for this. Arguing along these lines he was able to prove that there was also no algorithm for Hilbert’s Entscheidungsproblem.
Machines for computing have a long history. Pascal, Leibniz, and Babbage all designed physical machines. Turing, in this paper, was doing something different. He was designing theoretical machines, not plans for physical machines. He was interested in what could be computed and what questions were beyond any computer’s power to address. However, von Neumann, in the 1940s, realized that the stored-program concept was a powerful idea that needed to be incorporated in actual machines. Von Neumann was a leading mathematician of the time. He was also involved in the development of the hydrogen bomb, and that involved large computations that were beyond the ability of human computers. Though he was interested in the theory, he also wanted actual computers to be built. His influence ensured that the stored-program concept would be incorporated in the design of all subsequent computers.
These ideas now seem familiar. Modern computers are universal Turing machines. They run programs that are stored in memory. We all now know the power of computers, but not many of us truly understand their limitations. Turing did. It’s all there in his great paper of 1936.