Philosophy Area

What would Alan Turing have done after 1954? Lecture at the Turing Day, Lausanne, 2002 by Andrew Hodges

On 28 June 2002 I spoke at the Turing Day at the Swiss Federal Institute of Technology, Lausanne (EPFL), celebrating the 90th anniversary of Alan Turing's birth. My lecture was on the impossibly counterfactual question: 'What would Alan Turing have done after 1954?'
This photo shows the distinguished mathematical logician Martin Davis at lunch, and to his right, Craig Webster. Martin Davis was the first speaker of the day, and I was the last. The Turing Day site gives the full programme of speakers.
The text below comes from my speaking notes and from the transparencies that I showed. It contains references to the talks given earlier in the day, notably those of Martin Davis (left), Christof Teuscher (third from left), Jonathan Swinton (fourth from left), B. J. Copeland (fourth from right), and Tony Sale (third from right). Douglas Hofstadter was, unfortunately, absent from this early-morning roll-call. I was wearing a Turing '90 tee-shirt left over from the Turing 1990 conference at Sussex University! Photo: Alain Herzog, EPFL. There are more photographs of the event on the Turing Day site. A more formal version of these remarks appeared in the volume Alan Turing: life and legacy of a great thinker, ed. C. Teuscher (Springer, 2004). For this volume I have also written a short introductory biography of Alan Turing, also available on this website. My talk was featured in the distinguished Swiss newspaper, the Neue Zürcher Zeitung, on 26 July 2002. This was because of the material which appears in Part 2 of this web-presentation, strongly criticising B. J. Copeland's interpretation of Turing's 'oracle'. The NZZ reporter also drew upon on this website, including my remark about a possible 'April Fool' on this page. The report (in German) is not in the NZZ's own on-line archive but is available in pdf form here. Douglas Hofstadter, who was interviewed for this report, contributed further to this criticism. See also Jonathan Swinton's letter headed 'Complex Rubbish' in The Guardian, 5 May 2003, on the relation between Turing, morphogenesis and complexity theory.

Alan Turing at the end of his (real) life

In 1946, at 34, Alan Turing's head was full of the greatest Anglo-American secrets of the war, and full of plans for the computer of the future. But he died on 7 June 1954 at the age of 41. It is an unanswerable question as to what he would have done if he had lived. His life was full of surprises at every turn, and was unpredictable. But I shall use this counterfactual theme to discuss what he was doing and thinking at his death in 1954, and to survey some other unfinished threads in his life.

This last phase of his life has been dramatised in the play and TV film Breaking the Code. It began with his arrest on the first day of Queen Elizabeth's reign, 7 February 1952 (this is my contribution to the current Golden Jubilee celebrations!) It was notable for his holidays abroad in 1952 and 1953 which, as he explained, were to escape the English law.

Here I showed a page of Turing's 'Ibsen5' machine-code program, as on this Scrapbook Page. I referred to the talk earlier in the day where Jonathan Swinton had illustrated Alan Turing's morphogenesis work with some of his Manchester machine-code programming. He had shown a page of KJELL theory, explaining that this was a reference to Turing's Norwegian holiday in 1952 and the young man he met there.

Breaking the machine code: IBSEN was just another Norwegian allusion. The choice of Norway was in fact Alan Turing's response to news of the first open European gay movement in Scandinavia, twenty years ahead of his time as usual. In March 1953, Kjell tried to visit him in Manchester, and this caused a second major crisis for Turing with the police keeping watch on him. This doesn't surprise me, because he had so much top-secret knowledge at the height of the cold war. We do not know how matters developed between then and his death on 7 June 1954, and this period remains full of mystery.

Where his theory of life might have led

• A connection with von Neumann's ideas for discrete self-organising systems, usually considered as the foundation of 'artificial life.'
• The decoding of DNA in 1953 — here I referred to what Douglas Hofstadter had said in his talk about the fascination of DNA programming.
• It was through numerical simulations of non-linear equations, made possible by the computer, that chaotic phenomena became accessible to investigation in the 1950s. It seems quite possible to me that he would have seen the nature of chaos a lot quicker than other people did.

Word problems

He explained a 'word problem' in terms of a problem in knot theory. This illustration itself pointed to another fascinating and growing area in post-war mathematics, and also reflected the more geometrical turn of his interests. The 1954 article went on to explain Gödel's theorem This was perhaps the first popular article on the subject, which was not at all well known in those days. (Douglas Hofstadter's Gödel, Escher, Bach did not appear until 25 years later!) So this article also suggests another role that a longer-lived Alan Turing might have taken — a great communicator of mathematics and science to a wide audience.

Computer Science and Machine Intelligence

I always hoped he would return one day to the practical problems of making a machine learn. There should be somewhere a copy of the report he wrote on this after his sabbatical year at Cambridge from the NPL.

Now, the report he wrote for the NPL, Intelligent Machinery, is the basis for the work which has brought us all here today, thanks to Christof Teuscher! I'm sure there will be more to come, extending the exploration of Turing's models.

The computer scientist John McCarthy would have invited Turing to Dartmouth College in 1956, for what is wrongly thought of as the conference that began Artificial Intelligence. What would Turing have said? Well, I hope he would have been living witness to the fact that Artificial Intelligence had started well before 1956, as Prof. Copeland rightly said in his talk. I like also to think he would have advocated avoiding the separation of 'top-down' from 'bottom-up' research that was in fact to develop so strongly for the next 30 years (as Christof Teuscher brought out so clearly in his talk.) In contrast, Turing in 1948 and again in 1950 described both approaches together, saying that both approaches should be tried.

But it is worth noting Gandy's message that Turing had shown little interest in pursuing this work. And I'm not sure he would have accepted the invitation to Dartmouth College. He didn't like conferences much! But he would have enjoyed THIS one, I assured the audience, with quite enough handome young men to please him... he wouldn't have changed at 90...

When he had the 1951 Manchester computer at his disposal, he had not used it to follow up his bottom-up ideas on networks, nor his top-down ideas on chess-playing. So it is by no means obvious that a longer life would have led him to continue with AI research. He seemed to prefer to leave it to others.

The same goes for his ideas for programming theory. It is very striking that he continued to write raw machine code for the Manchester machine, although he of all people knew that the machine itself could have been made to do the routine work. In 1946, years ahead of others, he had seen the potential of the stored program for interpreters, compilers and scripts:

The process of constructing instruction table should be very fascinating. There need be no real danger of it ever becoming a drudge, for any processes that are quite mechanical may be turned over to the machine itself.

In 1947 he explicitly recognised the general nature of programming languages.

...one could communicate with these machines in any language provided it was an exact language, i.e. in principle one should be able to communicate in any symbolic logic, provided that the machine were given instruction tables which would allow it to interpret that logical system.

In 1950 his M.Sc. student Audrey Bates worked on putting a small part of Church's lambda-calculus in a form where it could be mechanised by the Manchester computer. This is a small snippet of her thesis:

This work could have led to LISP programming, which was also inspired by the lambda-calculus, but he never followed it up. The same is true of the work he did on program proofs in 1949; this was never taken up and had to wait for others in the 1960s.

He preferred making the first attack at a new idea and then leaving details to others. Of course, Christof Teuscher knows there may be an enormous amount of work in sorting out such so-called details!

To speculate a little more wildly, there is another obvious arena where his knowledge of mathematical logic might have been brought into practical computer science: this is what we have known as complexity theory since the 1970s.

Tony Sale's talk showed how practical time constraints on algorithmic solutions formed a vital aspect of Turing's wartime work. It seems quite possible to me that he was consulted by GCHQ after 1948 about the use of computers for large-scale problems, such as the famous Venona problem of Soviet messages which was the top Anglo-American priority in that period. If so it is quite possible that researches in large-scale efficient computer-based searching and sorting would have brought him to complexity-theory ideas.

Artistic break I took a break here with something more picturesque, showing the fine print by the young Texan artist Jin Wicked. You can see it on this Scrapbook Page. You might see some debt to Escher in her style as well as Gödel in the background! She has illustrated the Turing machine scanned by a head — a human head, Alan Turing's head, the eyes turned inwards and looking with the Mind's I. Notice the tape running off to Andromeda, and at the other end, his schoolboy pencil marking the squares, exactly his own image in On Computable Numbers. There is his old school, and his old school tie, and then behind the scenes, the formulas of complexity theory that he might have done.

Probability and cryptology I'm now turning back to another thought about Turing's wartime work, which mainly lay in probability theory and Bayesian statistics. Afterwards he left it to Jack Good to write up a civilian version of his theory, and he made no effort to pursue the parallel of his work with Shannon's information theory. But possibly he would one day have gone on to combine his knowledge of computation and probability: in particular he had left the concept of randomness oddly informal. He described machines 'with random elements' but this was left to Shannon and others in 1956 work to define properly. Incidentally, the whole 1956 volume of Automata Studies in which this appears was bulging with the development of Turing-related ideas, including an article by Martin Davis. It gives a vivid picture of how, at this high level, Turing's work was continuing full of life in the 1950s. Looking further ahead, the ideas of Gregory Chaitin on randomness and computability give a picture of a field Turing might have opened — even if not necessarily agreeing with all Chaitin's views. Another related topic, where Max Newman certainly had very advanced ideas in 1951, was in the use of probabilistic methods in algebra and number theory. Probabilistic primality testing, as used in public-key cryptology today, might have been working much earlier in Turing's hands. He might also have made powerful advances in cryptology itself. It is striking how he made general statements about this field, and we do not know where his thoughts were leading. Turing's 1936 letter to his mother from Princeton: I have just discovered a possible application of the kind of thing I am working on at present. It answers the question 'What is the most general kind of code or cipher possible', and at the same time (rather naturally) enables me to construct a lot of particular and interesting codes. What was the answer? What were the codes? Turing's 1937-8 cryptological work as reported (accurately?) to me by Dr Malcolm McPhail in 1978: ... he would multiply the number corresponding to a specific message by a horrendously long but secret number and transmit the product. The length of the secret number was determined by the requirement that it should take 100 Germans working eight hours a day on desk calculators 100 years to discover the secret factor by routine search. Turing actually designed an electric multiplier... What was it? (multiplication is too simple). What was his theory of its security? Turing's famous 1950 paper: I have set up on the Manchester computer a small programme using only 1000 units of storage, whereby the machine supplied with one sixteen figure number replies with another... I would defy anyone to learn from these values sufficient about the programme to be able to predict any replies to untried values. In the paper this plays the role of showing how a computable process — in fact a small program — can be totally surprising, thus making a point about the mechanizability of the brain. But read another way it is a claim to a cipher system unbreakable even with chosen plaintext — the modern criterion of security. Once again we can only speculate on what he was doing for GCHQ, and why GCHQ had tried to get him back to work full-time, until his 1952 exclusion. What might have he done if political establishment had treated him differently? Would his effect on the cold war history of 1954 have been as significant as it was on the Atlantic war of 1944? Both were great wars of information and intelligence.

Science fiction break I took another break here for a science-fiction story by the writer Greg Egan, first published in Asimov's Science Fiction in 2000. The whole story is on-line here. It starts on a political line, what might have happened if Alan Turing had been treated differently by his rulers, and has all sorts of imaginative elements, including a dialogue with the theologian C. S. Lewis. But it goes on to focus on scientific advances by and around a counter-factual Turing of the late 1950s. An important point is that it correctly introduces an interest in fundamental physics. The story is called Oracle, a reference to the uncomputable oracle of Turing's 1939 paper. In this excerpt another character makes a rough link of the oracle with time travel. ...'Time travel,' Helen said, 'gives me the chance to become an Oracle. There's a way to exploit the inability to change your own past, a way to squeeze an infinite number of timelike paths — none of them closed, but some of them arbitrarily near it — into a finite physical system. Once you do that, you can solve the halting problem... The author carefully says that all this is 'fanciful,' and so it is. But I think it is a very thoughtful attempt to express the idea that getting an infinite amount of information into a finite physical system is of just that order of difficulty!