Alan Turing First published Mon Jun 3, 2002; substantive revision Mon Aug 27, 2007 By Andrew Hodges Stanford Encyklopedia of Philosophy 4. The Uncomputable Turing turned to the exploration of the uncomputable for his Princeton Ph.D. thesis (1938), which then appeared as Systems of Logic based on Ordinals (Turing 1939). It is generally the view, as expressed by Feferman (1988), that this work was a diversion from the main thrust of his work. But from another angle, as expressed in (Hodges 1997), one can see Turing's development as turning naturally from considering the mind when following a rule, to the action of the mind when not following a rule. In particular this 1938 work considered the mind when seeing the truth of one of Gödel's true but formally unprovable propositions, and hence going beyond rules based on the axioms of the system. As Turing expressed it (Turing 1939, p. 198), there are "formulae, seen intuitively to be correct, but which the Gödel theorem shows are unprovable in the original system." Turing's theory of "ordinal logics" was an attempt to "avoid as far as possible the effects of Gödel's theorem" by studying the effect of adding Gödel sentences as new axioms to create stronger and stronger logics. It did not reach a definitive conclusion. In his investigation, Turing introduced the idea of an "oracle" capable of performing, as if by magic, an uncomputable operation. Turing's oracle cannot be considered as some "black box" component of a new class of machines, to be put on a par with the primitive operations of reading single symbols, as has been suggested by (Copeland 1998). An oracle is infinitely more powerful than anything a modern computer can do, and nothing like an elementary component of a computer. Turing defined "oracle-machines" as Turing machines with an additional configuration in which they "call the oracle" so as to take an uncomputable step. But these oracle-machines are not purely mechanical. They are only partially mechanical, like Turing's choice-machines. Indeed the whole point of the oracle-machine is to explore the realm of what cannot be done by purely mechanical processes. Turing emphasised (Turing 1939, p. 173): We shall not go any further into the nature of this oracle apart from saying that it cannot be a machine. Turing's oracle can be seen simply as a mathematical tool, useful for exploring the mathematics of the uncomputable. The idea of an oracle allows the formulation of questions of relative rather than absolute computability. Thus Turing opened new fields of investigation in mathematical logic. However, there is also a possible interpretation in terms of human cognitive capacity. On this interpretation, the oracle is related to the "intuition" involved in seeing the truth of a Gödel statement. M. H. A. Newman, who introduced Turing to mathematical logic and continued to collaborate with him, wrote in (Newman 1955) that the oracle resembles a mathematician "having an idea", as opposed to using a mechanical method. However, Turing's oracle cannot actually be identified with a human mental faculty. It is too powerful: it immediately supplies the answer as to whether any given Turing machine is "satisfactory," something no human being could do. On the other hand, anyone hoping to see mental "intuition" captured completely by an oracle, must face the difficulty that Turing showed how his argument for the incompleteness of Turing machines could be applied with equal force to oracle-machines (Turing 1939, p. 173). This point has been emphasised by Penrose (1994, p. 380). Newman's comment might better be taken to refer to the different oracle suggested later on (Turing 1939, p. 200), which has the property of recognising "ordinal formulae." One can only safely say that Turing's interest at this time in uncomputable operations appears in the general setting of studying the mental "intuition" of truths which are not established by following mechanical processes (Turing 1939, p. 214ff.). In Turing's presentation, intuition is in practice present in every part of a mathematician's thought, but when mathematical proof is formalised, intuition has an explicit manifestation in those steps where the mathematician sees the truth of a formally unprovable statement. Turing did not offer any suggestion as to what he considered the brain was physically doing in a moment of such "intuition"; indeed the word "brain" did not appear in his writing in this era. This question is of interest because of the views of Penrose (1989, 1990, 1994, 1996) on just this issue: Penrose holds that the ability of the mind to see formally unprovable truths shows that there must be uncomputable physical operations in the brain. It should be noted that there is widespread disagreement about whether the human mind is really seeing the truth of a Gödel sentence; see for instance the discussion in (Penrose 1990) and the reviews following it. However Turing's writing at this period accepted without criticism the concept of intuitive recognition of the truth. It was also at this period that Turing met Wittgenstein, and there is a full record of their 1939 discussions on the foundations of mathematics in (Diamond 1976). To the disappointment of many, there is no record of any discussions between them, verbal or written, on the problem of Mind. In 1939 Turing's various energetic investigations were broken off for war work. This did, however, have the positive feature of leading Turing to turn his universal machine into the practical form of the modern digital computer. Works by Turing 1936, "On computable numbers, with an application to the Entscheidungsproblem", Proc. London Maths. Soc., ser. 2, 42: 230"265; also in Davis 1965 and Gandy and Yates 2001; [Available online]. 1939, "Systems of logic defined by ordinals", Proc. Lond. Math. Soc., Ser. 2, 45: 161"228; also in (Davis 1965) and in (Gandy and Yates 2001). This was Turing's Ph.D. thesis, Princeton University (1938). 1946, Proposed Electronic Calculator, report for National Physical Laboratory, Teddington; published in A. M. Turing's ACE report of 1946 and other papers, B. E. Carpenter and R. W. Doran (eds.), Cambridge, Mass.: MIT Press (1986); also in Collected Works (Volume 1). 1947, "Lecture to the London Mathematical Society on 20 February 1947", in A. M. Turing's ACE report of 1946 and other papers, B. E. Carpenter and R. W. Doran (eds.), Cambridge, Mass.: MIT Press (1986); also in Collected Works (Volume 1). 1948, "Intelligent Machinery", report for National Physical Laboratory, in Machine Intelligence 7, B. Meltzer and D. Michie (eds.) 1969; also in Collected Works (Volume 1). 1950a, Programmers' Handbook for the Manchester Electronic Computer, Manchester University Computing Laboratory. [Available online in PDF]. 1950b, "Computing machinery and intelligence", Mind, 50: 433"460; also in Boden 1990, Collected Works (Volume 1), and [Available online]. 1951, BBC radio talk, in The Essential Turing, B. J. Copeland (ed.), Oxford: Clarendon Press (2004). 1952, "The chemical basis of morphogenesis", Phil. Trans. R. Soc. London B 237: 37"72; also in The Collected Works of A. M. Turing: Morphogenesis, P. T. Saunders (ed.), Amsterdam: North-Holland (1992). The Collected Works of A. M. Turing consists of 4 volumes: Volume 1: Mechanical Intelligence, D.C. Ince (ed.), Amsterdam: North-Holland, 1992. Volume 2: Morphogenesis, P. T. Saunders (ed.), Amsterdam: North-Holland, 1992. Volume 3: Pure Mathematics, J. L. Britton (ed.), Amsterdam: North-Holland, 1992. Volume 4: Mathematical Logic, R. O. Gandy and C. E. M. Yates, Amsterdam: North-Holland, 2001. Secondary Literature Boden, M. (ed.), 1990, The Philosophy of Artificial Intelligence, Oxford: Oxford University Press. Church, A., 1937, Review of Turing 1936"7, Journal of Symbolic Logic, 2: 42. ---, 1940, "On the concept of a random sequence", Bull. Amer. Math. Soc., 46: 130"135. Copeland, B. J., 1998, "Turing's o-machines, Searle, Penrose and the brain", Analysis, 58(2): 128"138. ---, 1999, "A lecture and two radio broadcasts on machine intelligence by Alan Turing", in Machine Intelligence 15, K. Furukawa, D. Michie, and S. Muggleton (eds.), Oxford: Oxford University Press. --- (ed.), 2004, The Essential Turing, Oxford: Clarendon Press. Copeland, B. J. and D. Proudfoot, 1996, "On Alan Turing's anticipation of connectionism", Synthese, 108: 361"377. Davies, E. B., 2001, "Building infinite machines", British Journal for the Philosophy of Science, 52 (4): 671"682. Davis, M., 2000, The Universal Computer, New York: Norton. --- (ed.), 1958, Computability and Unsolvability, New York: McGraw-Hill; New York: Dover (1982). --- (ed.), 1965, The Undecidable, New York: Raven. Dawson, J. W., 1985, Review of Hodges (1983), Journal of Symbolic Logic, 50: 1065"1067. Deutsch, D., 1985, "Quantum theory, the Church-Turing principle and the universal quantum computer", Proc. Roy. Soc. A, 400: 97"115. .....................................................................................................