It used to be supposed in science that if everything was known about the Universe at any particular moment then we can predict what it will be through all the future. This idea was really due to the great success of astronomical prediction. More modern science however has come to the conclusion that when we are dealing with atoms and electrons we are quite unable to know the exact state of them; our instruments being made of atoms and electrons themselves. The conception then of being able to know the exact state of the universe then really must break down on the small scale. This means then that the theory which held that as eclipses etc. are predestined so were all our actions breaks down too. We have a will which is able to determine the action of the atoms probably in a small portion of the brain, or possibly all over it.⁷

For the rest of his life, Turing would wrestle with the issue of whether the human mind was fundamentally different from a deterministic machine, and he would gradually come to the conclusion that the distinction was less clear than he had thought.

He also had an instinct that, just as uncertainty pervaded the subatomic realm, there were also mathematical problems that could not be solved mechanically and were destined to be cloaked in indeterminacy. At the time, mathematicians were intensely focused on questions about the completeness and consistency of logical systems, partly due to the influence of David Hilbert, the Göttingen-based genius who, among many other achievements, had come up with the mathematical formulation of the theory of general relativity concurrently with Einstein.

At a 1928 conference, Hilbert posed three fundamental questions about any formal system of mathematics: (1) Was its set of rules complete, so that any statement could be proved (or disproved) using only the rules of the system? (2) Was it consistent, so that no statement could be proved true and also proved false? (3) Was there some procedure that could determine whether a particular statement was provable, rather than allowing the possibility that some statements (such as enduring math riddles like Fermat’s last theorem,^I Goldbach’s conjecture,^II or the Collatz conjecture^III) were destined to remain in undecidable limbo? Hilbert thought that the answer to the first two questions was yes, making the third one moot. He put it simply, “There is no such thing as an unsolvable problem.”

Within three years, the Austrian-born logician Kurt Gödel, then twenty-five and living with his mother in Vienna, polished off the first two of these questions with unexpected answers: no and no. In his “incompleteness theorem,” he showed that there existed statements that could be neither proved nor disproved. Among them, to oversimplify a bit, were those that were akin to self-referential statements such as “This statement is unprovable.” If the statement is true, then it decrees that we can’t prove it to be true; if it’s false, that also leads to a logical contradiction. It is somewhat like the ancient Greek “liar’s paradox,” in which the truth of the statement “This statement is false” cannot be determined. (If the statement is true, then it’s also false, and vice versa.)

By coming up with statements that could not be proved or disproved, Gödel showed that any formal system powerful enough to express the usual mathematics was incomplete. He was also able to produce a companion theorem that effectively answered no to Hilbert’s second question.

That left the third of Hilbert’s questions, that of decidability or, as Hilbert called it, the Entscheidungsproblem or “decision problem.” Even though Gödel had come up with statements that could be neither proved nor disproved, perhaps that odd class of statements could somehow be identified and cordoned off, leaving the rest of the system complete and consistent. That would require that we find some method for deciding whether a statement was provable. When the great Cambridge math professor Max Newman taught Turing about Hilbert’s questions, the way he expressed the Entscheidungsproblem was this: Is there a “mechanical process” that can be used to determine whether a particular logical statement is provable?

Turing liked the concept of a “mechanical process.” One day in the summer of 1935, he was out for his usual solitary run along the Ely River, and after a couple of miles he stopped to lie down among the apple trees in Grantchester Meadows to ponder an idea. He would take the notion of a “mechanical process” literally, conjuring up a mechanical process—an imaginary machine—and applying it to the problem.⁸

The “Logical Computing Machine” that he envisioned (as a thought experiment, not as a real machine to be built) was quite simple at first glance, but it could handle, in theory, any mathematical computation. It consisted of an unlimited length of paper tape containing symbols within squares; in the simplest binary example, these symbols could be merely a 1 and a blank. The machine would be able to read the symbols on the tape and perform certain actions based on a “table of instructions” it had been given.⁹

The table of instructions would tell the machine what to do based on whatever configuration it happened to be in and what symbol, if any, it found in the square. For example, the table of instructions for a particular task might decree that if the machine was in configuration 1 and saw a 1 in the square, then it should move one square to the right and shift into configuration 2. Somewhat surprisingly, to us if not to Turing, such a machine, given the proper table of instructions, could complete any mathematical task, no matter how complex.

How might this imaginary machine answer Hilbert’s third question, the decision problem? Turing approached the problem by refining the concept of “computable numbers.” Any real number that was defined by a mathematical rule could be calculated by the Logical Computing Machine. Even an irrational number such as π could be calculated indefinitely using a finite table of instructions. So could the logarithm of 7, or the square root of 2, or the sequence of Bernoulli numbers that Ada Lovelace had helped produce an algorithm for, or any other number or series, no matter how challenging to compute, as long as its calculation was defined by a finite set of rules. All of these were, in Turing’s parlance, “computable numbers.”

Turing went on to show that noncomputable numbers also existed. This was related to what he called “the halting problem.” There can be no method, he showed, to determine in advance whether any given instruction table combined with any given set of inputs will lead the machine to arrive at an answer or go into some loop and continue chugging away indefinitely, getting nowhere. The insolvability of the halting problem, he showed, meant that Hilbert’s decision problem, the Entscheidungsproblem, was unsolvable. Despite what Hilbert seemed to hope, no mechanical procedure can determine the provability of every mathematical statement. Gödel’s incompleteness theory, the indeterminacy of quantum mechanics, and Turing’s answer to Hilbert’s third challenge all dealt blows to a mechanical, deterministic, predictable universe.

Turing’s paper was published in 1937 with the not so snappy title “On Computable Numbers, with an Application to the Entscheidungsproblem.” His answer to Hilbert’s third question was useful for the development of mathematical theory. But far more important was the by-product of Turing’s proof: his concept of a Logical Computing Machine, which soon came to be known as a Turing machine. “It is possible to invent a single machine which can be used to compute any computable sequence,” he declared.¹⁰ Such a machine would be able to read the instructions of any other machine and carry out whatever task that machine could do. In essence, it embodied the dream of Charles Babbage and Ada Lovelace for a completely general-purpose universal machine.