Uncomputability in the work of Alan Turing and Roger Penrose

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

This text has been written as the version for printed publication of the talk I gave to the forum on Jenseits der Turing-Maschine [Beyond the Turing machine] in Hamburg on 6 October 2000. This forum formed part of the extended series on computer-related topics organised by Interface 5. The meeting was held in the distinguished library of the Warburg Haus. I must express my particular thanks for being invited to give a presentation in English, as regrettably I was unable to participate in the German language.
The talk and following discussion were recorded on video. It is intended that they will become available on-line.	I took this picture with my digital camera and it shows myself photographing the computer screen which is showing the video camera image of myself photographing the computer screen which...
This is not a final text, as I expect it to be revised in accordance with the style and format adopted for the printed publication. Since giving this talk I have also given a similar lecture at Colgate University, New York. This was on 2 February 2001. Another talk on this topic was advertised for 5 February 2001 at Trinity College, Hartford, Conn., but was unfortunately cancelled because of a severe snowstorm. I made another similar presentation at King's College, London University on 16 March 2001, and at the Department of Cognitive Science, University of California, San Diego, on 16 April 2001. This pre-print web-page version has been laid out in three parts: Part 1: Turing from 1936 to 1941 on this page Part 2: Turing from 1941 to 1954 on the next page Part 3: References and notes on the third page

Part 1: Turing from 1936 to 1941

Although (Turing 1950) is probably best known for its formulation of the so-called Turing Test, and its constructive proposals for research in Artificial Intelligence, Turing actually devoted considerable attention to the mathematical groundwork of computability and its applicability to the problem of Mind. Indeed Turing's position at this stage could be summarised as saying that the activities of an intelligent mind must be a computable process. In the course of arguing this position he made an assumption about the material basis of mind which is not quite explicit. This has recently been characterised by Roger Penrose (Penrose 1994, page 21) as follows: 'It seems likely that he [Turing] viewed physical action in general — which would include the action of a human brain — to be always reducible to some kind of Turing-machine action.' Although this goes a little further than Turing's 1950 discussion of the physical basis of the nervous system, I agree that this view is essential to Turing's 1950 arguments.

This Turing thesis marks the essential point on which Penrose parts company from Turing. To summarise Penrose's views: Gödel's theorem tells us that we can see the truth of statements which cannot be proved by the application of a formal system of rules. Using Turing machines, this argument can be put in the form of showing minds able to perform uncomputable operations. Gödel also took this view of the mind's power, but unlike Gödel, Penrose insists on a materialist or physicalist base for mental faculties and deduces that there must be uncomputable elements in physical law which the brain exploits when it performs the uncomput>

Transfer interrupted!

I have presented this argument as if it were one between Turing and Penrose as individuals but of course there is a major difference between the protagonists. Although Turing in his time saw himself as a heretic, virtually the whole of the scientific world now supports his assumptions of mechanizability, whereas Penrose's views (as in Penrose 1989, 1994, 1996) are widely considered (though not by me) to be absurd.

However what I wish to show is that Turing was actually deeply concerned by the very issues later raised by Penrose, and that the development of his thought shows their pervasive influence. We can go to the heart of the issue by looking at the year 1936 itself.

In Alan Turing: the Enigma (Hodges 1983), mapping the development of Turing's thought, I found it necessary to make a strong statement about a change of direction in Turing's thought at the completion of his famous paper in that year. The reason is this: until that point, the young Turing had been most absorbed by the two questions which are essentially in Penrose's direction, i.e. casting doubt on the mechanizability of mind. When he was 20, Turing was so struck by the quantum-mechanical nature of matter and its apparent unpredictability that he wrote privately of how the brain could exploit this, as an explanation of free-will (Hodges 1983, p. 63). This study led Turing to von Neumann's foundations of quantum mechanics, but not to any published work. The publication that later made him famous was, of course, his 1936 formulation of computability. But the main mathematical result of this paper was to demonstrate the limitation of computability, by giving a definitive negative answer to Hilbert's Entscheidungsproblem. Turing showed it possible to give unambiguous definitions of real numbers which are not computable. It is therefore a striking fact, which I pointed out, that in Turing's later work his central thrust is the exploration of how much machines can do, not of what they cannot, culminating in the 1950 position discussed above. In my book I placed this shift at the completion of his paper in 1936. Turing's ground-breaking discovery of the universal machine concept, anticipating the computer, does lend some support to the idea of a shift at this point.

I do not doubt that there was indeed this shift of emphasis and excitement in Turing's work. But in (Hodges 1997) I put forward a modified view in which this shift was less sudden and came rather later: probably in about 1941 while Turing was spearheading the cryptanalysis of German naval signals at Bletchley Park. This change of view sheds a different light on the period between 1936 and 1941 in Turing's thought. I will discuss how it affects first the interpretation of 'intuition' in his 1938 work on 'ordinal logics,' and then the first ideas for machine intelligence that he began to discuss with Bletchley Park colleagues in 1941.

Turing's 1938 Princeton Ph.D. thesis, work conducted in close cooperation with Church, was entitled Systems of logic defined by ordinals, and published as (Turing 1939). Predominantly the work consisted of highly technical developments within mathematical logic. However the driving force lay in the question: what is the consequence of supplementing a formal system with uncomputable deductive steps? In pursuit of this question, Turing introduced the definition of an 'oracle' which can supply on demand the answer to the halting problem for every Turing machine. Turing gave his subject-matter an interpretation which described the mathematician's 'intuition' in theorem-proving, and Newman (1955) effectively identified the uncomputable 'oracle' with intuition. This was perhaps going too far since the 'oracle' is capable of far more than any human being; nevertheless Newman had a unique status as Turing's collaborator at this period and must reflect the tenor of Turing's discussions. In any case, Turing makes it clear that the 'intuition' being discussed is related to the human act of seeing the truth of a formally unprovable Gödel statement. To summarise, it is notable that Turing's 1938 work focussed on the same issue as Penrose now raises: the interpretation of uncomputable deductions.

Turing defined the 'oracle' purely mathematically as an uncomputable function, and said, 'We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine.' The essential point of the oracle is that it performs non-mechanical steps. Turing does not give any physical interpretation, and the word 'brain' is notably absent from the paper. It is not ahistorical to ask what Turing could have imagined the human brain was doing in such a moment of 'seeing', since Turing's youthful writing had shown himself alive to such questions. But we have no idea how he might have answered in this 1938 period. This question is naturally of interest to Penrose, who draws attention to Turing's oracle definition (Penrose 1994, p380ff). But Turing's oracle cannot be identified with the physical effect Penrose needs for his theory of mind. As Penrose points out, intuition can again outdo the oracle. Turing must have been fully aware of this point, since the main content of his paper lies in developing an infinite sequence of more and more powerful logics; the oracle as first defined only takes a first step into the uncomputable and barely scratches the surface of its complexity.

At this point I must digress to describe the recent assertions of the philosopher B. J. Copeland who has made sensational popular claims about Turing's 'oracle' definition and its capacity to revolutionise future computer science. The essential point is that Copeland sees the oracle as the component of a new kind of machine, more powerful than Turing machines; and with his colleague D. Proudfoot chides others for not acknowledging such machines. In their popular article (Copeland and Proudfoot 1999a), a discussion of 'what Turing imagined' is illustrated by a picture of an oracle in a black box, which accordng to the authors might work by measuring the capacitance of an electrical element to any desired number of binary places.

Turing imagined nothing of the sort, and his explicit statement about the oracle should make it clear that he was exploring the world of the non-mechanical. Curiously, in another paper (Copeland 1999b), Copeland has actually omitted the words 'apart from saying that it cannot be a machine' from Turing's statement, quoting him as saying merely 'We shall not go any further into the nature of [an] oracle.' This misreading is perhaps one source of Copeland's confusion. Another source may lie in Turing's definition of an 'oracle-machine' which is a Turing machine allowed at certain points to 'consult the oracle.' Such a machine is not purely mechanical: it is like the 'choice-machine' defined in (Turing 1936-7) which at certain points allows for human choices to be made. Turing used the word 'machine' for entities which are only partially mechanical in operation, reserving the term 'automatic machine' for those which are purely mechanical. Copeland appears to imagine that when Turing describes the oracle-machine definition as giving a 'new type of machine', he is defining a new type of automatic machine. On the contrary, Turing is defining something only partially mechanical.

To take this point further, it is worth noting that the expression 'purely mechanical process' enters into Turing's definitive statement of the Church-Turing thesis, which comes as an opening section to (Turing 1939), and that Turing goes on: 'understanding by a purely mechanical process one which could be carried out by a machine.' In the subsequent discussion the word 'machine' is used to mean 'Turing machine'. There is no evidence that Turing had any concept of a purely mechanical 'machine' of any kind other than encapsulated by the Turing machine definition.

In contrast, Copeland has to argue that Turing had all the time in mind the possibility of (purely mechanical) machines more powerful than the Turing machine, (viz. oracle-machines), and therefore has to claim that Turing's definition of the Turing machine carefully allowed for this possibility. Since the Turing machine is introduced in imitation of a human being working methodically, this leads Copeland to suggest that Turing had in mind the possibility of machines with superhuman ability. In (Copeland 1997) the philosopher explains that 'For among a machine's repertoire of atomic operations there may be those that no human being unaided by machinery can perform.' Although this is not explicitly stated to be Turing's own reasoning, it is given as an explanation of why Turing's definition of computability was made as it was. There is however not a trace of any such idea in Turing's work, as one may readily see from Turing's definitive statement of the Church-Turing thesis (which Copeland omits to cite in his paper on the subject). Another definitive statement comes in Church's review of (Turing 1936-7), in (Church 1937a). Church wrote this while Turing was with him in Princeton in 1937; moreover Church was famously a cautious and careful writer, and later repeated his words in (Church 1940). Thus we should take very seriously his summary of Turing's definition, which was as follows:

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.

This account of the Turing machine, far from carefully restricting the definition to the human worker with explicit instructions, encompasses all finitely defined machines, leaving no scope for imagining machines more powerful. Copeland ignores this crucial statement of Church's interpretation and acceptance of Turing's work, but does cite Church's review of Post's work (Church 1937b) which is on the next page in the same journal. This refers to Turing's definition (as being more satisfactory than Post's), using the expression 'an arbitrary machine.' It is obvious what this means from the immediately preceding review of Turing's paper, but Copeland gives it the most extraordinary and contrived interpretation: he asserts that the expression 'arbitrary machine' refers to the 'arbitrary' aspects of the Turing machine definition. As we shall see, Copeland also attempts to find evidence of 'oracles' as machine operations in Turing's later thinking. However a study of these primary sources makes it perfectly clear what Turing and Church had in mind; and the whole point of the oracle is that it is non-mechanical.

Continue to Part 2