Computing with Quantum Cats

IF NECESSITY IS the mother of invention, the computer had two mothers – cryptography and the hydrogen bomb. But there was only one father: Alan Mathison Turing.

A child of empire

Turing was conceived in India, where his father, Julius, was a member of the Indian Civil Service helping to administer this jewel in the crown of the British Empire; but he was born, on 23 June 1912, in Maida Vale, London, when his parents were on home leave. He already had a brother, John, born in India on 1 September 1908. When Julius returned to India their mother, Sara,¹ stayed in England with the two boys, but only until September 1913, when she rejoined her husband and left the children in the care of a retired army colonel and his wife, who lived at St Leonards-on-Sea in Sussex. There was a nanny who looked after the two boys and the colonel’s four daughters, together with another boy whose parents were overseas, and later three cousins of Alan and John. Their mother returned for the summer of 1915, staying with the boys in rented rooms in St Leonards, and both parents came to England in the spring of 1916 – the first time that Alan really had an opportunity to get to know his father. At the end of this leave, in August, Julius Turing returned to India for his next three years’ tour of duty. John had already been sent away to school at Hazelhurst, in Kent; Alan, having been just one of a motley group of children, now became in effect the only child of a single parent, who took him almost everywhere with her, including to the High Anglican church she attended (which he hated) and to art classes (she was an accomplished watercolourist), where he was the darling of the female students.

Alan was remembered as a bright, untidy child with a predilection for inventing his own words, such as ‘quockling’ to describe the sound of seagulls and ‘greasicle’ for a guttering candle. It was impossible to pull the wool over his eyes – when his nanny tried to let him win a game they were playing by making poor moves, he saw through the subterfuge and was infuriated; when his mother was reading him a story and left a dull passage out, he yelled: ‘You spoil the whole thing.’² Nor was he ever in any doubt about the accuracy of his own world-view: he knew, for example, that the fruit which tempted Eve in the Garden of Eden was a plum. But he never could tell left from right, and marked his left thumb with a red spot so that he would know which was which.

Having taught himself to read (from a book appropriately called Reading Without Tears), Alan first encountered formal education at the age of six, when his mother sent him to a local day school to learn Latin. This failed to stir his interest, but highlighted his great difficulty with the physical process of writing, especially with the ink pens in use at the time. His work was always a mess of scratchy scribbles, crossings-out and blots, reminiscent of nothing so much as the spoof handiwork of Nigel Molesworth in the stories by Geoffrey Willans and Ronald Searle.

Alan’s next meeting with his father came in 1919, when Julius’s leave included a holiday in Scotland: here the seven-year-old boy impressed his family on a picnic by tracking the flights of wild bees to their intersection to find honey. But in December both parents sailed for India, and Alan returned to the colonel’s house in St Leonards while John went back to school in Hazelhurst. The next two years saw a change in Alan. When his mother next returned, in 1921, she found that the vivacious and friendly boy she had left in England had become ‘unsociable and dreamy’, while his education had been so neglected that at nearly nine he had not learned how to do long division. She took him away for a holiday in Brittany, and then to London, where she taught him long division herself. She later recalled that when he had been shown how to find the square root of a number, he worked out for himself how to find the cube root.

At the beginning of 1922, it was time for Alan to follow his brother John to Hazelhurst, a small school for thirty-six boys aged from nine to thirteen, with just three teachers and a matron who looked after the boys. The brothers were together at Hazelhurst for only one term before John left at Easter for Marlborough College and the public-school education for which ‘prep’ schools such as Hazelhurst were preparing their boys. The same year, Alan was given a book called Natural Wonders Every Child Should Know, by Edwin Brewster. This first encounter with science made a deep impression on him, especially the way the author likened the workings of the body, even the brain, to a machine. He was less impressed by the sporting activities that young English gentlemen of the time were expected to enjoy (or at least endure), and later claimed that he had learned to run fast (he became a very good long-distance runner as an adult) in order to keep away from the ball during hockey. He was also disturbed by the imprecision of some of his teachers, and wrote to John that one of them ‘gave a quite false impression of what is meant by x’. His concern was not for himself, but that the other boys might be misled.

The summer of 1922 brought the return of Alan’s father on leave once more, and another happy family holiday in Scotland. But in September his parents left him back at Hazelhurst, departing down the drive of the school with Sara biting her lip as she watched her son running futilely after the taxi, trying to catch up with them. Bored by school, Alan achieved nothing spectacular in the way of marks, but loved inventing things and developed a passion for chemistry – which was purely a hobby: God forbid that a prep school like Hazelhurst should have anything to do with science. Science was almost as conspicuous by its absence at most public schools, so when in the autumn of 1925 Alan surprised everyone by doing well in the Common Entrance examination that was a prerequisite to the transition, his future presented his parents with something of a conundrum. John made an impassioned plea to their parents not to send his unusual younger brother to Marlborough, which ‘will crush the life out of him’, and Sara Turing worried that her son might ‘become a mere intellectual crank’ if he failed to adapt to public school life. The puzzle of what to do with him was solved by a friend of hers who was married to a science master at Sherborne, a school in Dorset established back in 1550 and brought into the modern public school system in 1869. The friend assured Sara that this would be a safe haven for her boy, and Alan started there in 1926.

Sherborne

He was due to arrive for the start of the summer term, on 3 May, from Brittany, where his parents were living to avoid paying British income tax. On the ferry to Southampton, Alan learned that there would be no trains, because of the general strike; totally unfazed, and still a month short of his fourteenth birthday, he cycled the 60 miles to Sherborne, staying overnight at Blandford Forum. This initiative was sufficiently unusual to merit a comment in the Western Gazette on 14 May. The same initiative and independence were shown a little later when Alan worked out for himself the formula known as ‘Gregory’s series’ for the inverse tangent, unaware that it had been discovered in 1668 by the Scottish mathematician James Gregory (inventor of a kind of telescope that also bears his name), and even earlier by the Indian mathematician Madhava.

Alan soon settled into his old habit of largely ignoring lessons that he found boring, then doing well in examinations, while continuing his private chemistry experiments and amusing himself with advanced mathematics. At Sherborne, grades depended on a combination of continuous assessment and examinations, each marked separately but with a final combined mark. On one occasion, Alan came twenty-second out of twenty-three for his term’s work, first in the examinations, and third overall. His headmaster did not approve of such behaviour, and wrote to Alan’s father: ‘I hope he will not fall between two stools. If he is to stay at a Public School, he must aim at becoming educated. If he is to be solely a Scientific Specialist, he is wasting his time at a Public School.’ But Alan escaped expulsion, and was rather grudgingly allowed to take the School Certificate examination, which had to be passed before he could move on to the sixth form at the beginning of 1929. His immediate future after school, however, was decided as much by love as by logic.

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 maths 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 13 February 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 maths 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.³ 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) proved 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 colours, 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 honour. 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 proved to be either true or false. The mathematical examples are more tricky, for those of us without a Part III in maths, but the principle is still the same. Embarrassingly for mathematicians, it turns out that there are mathematical statements which are true, but cannot be proved 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 23 September 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 23 July 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.

Not long after this, Turing had another experience that made a deep impression on him. In Cambridge that October he saw the Disney film Snow White and the Seven Dwarfs, and became fascinated by the scene in which the White Witch prepares the apple for Snow White. He used to go around reciting her incantation:

Dip the apple in the brew,

Let the Sleeping Death seep through.

Bletchley and the Bombe

GC&CS had become aware of the need to recruit mathematicians in case war should break out largely because of the adoption by the German military of a cipher machine called Enigma. The version of Enigma in use at that time contained three moveable discs (called rotors) in a line and a fourth, fixed, ‘reflector’, each with twenty-six electrical contacts, one for each letter of the alphabet. An electronic signal produced by pressing an individual letter on a keyboard (A, perhaps) passed into the first rotor and out through a different contact (maybe corresponding to L) into the adjacent contact in rotor two, and so on for rotors two and three, following a path determined by the alignment of the rotors and their internal wiring; then it was scrambled once more before being reflected back from the fourth rotor. After another three stages of scrambling, going back through the three rotors in reverse order, it then lit up a light bulb corresponding to another letter of the alphabet (crucially, never the same letter as the original keystroke). The operator then entered this as the first letter of the coded message, and proceeded to the next – but as that next key was pressed, the rotors moved on one click, so that a different electrical path would now be followed, and if the operator pressed A twice in a row, for example, two different letters would appear in the coded message.

The great practical advantage of these machines, thanks to the reflection process, was that, assuming the rotors of two machines were set up in the same way to start with, in order to decipher the message coded on one machine and broadcast by, say, Morse code, an operator far away using the other machine had only to type in the coded message, letter by letter, to retrieve the original plain text. The military version of Enigma also included a development called a plugboard, which involved literally plugging wires into pairs of holes in a board to connect pairs of letters at the first stage of the coding process. If, for example, J and G were joined in this way, and also Q and B, pressing key J would send the signal through contact G on the first rotor, not through J, and back perhaps as the coded letter Q which would follow the plugboard to emerge as B. Fortunately for the codebreakers, only six or seven pairs of letters were usually connected in this way.

There are 26 × 26 × 26 = 17,576 different ways to connect the three rotors in such a machine (the reflector does not rotate), and the code for a particular message could be cracked (if you knew the wiring of the rotors themselves) simply (if tediously) by trying out all 17,576 combinations to find the one that worked. The three rotors could be arranged in six different orders (1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,1,2; 3,2,1), but even 6 × 17,576 is not a number to daunt cryptanalysts. A plugboard with seven possible pairs out of 26 letters, though, introduced 1,305,093,289,500 ways of setting the machine for each of the 6 × 17,576 rotor settings. This was such a high number that the Germans were convinced that the Enigma code was uncrackable, and initially the British, sharing that view, devoted little attention to it. But, through a combination of luck and brilliance, the Poles, deeply concerned about the threat to their country from the Nazis, found a way into Enigma.

The luck came in 1932, when French spies got hold of a set of instructions which could be interpreted to reveal the wiring of the Enigma rotors. The French shared this information with their allies Poland and Britain, but only the Poles had the initiative to set a team of mathematicians the task of interpreting the information in this way. The skill came first in unravelling the wiring, and then in breaking the pattern used by the Germans to set up the Enigma machines each day. These basic settings were laid down in a set of instructions issued to all operators, and known as a ‘ground setting’. This would involve arranging the order of the rotors, then adjusting the three rotors, rather like setting a combination lock, so that a particular set of three letters, such as BKW, was at the top. Using this setting, the operator would choose his own setting for the rotors, perhaps XAF, and encipher this twice, producing a six-letter string such as AZQGBP, and send this on the ground setting before turning the rotors to the chosen setting and enciphering his message.

The snag was that each operator was using the same triplet, coded twice, based on the same rotor setting, at the start of every day – so that hundreds of short messages with identical content were going out coded the same way. The system was later improved so that although all operators used the same rotor setup each day, each operator could choose the initial setting and transmit it uncoded, in plain language, before going through the rest of the setup procedure. Even with this refinement, the repetition involved, and details such as the fact that no letter could be coded as itself, produced patterns when many messages were analysed, and this enabled the Poles to draw up statistical tables from which they could eliminate most possible settings of the Enigma machines each day and end up with the right setting. This was still a time-consuming process to carry out by hand. But the great breakthrough came when the Poles devised an electromechanical machine, using commercially available relays like those in Turing’s prototype multiplier, to work through all the possibilities. The relays clicking inside the machine when it was working made a sound like the ticking of the clockwork mechanism of a time bomb, so the machines became known as Bombas to the Poles, and more advanced machines, essentially developed by Turing and superficially similar to the Polish devices, were later dubbed Bombes by the British.

Until the end of 1938, with the aid of their Bombas the Poles were cracking the German Enigma codes not because Enigma was inherently unsafe, but because the Germans, complacently sure it was uncrackable, were careless in its use. This would be a recurring theme: what should have been an uncrackable system (and was, when used properly – by the German navy, in particular) was compromised by foolishness at high level, as in the use of repeated triplets just described, and personal stupidity at lower levels, as when operators began or signed off their messages ‘Heil Hitler’ or used a girl’s name for their initial rotor setting.

It was further made vulnerable by the carelessness of its operators and the bureaucratic nature of their system, so that many messages might begin with the German words for ‘Daily Report’, for example. One way into a message would be to take a ‘crib’ for a common word, such as Flugzeug (aeroplane) and find a match by ‘dragging’ a string of letters corresponding to the word through a message;⁷ and there were other statistical techniques. This process was greatly simplified by the German habit of using standard phrasing: for example, starting weather reports with the words Wetter für die Nacht (‘weather for the night’) and instructions sent out to Luftwaffe squadrons with the phrase ‘special instructions for’ followed by the squadron number. But all that only just made the Enigma codes crackable, and the cryptanalysts’ work often suffered setbacks – as at the end of 1938, when the Germans introduced two new rotors for each machine, making sets of five, from which three were chosen each day. Instead of there being six ways to order the rotors actually used, there were now sixty possibilities, and even with the aid of their Bombas the Poles could no longer cope. Worse, early in 1939 the Germans increased the number of pairings on the plugboard from six to ten. This was the situation in the summer of 1939 when, with war looming, the British and French sent teams to Warsaw to discuss the situation, and were astonished when the Poles revealed what they had managed to achieve.

Not the least of those achievements was that the Poles managed to keep the secret of the Bombas and the cracking of Enigma from their German occupiers after their country was invaded in September 1939. By then, GC&CS had been moved to a country house in Buckinghamshire, Bletchley Park, where Turing was among the prospective codebreakers ordered to report on 4 September.⁸ There, he was instrumental in the design and manufacture of the British Bombes, much more sophisticated machines capable of dealing even with the five-rotor system and the ten pairs of plugboard settings, provided the German operators of Enigma were careless enough to provide scraps of ‘cribs’ such as weather reports headed Wetter⁹