 My Publications |
Electronic Spinby Andrew HodgesA feature on Alan Turing
|
War stories generally involve a muddle of fact and fiction: not just in the spin of 'briefings' but lasting decades later. The story of the computer, which started in the foggy history of the Second World War, is no exception. Alan Turing (1912-1954) the British mathematician who formulated the first complete computer plan, remained a mystery for twenty years after his death. There is a specific reason for this: digital computing began in crypto, and crypto is by definition about deception, and the most closely guarded of state secrets. Alan Turing was the most important figure in World War II crypto, building on Polish mathematicans' work and in 1939 making a new breakthrough into decipherment of the now famous German Enigma messages. Fog of war still swirls around. When the feature film Enigma was released in 2001, the production company's PR material included claims about Alan Turing as the originator of the computer. The film itself gave the impression that its hero was 'really' Turing.
In fact, the film Enigma conflated two figures which in Robert Harris's original novel were clearly distinct: a fictional hero figure for the 1943 plot, and the real historical figure of Alan Turing, described as the originator of the British breakthrough with Enigma. The 1943 plot was fictional, but its setting, the world of the codebreaking centre at Bletchley Park, and the crisis of the battle of the Atlantic in March 1943, was realistic. What was the real Alan Turing doing at just that point? He was himself crossing the embattled Atlantic, returning from New York. A Robert Harris of the day would never have guessed that this eccentric, shy, boffin had been a high-level cog in the emerging UK-USA military alliance. In 1943 power was passing irretrievably to the USA, and a crucial aspect of the new UK-USA relationship was that Britain had been able to transfer its Enigma codebreaking to America. Crypto underlay the geopolitical situation; crypto also pushed 1940s computing to extremes, and out of this emerged, through Alan Turing, the computer in its modern form. Alan Turing spent that voyage with an electronics manual, learning electronics for himself to supplement what he knew from building a radio set at school.
A character stranger than fiction, this would be a filmic moment, a sports-jacketed Cambridge don with a ship-load of American troops. At a central moment of the twentieth century, yet an outsider, he was too far ahead of his time to be appreciated: the same was true for him as a gay man, coming out honestly twenty years too early for his own good. Plain and honest speaking was typical of him, and therefore made it very ironic that he more than anyone was involved in deadly secrecy. 'Phoney' was one of his favourite terms of abuse, along with 'politician, salesman, charlatan': Alan Turing would not have been 'comfortable' with 'spin'. In the end the contradictions would kill him in 1954: criminalised by openness he famously took potassium cyanide and left a bitten apple as a clue. The apple was from Eden, or maybe from Snow White. Filmic again, but not for Hollywoood: the playwright Hugh Whitemore, whose play Breaking the Code told Turing's story, was told by a producer to adapt it thus: 'I don't want this guy to be a faggot and for God's sake cut out all the mathematics.'
I introduced Alan Turing as a 'mathematician' because that was how he described himself, but as well as being rather offputting, this label conceals the full scope of what he did. His original 1936 work was indeed mathematical, but it went outside classical mathematics both to lay down a new kind of logical engineering, and also to cast new light on old questions of mind and matter. This paper defined the mind-set of programming, breaking down huge tasks into routines that can be done automatically, one step at a time. By defining the idea of a machine for symbolic manipulations, now called a Turing machine, he defined precisely the concept of algorithm — the concept we can't help seeing now as a computer program. You couldnąt have called it that in 1936 because there weren't any computers — but that is exactly what Turing saw, ahead of his time. He described in this 1936 paper the definition of a universal machine, which embodies exactly the modern idea of a computer which can read any program and execute it. His scheme naturally embodied the idea that instructions can be stored and manipulated just like data — a concept now so natural that it's used without thinking, but which made Turing's ideas entirely different from those of Babbage and his followers. Thus he founded the new world of computer science.
As there is often confusion about this, I should emphasise that the universal machine was not used in World War II codebreaking. But large-scale electronic switching was successfully used — in the Colossus. (This was used to break another German cipher system, quite different from the Enigma.) So I wouldn't call Colossus 'the first computer' as some people do — it was an electronic machine designed for a special purpose, and it didn't have the defining property of loading software into an all-purpose store. The success of the Colossus, however, meant that Turing learnt between 1943 and 1945 how electronic megahertz speed could turn into practice the universal machine of his 1936 theory.
Usually the Hungarian-American John von Neumann gets the credit for the first general plan, and it's true that the EDVAC report of June 1945 was complete before Turing finished his first report. But Turing's plan was independent, more detailed, and had much more to say about the scope of the new computer world. It can also be said that von Neumann's contribution was possible because he knew the principle of a stored-program computer from Turing's 1936 work. Of course, the American work got much better and bigger publicity.
The contrast between American and British approaches was marked. Turing was a true Brit in his attitude, critical of what he called 'the American approach of using much equipment rather than thought.' (In March 2003 I heard a similar criticism: 'we equip the man, they man the equipment' from a Royal Marine). Turing's words probably reflected his top-level visit in December 1942 to Dayton, Ohio, to inspect the progress of the new American Bombes. These had been organised rapidly and on a large scale but without regard to the sophisticated short-cut methods employed by the British at Bletchley Park.
Turing didn't have much equipment, but did a lot of thinking during 1944 and 1945, based mainly in a hut in a MI6 establishment, Hanslope Park, where he had one engineer assistant. He was 'building a brain,' he told his assistant; it sounds like Dad's Army. This was where the computer revolution was conceived, though at the time no-one — certainly not a historian or film director — would have noticed its significance.
In October 1945, Alan Turing was taken on at the National Physical Laboratory, with a commission to finish design his computer design, but he was defined as a mathematican, not engineer: as soft, not hard. VE Day had reinstated divisions and distinctions which were to kill his project. In 1940, in a desperate situation, Turing's lone effort against the defeatism of the establishment, had allowed him to work with both logic and engineering and so design the Bombe. But after the war he was compartmentalised, and also suffered from his work being so secret that it gave him no authority. His difficulties were accentuated by his own eccentric way of doing his own thing. In 1946 it was not usual for civil servants to run across London to departmental meetings, combining his work with training for the marathon running that nearly got him into the 1948 Olympic squad.
Nonetheless, the NPL appointment gave him a platform on which to announce a prospectus. In March 1946 Turing presented his plan for a computer, dubbed the ACE (Automatic Computing Engine), and its presentation was at that point the most complete plan and comprehensive survey of the future of computing. Turing had advanced ideas on its physical setting: for instance, he imagined how the ACE could be used remotely by a telephone link. But Turing's very individual ideas for the hardware are not so much of interest now; more important is that he saw the emergent world of software. He listed a string of applications, some numerical, but one in database querying, one in chess-playing, and explaining the potential of subroutines, stack control, and higher-level languages. We take it for granted now, but in 1945 this 'universality' had a preposterous air.
He saw that in writing programs, anything routine could be left to the machine itself to do: compilers and editors make this obvious now, but it was not obvious in 1945. Why did Turing see so far ahead? The reason lies in1936. The concept of the Turing machine was not arithmetical but logical: it showed how to codify any operation with symbols, not necessarily to do with arithmetic calculations. The whole point of the universal machine was that one machine could any and every such coded task. The coding of tasks was the real focus: Turing regarded his hardware design as full of details which were forced on him by the limited nature of storage available in 1946, but essentially transitory. (In fact the Pilot ACE, built in 1950 as a modified form of Turing's design, went to the Science Museum in 1958, where you can see it now.) His policy was to make it, try it out and go on to something better, meanwhile getting on with coding 'every known problem', as he explained had to be done.
But Turing failed to get his way. In 1948 he gave up and went off to Manchester University, where his mathematical colleague Newman had funding for a different computer project. Newman knew all about Turing's ideas and had given the idea of stored instructions to the top electronic engineers there, who came from the wartime radar work. The result, in June 1948, was the world's first first demonstration of a stored program — with a store of 1000 bits. Unfortunately for Newman's ideas, their success meant that thereafter at Manchester the electronic engineering dominated everything, no-one asked where the idea of the computer had come from, and the mathematicians' role was forgotten.
Manchester remained a centre for hardware innovation and production, and as such left Turing sidelined. In particular, no-one identified the opportunity to start a British software industry, exploiting the ingenuity and flexibility seen at Bletchley Park. (Perhaps IBM made a similar mistake years later). At Manchester, engineering a computer was real work for real men, but using a computer had the low status of women's work. Turing himself was partly to blame: he neglected the opportunity to develop his own powerful software ideas: these were all lost. He did not do much more than go through the motions of configuring machine code to make the Manchester computer work, and worked purely for his own mathematical research after 1950 — all done by handwritten raw machine code.
One underlying weakness was that, as a1949 government report put it, 'English technology is conceptually in advance of American technology in the field of electronic computers' but 'there is no one firm in England' with 'facilities for large-scale manufacturing...' It was known that IBM had just such facilities, and that the 'initial advantage' might be lost. It duly was, and the rest is history.
There is an interesting question, however, as to whether Turing was doing something more private behind the scenes. When Turing formulated his ACE plan immediately after the war, he certainly saw it as a machine for continuing the wartime codebreaking work. His report explicitly mentioned 'Foreign Office' support — although, in the event, this did not seem to be forthcoming in 1947 when the project foundered. Turing's arguments for building a computer rested on the value of a 'universal' machine which would need no new engineering, only paperwork. As such, this would be a great advance on Bletchley Park days when new cipher problems meant the physical engineering of new machines. Although that was the general principle, however, Turing mentioned in his plan an idea which ran against it. He suggested allowing for special circuits which could be attached for 'doing things simply which could be done lengthily as a [program]'. This, the equivalent of special customised chips, was almost certainly a coded reference to the Enigma problem and how Turing had broken it. Let's go back a bit to look at the Enigma.
The military Enigma is 70 years old, but it's still interesting as a case-study in crypto and computing. One thing that may not be appreciated is that it had the equivalent of about 83 bits of key — quite large enough to defeat brute force search. People sometimes say there was some incredibly small 'chance' of breaking a message — the chance of hitting on the right key for an isolated message. But of course that wasn't how it was broken. Firstly, they did not have isolated messages but a whole slew of related material, enciphered on related keys, which could be usefully combined and compared. The system by which the Enigma operators chose the message keys was pre-printed in code books, and after the famous British captures of U-boats in 1941, this system was known. Secondly, Turing found a flaw in the Enigma design which could be exploited by a brilliant logical idea. The flaw lay in the very particular way in which the standard commercial Enigma had been upgraded for military use in the 1930s: it is one of those critical details in history which could well have been otherwise. The British Typex machine of World War II was also a modification of the basic Enigma, but a much better one, not liable to Turing's attack. Had the technical decisions been the other way round, history might have been very different.
Turing's stunning idea was incorporated in the design of his machine, the British Bombe. This is what he achieved in 1939. It needed a logical genius to think of it, so is actually rather hard to understand, and of course depends on the details of the Enigma, so I won't try to explain it here. You can find a complete specification on www.codesandciphers.org.uk, which has an on-line simulator. Of course a simulation shows that it can be implemented by a computer as a step by step operation, and a modern computer does it very quickly. But it's not actually very natural for programming, because Turing's Bombe worked through a special electrical circuit which checked a certain very complex logical condition immediately. You could say that its efficiency lay in the parallelism of the circuit. A computer equipped with this extra circuit for the specific Enigma problem would be much quicker than one having to execute the method in many steps, and this must be what Turing had in mind when suggesting this exception to his general point about the virtue of the universal machine in which no such hardware changes need be made.
Talk of 'parallelism' may seem surprising if you think of 'parallel computing' as something new. But in pre-computer days, ingenious parallel methods were essential and natural. For example, a very effective codebreaking method lay in putting punched cards against each other to see where they matched. A search for matching positions can of course be programmed by a serial process, but the eye somehow seems naturally to see the matches all at once. Turing's special circuit for the Bombe was an ingenious analogue of such immediate vision. People often think that nowadays you would just break Enigma messages by 'putting them on a computer.' But searching through all the possible keys for a message would be very slow and inefficient. Finding an ingenious program to make a great short-cut would still today be vital. And a present-day programmer would be doing very well indeed to see the ingenious idea that Turing saw in 1939; in fact it might actually be harder now than in 1939 because we are so trained in serial program-writing mode.
This is a lesson that might well apply to other crypto problems. A first lesson of the Enigma is that key-size alone doesn't give a measure of 'strength'. Large key size only implies strength if there is no way of breaking the material which is better than trying out every possibility in turn until you hit the right key. Turing's Bombe did far better on the Enigma than this brute force method, and people have had suspicions of the security of other systems. When the Data Encryption Standard was announced in 1975, suspicion was immediately aroused that the system had some unobvious 'trapdoor' which would allow fast cryptanalysis by the National Security Agency, although no-one seems to have found one. Turing's Bombe is a reminder that the use of ingenious special-purpose chips may greatly shorten codebreaking times from those calculated on the basis of one-at-a-time searching operations.
This little hint of 'compromise' in Turing's 1946 computer plan gives one clue to other developments that Turing may have continued to pursue after his war work. He may well have had many advanced ideas, still kept secret, for although he is most famous for the specific breakthrough into the Enigma, there was much more than this to what he did in the war. Even in 1936, he had ideas for turning the 'Turing machine' into ingenious ciphers, ideas never published. His codebreaking work rested on a concept of information measure, parallel to Shannon's work. (Turing and Shannon met and swapped ideas in the middle of the war). He certainly didn't stop in 1945, for in his 1950 paper, Turing mentioned an idea equivalent to designing a cipher system which is unbreakable even with unlimited chosen plaintext — the modern criterion of security. It's anyone's guess what he was doing for GCHQ between 1948 and 1952, when he lost his security clearance because he was revealed as a homosexual. Possibly he was involved in the 'Venona' attack on Soviet messages, another secret link between the US and UK in the Cold War world. But his secrets were taken to the grave in 1954.
In the 1940s and 1950s encryption was entirely state-dominated, unknown to the public. But in the 1970s the demands of business (US especially) meant that government couldn't keep serious encryption to itself any longer. Now, of course, individuals can be players too, empowered by personal computing, and the real difference from 1939, when Turing did his lateral thinking about Enigma, is that nowadays cryptology is open to worldwide discussion within the scientific and technical community. One thing that has not changed, perhaps, is that politicians and administrators have great difficulty in dealing with questions of any technical complexity or subtlety. Turing was the champion of the techies against the suits in such questions!
It was codebreaking that started Turing's practical computer plan. But it was also codebreaking that kicked off his research programme for Artificial Intelligence, the other thing he has become most famous for. Even in 1941 they had discussions about programmed chessplaying at Bletchley Park. How much would it be possible to automate — and supersede — the actions of the human brain? Turing cited 'cryptography', along with language translation, as a prime example of possible AI applications in 1948. AI was his main focus at this period, and led to his most famous paper in 1950, the one which introduced the 'Turing test' for artificial intelligence.
Perhaps I am a killjoy but there is a case for saying that the test itself is not so great an achievement. It has inspired chatterboxes and Loebner test competitions (see www.loebner.net) and so a lot of public interest in the claims of AI enthusiasts. It's also a full-blooded techie revenge on the Arts, a bold assertion of the claims of science to investigate anything and everything. But the idea of a comparison test of machine and brain is not, in itself, very profound. Turing's 1950 paper had other, deeper, features. One was the precise idea of computation, as discovered in 1936, now giving real substance to the Artificial Intelligence program, as opposed to vague robot science fiction aspirations. The second lay in Turing's constructive proposal for AI research. This was two-pronged, anticipating both top-down approaches like expert systems, and bottom-up neural nets and genetic algorithms. Later on these approaches became deadly rivals, their advocates hardly on speaking terms, but Turing saw them as to be tried together.
But there are some things Turing didn't do. One is the rigorous classification of 'tractable' and 'intractable' problems, the realm of 'complexity theory' since the1970s, for which Turing's fundamental machine concept was a starting-point. Sorting is tractable: factorisation (as yet) is not. Turing had plenty of mathematical stimulation at Manchester which might have led him in this direction, but he did not take it. Another line of development that Turing missed was that of miniaturisation: when giving a discussion of the physical basis of computing in 1948 he assumed that the distance between components would be of the order of a centimetre. Perhaps for this reason, he didn't address a fundamental problem that limits classical computing: the quantum-mechanical nature of electrons which means that when storage is down to the level of an atom, they cannot be thought of as definitely in or out of a location. So-called 'tunnelling' breaks down the reliable 0-or-1 storage on which classical computing depends.
Quantum computing, as it has been developed since the 1980s, exploits the very 'tunnelling' that makes classical computing break down at the atomic level. It uses the 'superposition' principle which means that a particle such as an electron can be in two places at once — or rather, that an electrron is not a 'thing' which can be thought of having location in the way as objects in our ordinary experience. It's a shame Turing didn't go on to this extension of his machine ideas, but it was a fine no-bullshit counterpart of Alan Turing, the American physicist Richard Feynman, who propelled the basic ideas which researchers are now trying to make practical.
A quantum storage unit can store a 0 and a 1 at once; and n quantum storage units can store 2n states. This gives a quantum computer the potential of an exponential speed-up. (Typically, a quantum storage exploits the superposition of particle spin, so that you may say that electronic spin, capable of having it both ways at once, does have a genuine use after all!) The effect can be thought of as like computing in parallel: some people like to think of these parallel operations as taking place in alternative worlds, but it isn't essential to conceptualise it like this. It is not magic: any gain in time will have to be paid for by the cost of extreme accuracy in the engineering of a quantum computer.
In 1994, it was discovered that the theoretical exponential speed-up could be exploited in the problem of factorising large numbers. A quantum computer could turn factorisation into a problem as tractable as sorting. Many communication protocols use public-key systems to encode or give electronic signatures — PGP, for example. But public key depends for its security on the difficulty of factorising the publicly announced number. So it would be vulnerable to a quantum computer large enough to tackle the huge numbers involved. So far, as regards practical prospects, quantum computing technology is still a long way from achieving this, but it is an entirely serious research program.
These are questions Alan Turing never anticipated. And yet, at the end of his life, he did start a fresh look into quantum physics which may turn out in the end to be even more prescient. His investigation was into what is called the 'reduction' or 'measurement' or 'collapse of the wave function' in quantum mechanics — the very mysterious process that connects the superposed both/and world of quantum states into the definite either/or world of macroscopic objects. It probes the question of what 'an electron' really is. Alan Turing had studied quantum mechanics when he was a student, at a time when it was genuinely 'new physics,' and had been puzzled by this issue even then; in this last phase of his life he returned to it. Incidentally, it seems that his interest was motivated by the question of whether quantum mechanics could affect the operation of the human brain, the same question as Roger Penrose opened up in the 1980s in The Emperor's New Mind.
To terminate a quantum computation you have to make a measurement, and this involves the mysterious reduction process. One major problem in quantum computing is that you can't see what is happening inside a computation without terminating it, so you have to know in advance how long the computation will take. But we know (from Turing's own 1936 work) that there can't be any general way of knowing how long a computation will take. This makes quantum computing, as it stands now, more like the addition of a speed-up Bombe to a classical computer, than a complete and independent theory in its own right. It may be that a complete theory will only come from a full understanding of how 'reduction' works and of how the quantum world is related to the macroscopic world we experience.
Meanwhile, it is striking that the very thing quantum computers seem to be best for, fast factorisation, is also the very thing that would make devastating inroads into the commercial use of computers: it would break all the protocols which depend on sending information by public key. There is an echo of Turing's Bombe, which with its advanced design, drawing on Turing's abstruse expertise in logic, broke the German communication system. Mathematicians have often cultivated an above-it-all attitude which infuriates engineers but crypto has shown that there are no firm boundaries between theory and application.
Turing's great 1936 work found an exact mathematical definition of computation, and so an absolute limitation of computability. This apparently very abstruse and theoretical question has recently come more into the news as various people have claimed that there are ways of breaking 'the Turing limit' by quantum computing or some other way. I am sceptical about these: they seem to depend on setting up physically impossible systems with measurements of infinite precision. There is too much spin in announcements of scientific discoveries.
On the other hand there is a genuinely exciting frontier in nanotechnology arising from our ignorance of the physical laws which are at the boundary of 'small' and 'large', 'quantum' and 'classical'. In superconductivity, molecular engineering, maybe even brain physiology, there may yet be surprises at the boundaries between different kinds of science and engineering. Alan Turing never kept to conventional boundaries and the frontiers of quantum and crypto would excite him now as much as anything.
Let's hope it won't take another world war to stimulate the next step.
 Alan Turing Home Page |  Scrapbook: Turing's Computer |
 Turing Sources |  Alan Turing: the Enigma |
My Publications |
Email andrew@synth.co.uk |  My Main Page | |
