Part 11 of Turing: a natural philosopher  (1997)

The Uncomputable Revisited

It will seem that given the initial state of the machine and the input signals it is always possible to predict all future states. This is reminiscent of Laplace's view that from the complete state of the universe at one moment of time, as described by the positions and velocities of all particles, it should be possible to predict all future states. The prediction which we are considering is, however, rather nearer to practicability than that considered by Laplace. The system of the 'universe as a whole' is such that quite small errors in the initial conditions can have an overwhelming effect at a later time. The displacement of a single electron by a billionth of a centimetre at one moment might make the difference between a man being killed by an avalanche a year later, or escaping. It is an essential property of the mechanical systems which we have called 'discrete state machines' that this phenomenon does not occur.

This perhaps needs clarification: Turing means that the small physical displacement of an electron inside a computer will not (except with an extremely small probability) affect the discrete state that the computer is representing. Hence it will not affect the future evolution of the computation.

On this basis, Turing then poses

The Argument from Continuity in the Nervous System: The nervous system is certainly not a discrete-state machine. A small error in the information about the size of a nervous impulse impinging on a neuron, may make a large difference to the size of the outgoing impulse. It may be argued that, this being so, one cannot expect to be able to mimic the behaviour of the nervous system with a discrete-state system.

Turing's following remarks briefly indicate how a digital machine can imitate analogue machines, so that discreteness would be no disadvantage. On this topic, Penrose has reinforced Turing's comment, with the observation that 'avalanche' effects of instability and amplification, nowadays better understood through the analysis of chaos, are to the brain's disadvantage, and no argument against the feasibility of machine intelligence.

But this brings us to Penrose's central objection, which is not to the discreteness of Turing's machine model of the brain, but to its computability. Penrose holds that the function of the brain must have evolved by purely physical processes, but that its behaviour is — in fact must be — uncomputable. Since it cannot be that the laws of Nature are waived for the atoms in the brain, it follows that physical law, which at present is incompletely known, must in general have noncomputable aspects. Penrose sees the key in the as yet unknown rules which govern the reduction of the wave function in quantum mechanics. Turing raises no such possibility, and if we look for a discussion of what physical laws he supposes to underpin the function of the brain, we find a vagueness that is surprising considering Turing's knowledge of applied mathematics and physical theory. Apart from the remark made on E.S.P. (raising the possibility of laws of physics different from those so far known) there is only a comment that 'Even when we consider the actual physical machines instead of the idealised machines, reasonably accurate knowledge of the state at one moment yields reasonably accurate knowledge any number of steps later.' This can be elucidated by reference to his 1948 report: it refers not to quantum mechanics but to uncertainty in classical thermodynamics. The tendency of Turing's argument, though not explicitly stated, is that once the discrete state machine model is arrived at, it does not matter what exactly physical laws are. However, the E.S.P. discussion does implicitly admit that physical law enters into the underlying assumptions. Penrose takes a completely different point of view: to discuss what the mind does, as Turing attempts, it is of prime importance to know the fundamental physical content of mental 'doing.' But fundamental physics is quantum-mechanical and at present not fully known; here according to Penrose must lie a fundamental non-computability in nature, which the brain has evolved to take advantage of.

Quite apart from Penrose's theory, it is unclear how to apply computability to continuous quantities, as Turing must have known since he had to abandon in 1937 his intention of rewriting continuous analysis. The question the computability of physical laws, which are generally expressed as differential equations for continuous variables, remains a loose end in Turing's argument.

With computability now at the forefront, it is worth a further look at the problems of interaction between brain and external world. From Penrose's point of view these are irrelevant. If the physical world is computable, then in principle the world external to a brain can be simulated by a computer, and so all its experiences could be faithfully imitated; hence all interface questions take second place to the question of the computability of physical law. The same view is adopted by the most confident proponents of artifical intelligence, though with the opposite intent: they are happy to conceive of simulating the whole external world as well as a single brain. Turing never suggests doing this, but imagines a machine learning from interaction with the world; here his anxieties are concentrated. Penrose, regarding these problems as irrelevant, focuses attention on those questions of intelligence in which external interaction plays no role, questions in pure mathematics. In Penrose's view the impossibility of mechanical intelligence can be seen within mathematics alone: and this impossibility can be put in terms of Turing's own uncomputable numbers. How did Turing himself deal with this objection?

As I have already suggested, Turing probably decided in the 1941 period that the uncomputable, unprovable and undecidable were irrelevant to the problem of mind. In the 1950 paper, Turing exposes and responds to what he calls 'The mathematical objection,' but his answer is short, and I therefore quote the fuller version he gave in a talk to mathematicians in 1947: [13]

It has for instance been shown that with certain logical systems there can be no machine which will distinguish provable formulae of the system from unprovable, i.e. that there is no test that the machine can apply which will divide propositions certainly into these two classes. Thus if a machine is made for this purpose it must in some cases fail to give an answer. On the other hand if a mathematician is confronted with such a problem he would search around and find new methods of proof, so that he ought to be able to reach a decision about any given formula. This would be the argument. Against it I would say that fair play must be given to the machine. Instead of it sometimes giving no answer we could arrange that it gives occasional wrong answers. But the human mathematician would likewise make blunders when trying out new techniques. It is easy for us to regard these blunders as not counting and give him another chance, but the machine would probably be allowed no mercy. In other words, then, if a machine is expected to be infallible, it cannot also be intelligent.

This is the passage which explains the 1946 ACE report claim for the 'indications' of machine intelligence at the cost of making serious mistakes. Penrose disputes Turing's argument: we do not expect intelligence in mathematics to turn upon the making of mistakes, and even if a result is mistaken, it can be reliably verified or corrected by others when communicated. Indeed the very essence of mathematical intelligence is seeing the truth. In the 1950 paper, Turing adds a further statement, again very brief: 'There would be no question of triumphing simultaneously over all machines. In short, then, there might be men cleverer than any given machine, but then again there might be other machines cleverer again, and so on.' This may be contrasted with Penrose's explicit and detailed exposition of human triumph over any Turing machine capable of partial judgments on the halting problem, by an argument that is a development of seeing the truth of unprovable Gödel statements. This, in Penrose's argument, establishes that the mind is capable of the uncomputable. Turing's bald assertion, putting human and machine on a par, is no more than re-assertion of his claim that the brain's function is that of a discrete state machine; it does not add any evidential weight to it.

So in the course of the war Turing dismissed the role for uncomputability in the description of mind, which once he had cautiously explored with the ordinal logics. A great body of opinion has followed Turing's example; not only within computer science, but in philosophy and the cognitive sciences. To a surprising degree the subject of mathematical logic, in Russell's time an enquiry into fundamental truth, has followed Turing's example and come to justify itself as adjunct to computer science. Yet Turing was careful to offer his conclusions not as dogma, but as constructive conjectures to be tested by scientific investigation.

I believe that in about fifty years' time it will be possible to programme computers, with a storage capacity of about 109, to make them play the imitation game so well that an average interrogator will not have more than 70 per cent chance of making the right identification after five minutes of questioning. The original question, 'Can machines think?' I believe to be too meaningless to deserve discussion. Nevertheless I believe that at the end of the century the use of words and general educated opinion will have altered so much that one will be able to speak of machines thinking without expecting to be contradicted. I believe further that no useful purpose is served by concealing these beliefs. The popular view that scientists proceed inexorably from well-established fact to well-established fact, never being influenced by any unproved conjecture, is quite mistaken. Provided it is made clear which are proved facts and which are conjectures. no harm can result. Conjectures are of great importance since they suggest useful lines of research.

A notable feature of the Turing test setting is that it requires not so much a judge as a jury: not an expert, but common humanity. The democracy of Turing's thought has lasted well. As new computer applications come into circulation, the technology of the Internet will give a new spin to the futuristic drama of the Turing test. We shall all judge for ourselves.

The fifty-year figure seems to derive from an estimate of sixty people working fifty years to write sufficient code: hardly a practical research proposal, and indeed no such proposal was made. In July 1951, Turing gained the use of a more reliable machine at Manchester, but there is no trace of him using it to simulate neural networks, nor to code chess-playing algorithms. He and the small group around him published articles [14] under the heading 'Digital computers applied to games' in 1953, which mark pioneering research into machine intelligence. But this lead made no impact on the fresh start to Artificial Intelligence made by Newell, Simon, Minsky and McCarthy in the United States. Turing never wrote the book on Theory and Practice of Computation which would have established his reputation. Nor was he prepared to argue and fight over strategy and practical support: he had done this successfully in 1940 over naval Enigma, he had done it unsuccessfully in 1946 for the ACE; after this he did not try again.

[13] A. M. Turing, Lecture to the London Mathematical Society, 20 February 1947. Typescript in the Turing Archive, King's College, Cambridge.
[14] B. V. Bowden (ed.) Faster than Thought, (Pitman, 1953). Turing contributed the section on chess.
(See also the Bibliography on this site.)

© 1997, Andrew Hodges.

CONTINUE to part 12

Quick Links:

A D V E R T I S I N G

Doing research? Try us for books, computers, scanners, or monitors. Or try to relax with a chart CD, pop CD, dvd, video, or bottle of wine. Escape it all with flights, a hotel, holidays in europe, or short breaks.