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.

.....................................................................................................