What Did Turing Establish About the Limits of Computers and the Nature of Mathematics?

Editors’ Note: This is the fourth and last in a series of essays, written by Jack Copeland, spotlighting Alan Turing, who is considered the father of modern computing and whose work breaking German codes changed the course of World War II.

In the 1930s, a group of iconoclastic mathematicians and logicians launched the field we now call theoretical computer science. These pioneers embarked on an investigation to spell out the meaning and limits of computation. Pre-eminent among them were Alan Turing, Kurt Gödel, and Alonzo Church. These three men are pivotal figures in the story of modern science, and it’s probably true to say that, even today, their role in the history of science is underappreciated. The theoretical work they carried out in the ’30s laid the foundations for the computer revolution, and the computer revolution in turn fuelled the rocketing expansion of scientific knowledge that characterizes modern times. Previously undreamed of number-crunching power was soon boosting all fields of scientific enquiry, thanks in large part to these seminal investigations. Yet at the time Turing, Gödel, and Church would have thought of themselves as working in a most abstract field, far flung from practical computing. Their concern was with the very foundations of mathematics.

Gödel, a taciturn twenty-five-year-old mathematician from Vienna University, ushered in a new era in mathematics with his 1931 theorem that arithmetic is incomplete. In a sentence, what Gödel showed is that more is true in mathematics than can be proved. This sensational result shocked, and even angered, some mathematicians. It was thought that everything true could be proved, and moreover that everything that matters ought to be proved, because only rigorous proof by transparent and obvious rules brings certainty. But Gödel showed that, no matter how the formal rules of arithmetic are laid down, there would always be some mathematical truths—complicated relatives of simpler truths like 1+1=2—that cannot be proved by means of the rules. Paradoxically, the only way to eradicate incompleteness appeared to be to select rules that actually contradict one another.

Gödel’s epoch-making result seemed to leave one of mathematics’ most fundamental problems open, though—and that’s where Turing entered the picture. This unresolved problem was known as the Entscheidungsproblem, or decision problem. German mathematician David Hilbert had brought the Entscheidungsproblem into the spotlight. Hilbert, who was 50 years Turing’s senior, set the agenda for much of twentieth-century mathematics, in a speech he gave in Paris at the turn of the century, and by the 1930s he was virtually the pope of mathematics. Turing—untidy, irreverent, and scarcely older than an undergraduate—took on the Entscheidungsproblem, and proved Hilbert fundamentally wrong about the nature of mathematics.

Turing summarized the Entscheidungsproblem like this: Is there a “general mechanical process” for telling whether any given formula is provable? (Here “provable” means that the formula can be derived, step by logical step, using the rules and principles of Hilbert’s famous logico-mathematical calculus—known to math buffs as the “engere Functionenkalkül.”) Gödel gave a dramatic and easy-to-understand explanation of what Turing established about the Entscheidungsproblem. Gödel described an imaginary machine—a computing machine—looking something like a typewriter, except for having a crank-handle at the side. “Turning the handle” was Gödel’s metaphor for what we now call “executing an algorithm.” The user typed a mathematical, or logico-mathematical, formula at the keyboard and then turned the crank-handle round once. (The formula the user elected to type could be either true or false.) On Hilbert’s—essentially computational—view of the nature of mathematics, this computing machine could, in principle, be designed to behave as follows. When the crank was turned, the machine would sound its bell if the typed formula were a provable one; and if, on the other hand, the formula were not provable, then the bell would remain silent.

In a word, this machine is able to “decide”—in the sense of figure out or calculate—whether the typed formula is a provable one or not (hence the term “decision problem”). What Turing established is very simply stated: such a machine is impossible. Once you stray beyond the most elementary areas of mathematics (like Boolean algebra and the pure monadic functional calculus) it’s simply not possible to design a finite computing machine capable of deciding whether formulae are or are not provable. It was in a 1939 lecture in the United States that Gödel gave this summary of Turing’s result, and he rounded off his exposition with the dramatic remark that, at bottom, what this shows is that “the human mind will never be able to be replaced by a machine.” Had Turing been there, he might have objected that the issue about the mind is not quite so simple—but that’s another story.

It was precisely in order to prove the impossibility of this decision-machine that Turing dreamed up his universal computing machine—his ingeniously simple digital processor with an indefinitely extendable memory. By using programs stored in its memory, the universal machine can carry out every possible computation, Turing argued. Scarcely more than a decade later, on the back of wartime technology, Turing’s invention moved out of the realm of purely theoretical constructs, to become real hardware. As we now know, the electronic universal machine went on to transform science and society both. But when Turing invented it, he wasn’t thinking about electronic computers at all. Strangely enough, he was intent on proving the existence of mathematical realms that in a certain sense lie beyond the range of any computer, no matter how powerful.

Gödel’s own greatest gift to computer science—the branch of mathematics known as recursive function theory—was also a product of this curiosity-driven exploration of mathematics’ deepest foundations. Recursive function theory is essentially the theory of computer programs, yet when Gödel invented it, he wasn’t thinking about what we now call computing at all. He was working on the proof of his incompleteness theorem, and experiencing the first hazy glimpses of an unknown mathematical world—the strange and exciting landscape that lies beyond the computable.

Would you yourself be inclined to say that computers could perform any and every well-defined mathematical task? If not in practice, then at any rate in principle? In practice, some tasks would involve such vast amounts of processing that the fastest computers would take zillions of years to complete them, and moreover the numbers involved would get so large as to swamp any realistic amount of memory. But let’s use the term “digital super-optimism” for the view that computers can, in principle, do anything and everything mathematical—if only their human programmers are able to devise the right programs, and if only enough memory and processing power are on tap. In fact, even infinite tasks can be programmed, so long as it’s assumed that the computer running the program has access to unlimited memory (as the abstract universal Turing machine does). One example of an easily programmed infinite task is to calculate x² for x = 1, then x = 2, then x = 3, and so on, ever onwards through the integers. There is no end to this program’s calculations. Whatever gigantic number x you might consider—a billion times the number of nanoseconds in a billion years, for instance—the program will eventually reach that number and calculate its square.

Turing showed, however, that digital super-optimism is false. It is definitely not the case that all well-defined mathematical tasks can be done by computer—not even in principle. Some tasks just can’t be performed by computing machines, no matter how good the programmers or how powerful the hardware. Turing was the first to describe examples of tasks like this, and in discovering them he blazed a trail through the new landscape glimpsed by Gödel—the unknown world of uncomputability.

Some of Turing’s examples are simpler than others, and the simplest one is quite surprisingly straightforward. The task is this: to work out, about any given computer program (in some specific programming language, C++ for instance) whether or not running the program will involve outputting a given keyboard character, say “#.” It might seem a relatively easy task for someone who understands the programming language to scan through the lines of a program and figure out whether any instruction is going to result in the computer’s outputting the character “#.” Yet Turing showed that no computer can perform this task. (The reason, essentially, is that the scope of the task covers all computer programs, including the program of the very computer attempting the task.) Another example of an uncomputable task is provided by Turing’s result about the decision-machine: no computer can decide if arbitrarily selected formulae are provable or unprovable in Hilbert’s engere Functionenkalkül.

Between them, Gödel and Turing delivered a double blow to Hilbert’s account of the nature of mathematics, from which it never recovered. Gödel’s incompleteness result devastated Hilbert’s theory that mathematics is essentially about proof, and five years later Turing showed that there is much more to mathematics than just computation.

In the autumn of 1936 Turing left England for the USA, planning to write a PhD thesis at Princeton University. His supervisor there was Church, third of the three central figures in the 1930s attack on computation. Church was a few years older than Turing and a young turk in the Princeton mathematics department. At the end of the 1920s he had spent six months studying with Hilbert’s group in Germany. Church’s leading contribution to the 1930s revolution—he called it the ‘lambda calculus’, after a letter from the Greek alphabet—later became part of computer programming’s basic toolset.

Before Turing’s departure from England, he and Church had almost simultaneously proposed two different mathematical definitions of the idea of computation. Gödel was not at all impressed with Church’s definition, bluntly telling Church that his approach was ‘thoroughly unsatisfactory’. Turing’s definition, on the other hand, Gödel found “most satisfactory.” Even the modest young Turing admitted that his definition was “possibly more convincing” than Church’s. It was clear from the start that his and Church’s relationship was not going to fit into the usual student–supervisor pattern.

For his thesis topic Turing chose another of Hilbert’s pontifical claims about the nature mathematics—and once again he showed that mathematical reality is not as Hilbert thought. This time the disagreement concerned what mathematicians call intuition. Most people are able to see by intuition that elementary geometrical propositions are true—for instance, that a straight line and a circle can intersect no more than twice. There’s no need to go through a train of logical steps to convince yourself that this proposition is true. Simple “seeing,” in contrast to following a conscious train of logical deductions (if this then that, and if that then such-and-such) is the hallmark of intuition. “The activity of the intuition,” Turing explained, “consists in making spontaneous judgments which are not the result of conscious trains of reasoning.” The more skilled the mathematician, the greater is his or her ability to apprehend truths by intuition.

Hilbert labelled intuition a ‘mysterious art,” believing it has no proper place in modern mathematics. He said that mathematicians should proceed “according to formulable rules that are completely definite.” In short, intuition was bad form, and refined mathematics consisted of applying rules, Hilbert believed. This was a view belonging to a previous, more uncomplicated, era. Gödel had shown in his 1931 incompleteness theorem that mathematics cannot be reduced to a system of rules, and now Turing, in his 1938 doctoral dissertation, pushed things along still further. He argued that mathematics is too unruly for intuition’s role even to be circumscribed, let alone eliminated as Hilbert had wished.

As the elimination of intuition was not attainable, Hilbert might conceivably have been willing to settle for regulating intuition’s role—for restricting its use to delivering a few clearly delimited steps in what are otherwise completely rule-governed trains of inference. Turing attacked that idea too: no bounds can be set on the need for intuition. Mathematical thinking, he summed up, should be regarded “as the exercise of a combination of two faculties, which we may call intuition and ingenuity.”

Questions for Discussion

1.     Does it matter that arithmetic is incomplete?

2.     Was Gödel right to say that “the human mind will never be able to be replaced by a machine?”

3.     What practical implications does the existence of uncomputability have for computing?

4.     Is the entire physical universe computable?

5.     Is it possible to create a “universal debugger”—a computer program that takes computer programs as input and locates any bugs in them?

6.     Can there be a different kind of information-processing machine—a “hypermachine”—that is able to do some of the tasks computers cannot?

7.     Do Turing’s ideas about intuition have any implications for how we should teach mathematics to children?