Computing with Quantum Cats Read Free Page B

holiday in his honor. But something much more significant had happened to Turing during his studentship year. He had been introduced to the puzzle of whether it was possible to establish, from some kind of mathematical first principles, whether or not a mathematical statement (such as Fermat's famous Last Theorem) was provable. Apart from the philosophical interest in the problem, if such a technique existed it would save mathematicians from wasting time trying to prove the unprovable.
    A very simple example of an unprovable statement is “this statement is false.” If it is true, then it must be false, and if it is false, it must be true. So it cannot be proven to be either true or false. The mathematical examples are more tricky, for those of us without a Part III in math, but the principle is still the same. Embarrassingly for mathematicians, it turns out that there are mathematical statements which are true, but cannot be proven to be true, and the question is whether provable statements (equivalent to “this statement is true”) in mathematics can be distinguished from unprovable statements using some set of rules applied in a certain way.
    Turing's introduction to these ideas came from a series oflectures given by Max Newman on “The Foundations of Mathematics,” drawing heavily on the work of the German mathematician David Hilbert. Newman described the application of this kind of set of rules as a “mechanical process,” meaning that it could be carried out by a human being (or a team of such human “computers”) following the rules blindly, without having any deep insight. As the Cambridge mathematician G. H. Hardy had commented, “it is only the very unsophisticated outsider who imagines that mathematicians make discoveries by turning the handle of some miraculous machine.” But Turing, always idiosyncratic and literal-minded, saw that a “mechanical process” carried out by a team of people could be carried out by a machine, in the everyday sense of the word. And he carried with him the idea, from his childhood reading, of even the human body as a kind of machine. In the early summer of 1935, as he lay in a meadow at Grantchester taking a rest from a long run, something clicked in his mind, and he decided to try to devise a machine that could test the provability of any mathematical statement. By then, he had already met von Neumann, who visited Cambridge in the spring of 1935, and had applied for a visiting fellowship at Princeton, von Neumann's base, for the following year. He would not arrive empty-handed.
    Turing came up with the idea of a hypothetical automatic machine that would operate by reading and writing symbols on a long piece of paper—a paper tape. The tape would be divided into squares, and each square would either contain the symbol “1” or be blank, corresponding to the symbol “0.” The way in which the machine was set up would determine its initial “state.” The tape would start off with a string of 1s and 0s, representing a problem that had to be solved—as Turingwas well aware, any information can be represented in such a binary code, if the string of 1s and 0s is long enough.
    This may strike you as odd, because the binary “code” seems so simple. But the printed version of this book, for example, contains a certain amount of information “stored” in the words of the English language and the letters of the alphabet. It could be translated into binary language simply by setting A = 0, B = 1, C = 10, D = 11 and so on, with extra binary numbers for punctuation marks, and writing out the string of 1s and 0s on a paper tape. Something similar, but not using this particular code, happens when my words are processed by the computer on which I write, at the printer's when the code is turned into printed pages, and, if you are reading an electronic version of the book, inside your reader.
    The