Computing with Quantum Cats (3 page)

In the early 1930s, the structure of the mathematics course in Cambridge was changing. Everybody who entered in 1931 (eighty-five students in all) took two key examinations,
Part I
at the end of the first year and
Part II
at the end of the third year. So-called “Schedule A” students left it at that, which was sufficient to gain them their degrees. But “Schedule B” students, including Turing, took a further, more advanced, examination, also at the end of their third year. For the intake which followed Turing's year, the extra examination was taken after a further (fourth) year of study, as it has been ever since: it became known as
Part III
, and is now roughly equivalent to a Master's degree from other universities.

This peculiarity of the Cambridge system partly explains
why Turing never worked for a PhD in Cambridge. Having passed his examinations with flying colors, he was offered a studentship worth £200 which enabled him to stay on at Cambridge for a year to write a dissertation with which he hoped to impress the authorities sufficiently to be awarded a fellowship at King's. In the spring of 1935, still only twenty-two years old, Turing was indeed elected as a Fellow of King's for three years, with the prospect of renewal for at least a further three years, at a stipend of £300 per year; the success was sufficiently remarkable that the boys at Sherborne were given a half-day 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 of
lectures 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 Turing
was 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 machine Turing described would, when setting out to solve a specific problem, read the first symbol on a tape, and, in accordance with its state at the time, either erase a 1, print a 1, or do nothing. Then it would move on to the next square, and act in accordance with its new state, which would have been determined by what happened at square 1. It could move forwards and backwards along the tape, but only one square at a time, writing and erasing symbols, until it reached a state corresponding to the end of its task. It would then stop, and the string of 1s and 0s left on the tape would represent the solution to the problem the machine had been working on. And it would have been done by a purely “mechanical” process, owing nothing to inspiration or human intuition.

In terms of the original problem he had set out to solve, Hilbert's provability question, Turing's hypothetical machine was a great success. Simply by considering the way in which such a machine would work, he was able to show, using a
detailed argument which we do not need to go into here, that there are uncomputable problems, and that there is no way to distinguish provable statements in mathematics from unprovable statements in mathematics using some set of rules applied in a certain way. This was impressive enough. But what is even more impressive, and the main reason why Turing's paper “On Computable Numbers” is held in such awe today, is that he realized that his “automatic machine” could be a universal computer. The way the machine works on a particular problem depends on its initial state. It is a limited machine that can only solve a single problem. But as Turing appreciated, the initial state can be set up by the machine reading a string of 1s and 0s from a tape—what we now call a computer program. The same piece of machinery (what we now call hardware) could be made to do any possible task in accordance with appropriate sets of instructions (what we now call software). One such machine can simulate the work of any such machine. And such machines are now known as Turing machines. In his own words, “it is possible to invent a single machine which can be used to compute any computable sequence.”

The relevance of this idea to the logical puzzle that triggered Turing's investigation is that although he proved that it is possible to construct a machine to solve any solvable problem, it is not possible to construct a machine which can predict how many steps it will take to solve a particular problem. This is what establishes that although you can build an automaton to do anything that can be done, you cannot build a machine which tells you what can and can't be done. Logicians appreciate the full importance of this proof; but that is less important to us here than the fact that Turing machines exist.

A Turing machine simulates the activity of any specialist computer, using different sets of software. This is exactly what my iPhone, for example, does. It can be a phone, a TV or a navigation aid; it can play chess, solve certain kinds of mathematical problems, and do many other things. It can even do things its designers never thought of, as when an outside programmer devises a new app. Most people in the developed world now own, or have access to, a Turing machine, less than eighty years after the publication of “On Computable Numbers.”

The paper was completed in the spring of 1936, just after the German army re-occupied the Rhineland, and it was published just under a year later, in the
Proceedings of the London Mathematical Society
. In the interim, an inconvenient blip occurred. Just a month after he had read an early draft of Turing's paper, Max Newman received a copy of a paper by Alonzo Church, a mathematician based at Princeton, in which he reached the same conclusion about Hilbert's question, using a technique he called lambda calculus. In a sense, Turing had been pre-empted, and although his version was still worth publishing, he had to add an appendix establishing that his work and Church's work were equivalent. Nobody realized, at the time, that the really important discovery described in that paper was the principle of the universal Turing machine.

…AND PRINCETON

Encouraged by Newman and the possibility of working with Church, Turing was determined to make his visit to Princeton. He had applied for one of the Proctor Fellowships offered by Princeton; there were three of these each year, one for a
Cambridge scholar, one for Oxford and one for the Collège de France. Turing's application was unsuccessful—the Cambridge award that year went to the astronomer and mathematician Raymond Lyttleton—but he decided he could scrape by on his King's fellowship, which continued even when he was away, and went anyway, sailing from Southampton on the liner
Berengaria
on September 23, 1936.

“Working with Church” didn't quite live up to expectations, although the pair got on well enough, by the standards of Church's interactions with other people. Church was one of those people, not uncommon in the mathematical sciences, with a tendency towards autism—the physicist Paul Dirac, described by his biographer Graham Farmelo as “the strangest man,” is a prime example, although Church seems to have been nearly as strange. A colleague described him as speaking “slowly in complete paragraphs which seemed to have been read out of a book, evenly and slowly enunciated, as by a talking machine.”
⁴
His lectures always began with a ritual cleaning of the blackboard with soap and water, followed by ten minutes waiting for it to dry; but since the lectures simply consisted of reading out the same typewritten texts every year, there was plenty of time to spare. In 1936, Church was thirty-three and Turing twenty-four. In their own ways, both were a little peculiar and used to working alone. Turing was desperately shy, and had a fierce stammer (which, curiously, never troubled him when he was reading from a prepared script for radio broadcasts). It is scarcely surprising that there was no significant collaboration between them, although they did work together on a paper spelling out the equivalence of their two approaches to the Hilbert question, and Church acted as the formal supervisor for a thesis Turing wrote to
obtain a Princeton PhD, although by then he hardly needed the degree. More significantly, Turing established contact with von Neumann, of whom more shortly, who certainly appreciated the implications of “On Computable Numbers.” According to the computer scientist Julian Bigelow, who was in Princeton at the time, the fact that it was possible in principle to build a universal machine that could imitate all other machines “was understood by von Neumann.”
⁵
When Turing decided to apply again for a Proctor Fellowship to enable him to spend a second year at Princeton, it was von Neumann who wrote a letter of recommendation on his behalf. Turing, he said, “has done good work in branches of mathematics in which I am interested,” and was “a most deserving candidate.” With such support, this time the application was successful. Turing spent the summer of 1937 in England, where he got to know the philosopher Ludwig Wittgenstein, before returning to the United States “a rich man,” as he told his mother, with $2,000 to live on.

Unlike Church, Turing had practical skills. He had become interested in cryptography, specifically the kind of codes (strictly speaking, ciphers, but I shall use the terms interchangeably) that involve translating messages into numbers and then manipulating the numbers to produce a coded message. In a simple example, you can represent the letter A by 1, B by 2 and so on. Once your message is written out as a string of numbers, you then multiply that number by a large prime number to produce a new number, which can be transmitted openly. The person receiving the message can decipher it by dividing by the original prime number, but nobody who does not know this “key” can read the message. Back in Princeton, Turing decided to build a machine to carry
out this kind of multiplication, on a very small scale. He was motivated by increasing concern about the prospect of war in Europe, and told Malcolm MacPhail, a Canadian physicist who lent Turing a key to the workshop at Princeton, that the ultimate object was to produce a cipher that would require “100 Germans working eight hours a day on desk calculators 100 years to discover the secret factor.”
⁶

The machine used electromechanical switches—relays like those used in telephone exchanges at the time, controlled electrically. Such switches can only be either on or off, representing the 1s and 0s of a binary number. And binary multiplication is particularly simple, since it goes “0 × 0 = 0, 1 × 0 = 0, 1 × 1 = 1”—and that's it. Turing's electronic multiplier was never finished; it was only a part-time project, with limited resources. But he did build several components of the machine which worked satisfactorily.

In March 1938, the same month that Germany swallowed up Austria in an
Anschluss
, Turing was re-elected as a fellow of King's, although the news did not reach him immediately. Before it did, his father wrote urging him to find a permanent post in America, safely out of the way of any conflict, and Turing was actually offered a job as von Neumann's assistant at the Princeton Institute for Advanced Study (IAS), at a salary of $1,500 a year. But he was eager to return home, and never seriously considered the offer. He arrived back at Southampton on July 23, 1938, armed with a fresh (but pointless) Princeton PhD and the pieces of his electronic multiplier wrapped in brown paper. Almost immediately, he was recruited to take a summer course at the Government Code and Cipher School (GC&CS), then based in London, as one of several people identified through the old boy network
as likely to be useful in that branch of wartime intelligence.