Uncomputability in the work of Alan Turing and Roger Penrose

a talk given by Andrew Hodges
for Interface 5, Hamburg, 6 October 2000

This pre-print web-page version has been laid out in three parts: Part 1: Turing from 1936 to 1941 on the previous page Part 2: Turing from 1941 to 1954 on this page Part 3: References and notes on the third page

Part 2: Turing from 1941 to 1954

From 1941 onwards Turing began to speak of such ideas to his Bletchley Park colleagues, and also to use the word brain (Hodges 1983 p. 210ff). I suggest that having confronted the problem of how the physical brain could support the appearances of a non-mechanical 'intuition,' Turing concluded that the function of the brain was that of a machine, but one so complex that it could have the appearance of not following any rule. From this point Turing apparently became gripped by the potential of computability, and of his own discovery that all computable operations can be implemented on a single, universal, machine.

Thus, in this view it was during the war that Turing formulated both his central contribution to cognitive science and the practical prospect of a universal machine — the modern computer. We can see this from his emergence from wartime duties in 1945, when he proposed his own independent design (Turing 1946) of what he called a 'practical universal computing machine.' (For a new account of the origin of the modern electronic stored-program computer, which credits Turing with giving von Neumann the central idea, see (Davis 2000).) Although Turing promoted the practical benefits of a computer, it was more the prospect of using it to simulate the brain that engaged him from the start. Thus in (Turing 1946) he gave a statement about the prospect of a machine showing intelligence in chess-playing. It refers to mistakes in chess-playing, which, as expanded in later papers, betrays Turing's concern to resolve the problem of how minds can see the truth of Gödel sentences. His post-war argument is that humans make mistakes, machines make mistakes, they are on a par, and that once infallibility is off the agenda, the Gödel argument does not apply.

These remarks are to my mind evidence of how the post-war Turing, even in a technical report, felt obliged to respond to the implications of Gödel's work and his own 1938/9 discussion of 'intuition.' It was not long before Turing (1948) described the problem of 'intelligent machinery' as that of how to create machines with 'initiative.' This is not the same word as the 'intuition' of 1938/9 but has the same role as describing that what the mind does when not following any apparent rule. In Turing's postwar thought, initiative does not need uncomputable steps; it is as computable as the 'mechanical processes' even though this goes against one's expectations of 'machines.' It is merely necessary to widen the scope away from computations that follow a programmer's explicit plan. To this purpose Turing sketched nets of logical elements which he proposed could have the capacity for training and adaptation by indirect means, rather than by explicit functional design. Copeland and Proudfoot, here on rather firmer ground, have offered an account of this work on logical nets (Copeland and Proudfoot 1996).

The climate of computer science is now more favourable to Turing's viewpoint than it was before 1990. Until then advanced programming and connectionism were seen as rival approaches, but now it is more possible to see them, as Turing did, as avenues for research in machine intelligence to be used in combination. Thus Turing's ideas have a surprisingly modern flavour, just as his expression 'genetical search' anticipates the GA approach. Such implicit rather than explicit algorithms are sometimes called, confusingly, non-algorithmic; but the confusion is an echo of the view I now see Turing arriving at in about 1941, when he decided that apparent acts of uncomputable intuition and originality must in fact be accounted for by computable processes.

In this 1948 work Turing for the first time gives a classification of machines, now expanding the concept by distinguishing Turing machines as discrete and logically 'controlling,' as opposed to continuous or physically 'active.' Turing gave a little discussion of the physical embodiment of Turing machines, but without mentioning quantum mechanics. Likewise Turing's discussion of the continuous nature of physical systems, the brain in particular, was also cursory. However this very brevity is what suggests that Turing was readily assuming, as Penrose says, that physical action can be represented by a computable process.

There is of course no mention of oracles in this classification, since the oracle is not a machine. Copeland (1999b) claims that Turing refers to oracles through his discussion of random elements in a machine. Copeland states that Turing described 'a Turing machine to which such an oracle is attached' as a partially random machine. But Turing did not: this connection is never made in his work. In fact his examples give the clear impression that the use of pseudo-random sequences which are explicitly computable (e.g. the digits of π) would do just as well.

But 1950 is not quite the end of Turing's thought on machines and minds. Copeland has also recently performed the useful service of publishing the radio broadcast made by Turing (1951), unfortunately omitted from the Collected Works, and in a preface (Copeland 1999b) correctly draws attention to a comment of Turing about the question of whether brains can be seen as machines. Turing's remarkable comment suggests that he had given fresh thought to physics since writing the 1948 and 1950 papers. Turing here described the universal machine property, applying it to the brain, but said that its applicability required that the machine whose behaviour is to be imitated '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.'

I described in (Hodges 1983, page 441) how Turing in this curious sentence harked back to his youthful interest in the physics of the brain. Now I would consider more serious analysis needed. The point is that Turing here characterised the problematic status of quantum mechanics. I now see this bare sentence as a very plausible link between his work on computability and the surprising burst of work in physics just before his death. Copeland's identification of unpredictability, randomness and oracles misses this link. As Turing knew so early, it is the reduction or measurement process for which there is no prediction even in principle; the evolution of the wave-function by Schrödinger's equation is predictable. And it is the reduction process which drew his attention when in 1953-4 he pursued his new interest in physics.

It is unlikely that Turing was being drawn to Penrose's view of quantum mechanics as involving an uncomputable element. More probably, he was seeking to reformulate quantum mechanics as a predictable theory. He wrote to his student and colleague Robin Gandy, partly perhaps in jest, 'I'm trying to invent a new Quantum Mechanics but it won't really work. How about coming here next week and making it work for me?' (Turing 1953/4). Gandy reported that he was studying the problem of the 'watched pot paradox' of wave function reduction (Gandy 1954; Hodges 1983, page 495).

Turing's interest in reduction, and the lack of a rule for it, should not be confused with prospect of quantum computation as developed since the 1980s. Quantum computation does not cross the boundary of computability, and moreover depends on the predictability of unitary evolution. Yet the elementary applications of quantum computation, as applied in quantum cryptography, have already led to procedures depending on non-local effects which cannot usefully be formulated as classical algorithms. This is enough to show that logic and physics can no longer be kept apart. In 1983 I used the logical and the physical as an organising principle for the life and work of Alan Turing. But perhaps I did not follow this principle far enough. If we look to Turing for a prophecy of developments beyond the Turing machine, our best bet lies in this late hint that the full discussion of computability requires knowing more about quantum indeterminacy.

It is notable that in his 1951 talk Turing also raised the question of interpreting Gödel's theorem, and with less assertiveness than in 1950 that the problem went away through 'mistakes.' Turing did not draw a connection between Gödel's theorem and quantum mechanics, as Penrose does, but he did point to just these areas as leaving the most awkward questions.

The reason why Penrose concentrates on the interpretation of Gödel's theorem is not always appreciated. It is not because Gödel's theorem is some peak of intellectual refinement. Obviously, few human beings can actually follow the mathematics of Gödel's argument! The point is that all human beings show understanding, and Gödel's work serves to concentrate and purify this concept of 'understanding' in a context free from all the confusing elements posed by the external world, language, emotions, and so forth. Turing does not make this point, but the fact that he insisted on bringing this abstruse material into a popular radio broadcast shows he considered it of general importance, not a mathematician's private anxiety. In his 1938 work, Turing also stressed that 'intuition' was actually involved in all the mental work of mathematics; it was only when the steps were formalized according to Hilbert's progam that the non-formal deductions were exposed explicitly. (Penrose takes this point further, saying that it requires intuition even to know that numbers, rather than formal symbols, are the subject-matter of mathematics.)

Again, therefore, there are important points of similarity between the concerns and approaches of Turing and Penrose. Finally, I suspect that Turing was never completely sure that he had dealt with the problem. In his last paper (Turing 1954), a popular article, he rather lamely described the conclusion of Gödel's theorem as being that formal systems needed to be interpreted with 'common sense.' How to put 'common sense' into a computer is still an unanswered question.

Back to Part 1

Notes and References