In 1937, a remarkable paper entitled “On Computable Numbers, with an application to the Entscheidungsproblem,” appeared in the Proceedings of the London Mathematical Society. In it, the author, Alan Turing, a twenty-five-year-old Cambridge mathematician, described a hypothetical machine consisting of only a scanner and a tape. There is nothing special about either component; the tape is divided into boxes, like the frames of a roll of film, each of which could be marked with a symbol or be left blank, and the scanner could read, write, or erase these symbols by moving one box at a time to the left or to the right. A simple device, the Turing machine could do only three things: scan a box and stop; erase a symbol and write a new one; and scan a box and move to the left or to the right.
What’s so extraordinary about all this? Plenty. Even if the symbols on the tape were as simple as a slash (/), the Turing machine could solve almost any logical or mathematical problem. (But not all of them, as we shall see in a moment.) For example, suppose the tape contained two strings of five slashes separated by a blank box; by erasing a slash at the end of one of the strings and writing a slash in the blank box between them, the device could add 5 and 5. By the same token, it could subtract, multiply, and divide – or square a number, divide by three, and subtract 30 if the result exceeded 144. And that’s not all. Since the slashes on the tape can just as easily stand for instructions as numbers, it also could perform conditional jumps, subroutines, loops, and other programming tricks, and thus could control the operation of any device. In short, Turing’s imaginary creation is the Holy Grail of technology, a universal machine.
It is obvious to us today that the Turing machine is, in principle, a computer, with many of the same characteristics and capabilities; the tape is a general-purpose memory, storing both data and instructions, and the scanner is a central processor. Yet – and this is one of the greatest ironies in the history of computers – “Computable Numbers” wasn’t about computers at all and Turing never seriously considered building his machine; even with a limited tape, it would have wasted most of its time racing to and fro over the tape, a perpetually harried messenger in search of one or another precious piece of information. However, Turing didn’t dream up his mighty gadget for practical purposes. Rather, the Turing machine was conceived as a theoretical solution to a central problem in logic: the Entscheidungsproblem, or decision problem, which David Hilbert, the great German logician, had posed in 1928. Since we can’t understand “Computable Numbers” and the Turing machine – and therefore some fundamental ideas about computers – without understanding the Entscheidungsproblem, we’ll take a brief tour into the thickets of the theory of logic.