Lucas' Theorem

Are we 'Computers made of Meat'?  Is it possible that Scientific Laws will be discovered that totally explain human behaviour?  Lucas' Theorem, due to the great Oxford Philosopher John Lucas FBA, explains why both these hypotheses are impossible.


In the early days of mathematics, the Ancient Greek mathematicians got a shock. They had been investigating rational numbers (numbers of the form a/b where a and b are whole numbers) and had been making great strides in their ability to do calculations with and about them. The puzzling variety (2/3, 4/6 and 6/9 are all the same number) had been tamed by proving that any rational number can be expressed uniquely in its 'lowest terms' (ie when a and b have no common factors) and it seemed that every mathematical problem could be solved by them. Some of their philosophers went so far as to suggest that "everything is a number".

But whilst equations like 3x + 5 = 7 could be solved by rational numbers (x = 2/3) other proved more intractable. Consider x2 = 2. x = 7/5 is fairly close: 49/25 is only slightly less than 2 - 141/100 is even better. Clearly, by using larger and larger denominators you can get closer and closer to the answer.

Then a pesky mathematician showed that, however closely you could approximate the answer by rational numbers, you can never get there. For suppose that there was a rational number a/b such that (a/b)2 = 2. Then there must be a way of expressing the fraction in its lowest terms, as c/d say, where c and d have no common factor. But if (c/d)2 = 2, then c2 = 2d2, and thus c2 is an even number. But the square of any odd number is an odd number, so c must be an even number: 2f say. Hence (2f)2 = 2d2 so 4f2 = 2d2 so d2 = 2f2 so d2 is even, and hence d is even: 2g say. But this is impossible because c/d was a fraction in its lowest terms. Hence there is no rational number which solves the equation x2 = 2.

Note that it is not enough to say "ah well, let's take f/g as the new solution" because the proof can also be applied to the new fraction f/g

It is said that the first mathematician to prove this was put to death for his un-orthodoxy, and it was only many years later that other mathematicians brought the result to the attention of the educated public, so that it became an undoubted result.

Now all the 'arguments' for scientific determinism and "the brain is a computer" go along the lines of "of course we don't have anything like a complete theory yet, but we are continuing to make advances and so eventually we will have the full picture". You might have thought that the advocates of this line, who are all (presumably) aware of the above proof, must realise that this argument is completely fallacious, even if the gullible public to whom they offer the pronouncements does not. But in fact, Lucas's Theorem shows that, not only are the 'arguments' for Scientific Determinism and The Brain is a Computer fallacious, but the hypotheses are logically impossible.

John Lucas FBA was an Oxford Philosopher until his retirement in the 1990s. In the early days of Artificial Intelligence he proved a general result that has fundamental importance to any discussion of the distinction between computers and human beings, which was announced first in a paper and then in his book The Freedom of the Will (OUP).. Investigators of computers have been making great strides in their ability to do calculations which mimic the results of the human intellect. Decision making, calculation, symbolic manipulation, speech synthesis, expert systems, neural networks and the like provide closer and closer approximations to given aspects of human behaviour. Similarly, much trumpeted advances in neuroscience provide increasingly deeper understanding of the mechanisms of the brain. Surely it is "obvious" that eventually computers will be able to mimic human behaviour totally, and that scientists will be able to explain all aspects of the brain, and hence the mind. Far from being uniquely made in God's image, humans are 'nothing but' computers made of meat?

Lucas' Theorem Argument

Essentially it goes like this:

Define a Deterministic Logical System as a set of (at least two) states S, a set of inputs I and a logical system L which uniquely defines, given a state s in S and some inputs i in I, when the next state s' of the system will be.

There is a non-empty set of human beings HFree such that, for any member h of HFree, there does not exist a Deterministic Logical System which would accurately predict all h's actions in all circumstances.

Proof: Let HLog be the non-empty set of mathematical logicians capable of understanding Godel's theorem, and let h be a member of HLog.  Suppose there exists a Deterministic Logical System (S,I,L) which would accurately predict all h's actions in all circumstances.  Since h can do elementary arithmetic, L must be riche enough to contain  elementary arithmetic and thus by Godel's theorem there exists a proposition GL in L whose interpretation is "GL cannot be decided by L".   Consider now the circumstance where h (while rational) is asked: "is GL true?" . h will rationally answer "yes", reasoning as follows: "L cannot be contradictory, because if L were contradictory then (since in a contradictory logical system, if you can prove P you and prove not-P) the next state of the system would not be uniquely defined.  But if GL were false, then it would mean that "GL cannot be decided by L" can be decided by L, which is a contradiction.  Hence GL is true."  However, by definition, L cannot decide GL and thus will answer "don't know". QED.

Corrollary 1:  All rational human beings are members of HFree. Proof: it is absurd to suppose that there is anything so epistomolgically unique about mathematical logicians, and in principle all rational human beings are capable of being taught to understand Godel's theorem, .

Corrollary 2: No computer can competely model the mind of a human being. Proof: a computer is a Deterministic Logical System, and even if there are random factors in the program, these are ultimately either 'pseudo-random' or depend on random inputs, which can be made inputs to the Deterministic Logical System.

Corrollary 3: There can never be a scientific theory that completely accounts for human behaviour. Proof: If so then the scientific theory would be a Deterministic Logical System.

Note: none of these corrollaries deny that you can make increasingly accurate models or theories: they only show that the process will never finish. Similarly, you can make increasingly accurate approximations to the solution of the equation x2 = 2 in rational numbers, but you will never get there completely.

Amazingly The Freedom of the Will is out of print.  But similar arguments were made by the outstanding mathematician Sir Roger Penrose FRS in The Emporor's New Mind and Shadows of the Mind.  There is no doubt that the proof is correct, however uncomfortable and counter-cultural it may be to many in the western intelligensia.
Back to Star Course
Leading Scientists on Science & Religion