Computing with Quantum Cats Read online

  As in all public schools, filled with teenage boys with no other outlet for their burgeoning sexuality, there were inevitably liaisons between older and younger pupils, no matter how much such relationships might be officially frowned upon. It was in this environment that Alan realized that he was homosexual, although there is no record of his having any physical relationships with other boys at school. He did, though, develop something more than a crush on a boy a year ahead of him at school, Christopher Morcom.

  The attraction was as much mental as physical (indeed, from Morcom's side it was all mental). Morcom was another mathematician, with whom Alan could discuss science, including Einstein's general theory of relativity, astronomy, and quantum mechanics. He was a star pupil who worked hard at school and achieved high grades in examinations, giving Alan, used to taking it easy and relying on brilliance to get him through, something to strive to emulate. The examination they were both working for, the Higher School Certificate (or just “Higher”), was a prerequisite to moving on to university. In the mathematics paper they sat, Alan scored a respectable 1,033 marks; but Morcom, the elder by a year, scored 1,436.

  In 1929, Morcom was to take the examination for a scholarship at Trinity College, Cambridge. He was eighteen, and expected to pass. Alan was desperate not to see his friend go on to Cambridge without him. He decided to take the scholarship examination at the same time, even though he was still only seventeen and Trinity was the top college in Britain (arguably, in the world) for the study of math and science, with a correspondingly high admission standard. The examinations were held over a week in Cambridge, giving the two Shirburnians a chance to live the life of undergraduates, and to meet new people, including Maurice Pryce, another candidate, whom Alan would meet again when their paths crossed in Princeton a few years later.

  The outcome was as Alan had feared. Morcom passed, gaining a scholarship to Trinity that gave him sufficient income to live on as an undergraduate. Alan did not, and faced a separation of at least a year from his first love. But the separation became permanent when Morcom died, of tuberculosis, on February 13, 1930. Alan wrote to his own mother: “I feel that I shall meet Morcom again somewhere and that there will be some work for us to do together…. Now that I am left to do it alone I must not let him down.” And in the spirit of doing the work that they might have done together, or that Morcom might have done alone, and “not letting him down,” Alan tried once again for Cambridge in 1930. Once again, he failed to obtain a Trinity scholarship; but this time he was offered a scholarship worth £80 a year at his second choice of college, King's. He started there in 1931, when he was nineteen.

  CAMBRIDGE…

  Turing managed the unusual feat of joining in both the sporting life (as a runner and rower) and the academic life in Cambridge, while never quite fitting in anywhere socially. He also enjoyed at least one homosexual relationship, with another math student, James Atkins. But it is his mathematical work that is important here. Turing's parting gift from Sherborne, in the form of a prize for his work, had been the book Mathematical Foundations of Quantum Mechanics, by the Hungarian-born mathematician John von Neumann, who would soon play a personal part in Turing's story.3 In an echo of his early days at Sherborne, not long after he arrived in Cambridge Turing independently came up with a theorem previously (unbeknown to him) proven by the Polish mathematician Wacław Sierpiński; when Sierpiński's priority was pointed out to him, he was delighted to find that his proof was simpler than that of the Pole. Polish mathematicians would also soon loom large in Turing's life.

  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.”4 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.”5 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 wa
s to produce a cipher that would require “100 Germans working eight hours a day on desk calculators 100 years to discover the secret factor.”6

  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.