What would Alan Turing have done...

www.turing.org.uk/philosophy/lausanne2.html What would Alan Turing have done...

What would Alan Turing have done after 1954?

Lecture at the Turing Day, Lausanne, 2002
by Andrew Hodges

On 28 June 2002 I concluded the Turing Day at the Swiss Federal Institute of Technology, Lausanne (EPFL), with a lecture on 'What would Alan Turing have done after 1954?' These are my speaking notes.

This is Part 2 of the lecture. Go to the preceding page for Part 1.

Copeland's thesis

This brings me naturally to Prof. Copeland's influential views on what Turing would have done, because he has also raised the prospect of building oracle-machines — not as science fiction, but as a serious possibility for future technology!

I agree with Prof. Copeland in a very general sense: the physical world should not be assumed computable without investigation. Greg Chaitin made this point twenty years ago and no doubt many others have too. However I do not generally agree with where he has located possibilities for uncomputable physical effects in Turing's ideas. This is not just a matter of chasing arguments about what the word 'machine' means. It is about serious money! Prof. Copeland has asserted the possibility of a new industry: hyper-computation. If Turing's name backed this possibility, that would give it much greater credibility.

Prof. Copeland wrote in the Times Literary Supplement in 1998

Taking their cue from Turing's 1939 paper, a small but growing international group of researchers is interested in the possibility of constructing machines capable of computing more than the universal Turing machine... research in this direction could lead to the biggest change computing has seen since 1948. Hodges's Turing would regard their work as a search for the impossible. We suspect that the real Turing would think differently.

By machines capable of computing more than the universal Turing machine, I understand the 'oracle-machines' which Prof. Copeland described in terms of infinite-precision measurements in his 1999 Scientific American article. Note: This had been discussed by Martin Davis in his opening talk. See also this page. The reference to 1948 (the first working stored-program computer, giving rise to the IT industry of today) shows the economic seriousness of what he has in mind.

What is the difference between Prof. Copeland's 'real' Turing and 'my' Turing? I had written in Alan Turing: the enigma, summarising what Turing had achieved in 1936:

Alan... had discovered... a universal machine that could take over the work of any machine...

Prof. Copeland claims that I erred in writing 'machine' rather than specifically 'Turing machine' when saying that a universal machine could do the work of any machine. This is because:

Turing himself described abstract machines whose mathematical abilities exceed those of the universal Turing machine (in a ground-breaking paper published in 1939).

Prof. Copeland criticises the same sentence, for the same reason, in his article in the Journal of Philosophy (2000), and there says that I express a 'common view.' I do indeed! My statement about machines was in entirely respectable company: it reflected the description of Turing's work that Church himself gave in 1937. Church characterised computable functions, when introducing them to the world in the Journal of Symbolic Logic, as those that could be performed by machines. You will already have seen this in Martin Davis's talk, but I will show it again because of its significance for Prof. Copeland's thesis:

The author [i.e. Turing] proposes as a criterion that an infinite sequence of digits 0 and 1 be "computable" that it shall be possible to devise a computing machine, occupying a finite space and with working parts of finite size, which will write down the sequence to any desired number of terms if allowed to run for a sufficiently long time. As a matter of convenience, certain further restrictions are imposed on the character of the machine, but these are of such a nature as obviously to cause no loss of generality — in particular, a human calculator, provided with pencil and paper and explicit instructions, can be regarded as a kind of Turing machine.

Thus, Church drew no distinct line between the concepts of a human being following a rule, and the action of a finite machine. And Church offered no hint of speculation about machines that could exceed the power of Turing machines.

Church was supervising Turing's Ph.D. at Princeton when he wrote this review, so I cannot believe he made this statement lightly or in ignorance of Turing's views. He was always very careful. Also he repeated it in 1940 when he knew all about Turing's oracles! So, I think the sentence in my book was a fair reflection of Turing's own world-view in 1936.

Now we must ask: why did Church not mention Turing's abstract 'oracle-machines' when equating the scope of computability with the scope of machines?

Turing's 'oracle-machines' were defined for the purpose of exploring the uncomputable withing mathematical logic. They were defined by a generalisation of the concept of 'machine' to something that is only partly mechanical. The oracle formalises non-mechanical steps, which can be compared with 'intuition'. Turing wrote:

We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine.

There is a precedent: the 'choice-machines' defined by Turing in 1936, which ask for a human operator's decisions. These also are only partly mechanical. Turing gave no suggestion whatever that it might be possible to 'construct' something which by its nature is not a machine. So there is nothing in Turing's 1939 paper to justify Prof. Copeland's sensational technological and economic prospectus.

Nor is there in Turing's later work. When Turing in 1948 gave a full account of 'machines' in generality, oracles never appeared in his analysis. We can also look again at the letter that Robin Gandy wrote to Newman in 1954. Prof. Copeland has cited this as evidence that Turing thought his 1939 ideas had been overlooked. Indeed he did, but the full quotation shows he was referring to his ideas for advanced developments in pure mathematical logic. He suggested nothing to do with seeing oracles as possible hypermachines.

As a further point, Robin Gandy later took up a more formal analysis of the 'machine' concept in 1980. His results support Church's view above, that 'mechanical' implies 'computable.' What's more, Gandy, as Turing's disciple, never even considered counting an 'oracle' as a kind of machine.

Turing's whole thrust after the war was towards saying that the action of the brain must be computable. I have already referred to how he used a cipher system — a pseudo-random program — to exemplify how a machine can create a 'surprise'. But in fact his 1950 argument is not merely all within the scope of computable functions. He argued that a totally finite machine (with a fixed finite store) would suffice to simulate the finite brain. In fact, in that cipher-based example Turing emphasised how small a store was needed to create the effect of a 'surprise'. This point leads me to make a further defence against Prof. Copeland's attack on my work, which he made both in the Times Literary Supplement and the Journal of Philosophy, 2000. Here he asserted that I had overlooked references to uncomputable operations in Turing (1950):

An example of a discrete-state machine whose behavior cannot be calculated by a universal Turing machine is a digital computer with an infinite-capacity store and what Turing calls a 'random element' (pp. 438-439)

My comments:

Not at all: inspection of Turing's words shows that the 'infinite store' just corresponds to allowing an unbounded tape. It is the arena within which computable operations are defined, not something going beyond computability.

As for the 'random element', Turing specifically gives a pseudo-random (computable) illustration of it, namely the digits of π.

Professor Copeland continues:

Hodges... fails to include the crucial words "discrete state machines... can be described by such tables provided they have only a finite number of possible states."

My comment:

This qualification of 'finitely many states' isn't crucial at all. In his 1950 paper Turing gives a discussion based on totally finite machines, which don't use any tape; the states of the tape are absorbed into the states of the machine. The quoted condition is the condition on a process to be representable by a tapeless machine. This is a much more restrictive condition than computability. (A Turing machine has only finitely many configurations, but in general has an unbounded number of possible states of its tape.) So this condition doesn't even hint at uncomputable functions.

Comic Strip Break

At this point I offered the audience some welcome relief from academic argument by showing some pages from a Japanese comic-strip version of the Alan Turing story. I started with the drawings depicting the Turing Test (not, I pointed out, to be mistaken for a Chinese Room!). These were a bit dull, so inspired by Tony Sale's mention of the early 'comic strip' method of breaking Enigma ciphers, I showed the more dramatic pictures which claimed to illustrate what Turing did at Bletchley Park. As further excuse for this excursus, I said that at least they reminded us of Turing's always practical attitude to machines!

Computability and Physics

More seriously now, I come to the physics that I think the most telling and novel aspect of what Turing had started to do and where he might have gone on to far more. Here I must acknowledge Prof. Copeland more positively. Recently he published the script of Turing's 1951 BBC radio talk. This talk mostly shadowed the 1950 paper but, as he pointed out, had a significant difference. It had a mention of quantum mechanics. It was introduced specifically as a loophole in Turing's otherwise general argument that the action of the brain must be computable. Turing explained that for this argument it is

necessary that this machine [the brain] should be of the sort whose behaviour is in principle predictable by calculation. We certainly do not know how any such calculation should be done, and it was even argued by Sir Arthur Eddington that on account of the indeterminacy principle in quantum mechanics no such prediction is even theoretically possible.

In my view this is the only sentence in all Turing's work that points in the direction of something physical that may not be reducible to Turing machines. But it is a significant one. It goes against what Turing had said about simulating the nervous system in 1950. And here, exceptionally, Turing does not appeal to pseudo-random simulation as a satisfactory account of 'randomness'.

This is nothing whatever to do with oracles; there is no mention whatever of infinite information sources in here. The question raised by Turing is to do with the foundations of physics: is the world of quantum mechanical processes, with its so-called Heisenberg Uncertainty principle, compatible with a deterministic Turing machine model?

This sentence, taken seriously, makes a link between computability of mind, and Turing's late work in physics. Although I described this late physics work in my book, and noted Turing's harking back to Eddington, I hadn't seen the importance of this possible connection between fundamental physics and the question of computability of Mind. To describe this late work of 1953-54, let's turn again to Robin Gandy's June 1954 letter to Newman:

During this spring he spent some time inventing a new quantum mechanics... it did show him at his most lively and inventive; he said 'Quantum mechanists always seem to require infinitely many dimensions; I don't think I can cope with so many, I'm going to have about 100 or so — that ought to be enough don't you think?' Then he produced a slogan 'Description must be non-linear, prediction must be linear.'
A slightly more serious contribution... uses 'the Turing Paradox'; it is easy to show using standard theory that if a system start in an eigenstate of some observable, and measurements are made of that observable N times a second, then, even if the state is not a stationary one, the probability that the system will be in the same state after, say, 1 second, tends to one as N tends to infinity; i.e. that continual observation will prevent motion....

His 'non-linear' description in quantum mechanics meant some essentially new theory, and the word 'measurement' focusses on where he thought the problem lay. Turing was referring here to the puzzle of the reduction, collapse, or measurement process in quantum mechanics. No-one even now can say when or how it occurs — as Turing was pointing out with his Paradox.

Quantum mechanics was not new to Alan Turing. His interest went back to 1928. Then he had read Eddington, with Christopher Morcom his beloved school-friend.

In fact Alan Turing was one of the first serious readers in 1932 of von Neumann's 1932 book on the Mathematical Foundations of Quantum Mechanics. It was his school prize book — given after Christopher Morcom had suddenly died in 1930.

Von Neumann's axioms distinguished the U (unitary evolution) and R (reduction) parts of quantum mechanics.

I suggest Turing might have developed quantum computing. Now, quantum computing so far (Feynman, Deutsch, Shor etc) is based on the U process and so computable. It has not made much serious use of the R process: the unpredictable 'random' element that comes in with reduction, measurement, collapse of wave function. And it is the R process that has intrigued Turing here.

But quite recently quantum-computation people have begun studying the R process more closely. The R process is used less trivially in quantum cryptography, teleporting (recently in the news) and in the very striking idea of quantum non-interactive testing of classical structures, sometimes dramatised as 'bomb-testing.'

At this point I showed the diagram accompanying an article in New Scientist, 2 May 1998, about the work of my colleague the quantum computationalist Richard Jozsa. This showed a classical beam-splitting set-up, so showing the different roles of U and R in a quantum process. I briefly indicated, without going through the theory, how Elitzur and Vaidmann (1993) had shown that the slightly more complex logic of 'reduction,' as introduced into the experiment illustrated in this picture, could produce an extraordinary result.

If a 'live bomb' is a device which an effects 'measurement' or 'reduction', whilst a 'dud bomb' does not, you can sometimes tell, by testing the final state of a photon, that it must have been a live bomb even though it has not exploded! Classically, you could never test between live and dud without setting it off! This shows, incidentally, that quantum mechanics should not necessarily be thought of as introducing uncertainty into a classical picture: in this set-up it means that you can probe with certainty a counterfactual story — what would have happened if the photon had hit the detonator of the live bomb. The logical structure here is no different from that known to von Neumann in 1932, but modern technology with perfect mirrors and the detection of single photons makes it possible to investigate that logic far more stringently. In particular, Anton Zeilinger and co-workers in Vienna are conducting ingenious experiments designed to test the limits of the U and R rules.

These 1990s topics give a picture of where Turing might, perhaps earlier in the twentieth century, have thought of radical new ideas! They don't get inside the R process and explain when, how, and indeed if it actually happens, which Turing was probably trying to do. But they are probing at the logic of quantum mechanics in a way that I think would have fascinated him.

A bright young 22-year-old may yet suggest new ways of testing the different theories of what the 'reduction' process is really about. Alan Turing would have loved to see a young mathematician make a breakthrough like that today, as he himself did with the Turing-machine definition. Maybe there is someone here now who will!

Turing was probably trying to make quantum mechanics fully predictable, which no-one has been able to do. Perhaps also, as Gandy hinted in his note, more finite. That would fill in the loophole in his argument about mechanising thought. If so, it was in a sense the opposite of Penrose's view in The Emperor's New Mind. Penrose argues that the R process must be uncomputable because thought cannot be mechanised — as follows from taking a very strong view of the implications of Gödel's theorem. But, I think Turing is on common ground with Penrose in taking quantum mechanics and Gödel's theorem seriously in discussing Artificial Intelligence and the brain, and in saying that these questions must be resolved to get a satisfactory theory of mind and machines.

These are open questions now, almost as open as in 1932, when Alan Turing was 20 and wrote his first ideas about the mind:

Here I showed Alan Turing's youthful essay 'Nature of Spirit', as on this Scrapbook page, picking out the words

It used to be supposed in Science that if everything was known about the Universe at any particular moment then we can predict what it will be all through the future... More modern science however has come to the conclusion that when we are dealing the atoms and electrons... We have a will which is able to determine the action of atoms probably in a small portion of the brain...

'Modern physics' means quantum mechanics, as learnt from Eddington. At that stage, he thought of there being some unknown quantum mechanical law which accounted for the action of human Will. Presumably he changed his mind, since the emphasis of all his post-war work was so strongly towards eliminating such concepts as Will and consciousness. But who knows what he might have gone on to think after 1954? As a human being, he actually took his own will and consciousness very seriously, and this is one of the great paradoxes of his life. In his last years, as I suggested at the beginning of this talk, he insisted on his individuality and his freedom.

In my view there is still a mystery to the connections of logical and physical, quantum and classical, mind and brain. Alan Turing found his greatest strength when confronting the interfaces between conventional compartments of scientific thought, and might have come up with something that no-one could possibly have predicted.

Back to Part 1 of the lecture.