Part 4 of Turing: a natural philosopher  (1997)

Thinking the Uncomputable

This, his most difficult paper, is much less well known than his definition of computability. It is generally regarded as a diversion from his line of thought on computability, computers and the philosophy of mind, and I fell into this assumption in Alan Turing: the Enigma, essentially because I followed Turing's own later standpoint. But I now consider that at the time, Turing saw himself steaming straight ahead with the analysis of the mind, by studying a question complementary to On Computable Numbers. Turing asked in this paper whether it is possible to formalise those actions of the mind which are not those of following a definite method — mental actions one might call creative or original in nature. In particular, Turing focussed on the action of seeing the truth of one of Gödel's unprovable assertions.

Gödel had shown that when we see the truth of an unprovable proposition, we cannot be doing so by following given rules. The rules may be augmented so as to bring this particular proposition into their ambit, but then there will be yet another true proposition that is not captured by the new rules of proof, and so on ad infinitum. The question arises as to to whether there is some higher type of rule which can organise this process of 'Gödelisation.' An ordinal logic is such a rule, based on the theory of ordinal numbers, the very rich and subtle theory of different ways in which an infinite number of entities may be placed in sequence. An ordinal logic turns the idea of 'and so on ad infinitum' into a precise formulation. Turing wrote that: 'The purpose of introducing ordinal logics is to avoid as far as possible the effects of Gödel's theorem.' The uncomputable could not be made computable, but ordinal logics would bring it into as much order as was possible.

Turing's work, in which he proved important (though somewhat negative) results about such logical schemes, founded a new area of mathematical logic. But the motivation, as he himself stated it, was in mental philosophy. As in On Computable Numbers, he was unafraid of using psychological terms, this time the word 'intuition' appearing for the act of recognising the truth of an unprovable Gödel sentence:

Mathematical reasoning may be regarded rather schematically as the combination of two faculties, which we may call intuition and ingenuity. The activity of the intuition consists in making spontaneous judgments which are not the result of conscious trains of reasoning. These judgments are often but by no means invariably correct (leaving aside the question what is meant by 'correct'). Often it is possible to find some other way of verifying the correctness of an intuitive judgment. We may, for instance, judge that all positive integers are uniquely factorizable into primes; a detailed mathematical argument leads to the same result. This argument will also involve intuitive judgments, but they will be less open to criticism than the original judgment about factorization. I shall not attempt to explain this idea of 'intuition' any more explicitly.

The exercise of ingenuity in mathematics consists in aiding the intuition through suitable arrangements of propositions, and perhaps geometrical figure or drawings. It is intended that when these are really well arranged the validity of the intuitive steps which are required cannot seriously be doubted.

In consequence of the impossibility of finding a formal logic which wholly eliminates the necessity of using intuition, we naturally turn to 'non-constructive' systems of logic with which not all the steps in a proof are mechanical, some being intuitive. An example of a non-constructive logic is afforded by any ordinal logic... What properties do we desire a non-constructive logic to have if we are to make use of it for the expression of mathematical proofs? We want it to show quite clearly when a step makes use of intuition, and when it is purely formal. The strain put on the intuition should be a minimum. Most important of all, it must be beyond doubt that the logic shall be adequate for the expression of number-theoretic theorems...

Turing and Wittgenstein

Wittgenstein:... Think of the case of the Liar. It is very queer in a way that this should have puzzled anyone — much more extraordinary than you might think... Because the thing works like this: if a man says 'I am lying' we say that it follows that he is not lying, from which it follows that he is lying and so on. Well, so what? You can go on like that until you are black in the face. Why not? It doesn't matter. ...it is just a useless language-game, and why should anyone be excited?
Turing: What puzzles one is that one usually uses a contradiction as a criterion for having done something wrong. But in this case one cannot find anything done wrong.
W: Yes — and more: nothing has been done wrong, ... where will the harm come?
T: The real harm will not come in unless there is an application, in which a bridge may fall down or something of that sort.
W: ... The question is: Why are people afraid of contradictions? It is easy to understand why they should be afraid of contradictions, etc., outside mathematics. The question is: Why should they be afraid of contradictions inside mathematics? Turing says, 'Because something may go wrong with the application.' But nothing need go wrong. And if something does go wrong — if the bridge breaks down — then your mistake was of the kind of using a wrong natural law. ...
T: You cannot be confident about applying your calculus until you know that there are no hidden contradictions in it.
W: There seems to me an enormous mistake there. ... Suppose I convince Rhees of the paradox of the Liar, and he says, 'I lie, therefore I do not lie, therefore I lie and I do not lie, therefore we have a contradiction, therefore 2 x 2 = 369.' Well, we should not call this 'multiplication,' that is all...
T: Although you do not know that the bridge will fall if there are no contradictions, yet it is almost certain that if there are contradictions it will go wrong somewhere.
W: But nothing has ever gone wrong that way yet...

Turing's responses reflect mainstream mathematical thought and practice, rather than showing his distinctive characteristics and original ideas. In 1938, it should be noted, he was an untenured research fellow whose first application for a lectureship had failed, and whose chance of a conventional career lay in the mathematics studied and taught at Cambridge. His work in logic was but a part of his output, by no means well known. His Fellowship was for work in probability theory; his papers were in analysis and algebra. That year, he made a significant step in the analysis of the Riemann zeta-function, a topic in complex analysis and number theory at the heart of classical pure mathematics.

Getting statements free from contradictions is the very essence of mathematics. Turing perhaps thought Wittgenstein did not take seriously enough the unobvious and difficult questions that had arisen in the attempt to formalize mathematics; Wittgenstein thought Turing did not take seriously the question of why one should want to formalize mathematics at all.

There are no letters or notes which indicate subsequent contact between Turing and Wittgenstein, and no evidence that Wittgenstein influenced Turing's concept of machines or mind. If influence in the next ten years is sought, it should be found in the Second World War and Turing's amazing part in it.

[5] Systems of logic based on ordinals, Proc. Lond. Math. Soc (2) 45 pp 161-228 (1939).
This was also Turing's Princeton Ph.D. thesis (1938). (See also the Bibliography on this site.)
[6] C. Diamond (ed.) Wittgenstein's Lectures on the Foundations of Mathematics (Harvester Prerss, 1976). The quoted dialogue is extracted from lectures 21 and 22.

© 1997, Andrew Hodges.

CONTINUE to part 5

Quick Links: