Computability and Free Will

In this post I will draw on a proof from Roger Penrose’s book Shadows of the mind that I think is important to the free will issue. The proof goes like this.

Consider an algorithm that takes a single positive integer as an input. Depending on the input and the algorithm itself, either the algorithm terminates in a finite time or it does not. In the first case the algorithm is said to stop.

Define a mapping from the set of natural numbers to the set of algorithms (of the kind above). A1, A2, A3 … Let Ai(n) denote the ith such algorithm operating on the input n.

Let B be an algorithm that also takes a single input, such that B(n) stops if it determines that An(n) does not stop. Since B is an algorithm of the same class of algorithms (taking a single input), it exists at some location in the list of As. Let B = Am. That is, Am(n) stops if An(n) does not stop

Consider the operation of B (= Am) with the input m. B(m) = Am(m) stops if Am(m) does not stop. That is, the task of B(m) is to stop if it is able to determine that it itself does not stop. If B(m) stops, we have a contradiction. Therefore B(m) does not stop. Therefore B is unable to determine that its own operation on the input m does not stop.

Now suppose that B represents all human understanding of algorithms that can be expressed as an algorithm. All of this algorithmic understanding is unable to detemine that B(m) does not stop. But we as humans are able to determine that B(m) does not stop.

Therefore atleast some aspect of human understanding is non-algorithmic. (Or in other words, the human mind can solve some problems that are not computable)

Penrose intended this proof (which parallels Godel’s proof of the incompleteness theorem) to debunk the claims of strong AI (artificial intelligence) that the human mind works by just “running” a higly evolved and complex algorithm. He explicitly steered clear of taking any position on the issue of determinism. And with good reason. Computability is not the same as determinism. A non-computable process can still be fully deterministic.

Most people who deny free will do so because they cannot reconcile free will with present day science. But Penrose’s proof conclusively demonstrates that present-day science (all the physical theories widely accepted in physics today are computable)  is incapable of explaining human understanding. It is not just that present day science does not have a theory of the mind. It cannot have a theory of the mind even in principle. Penrose argues that we need a non-computable theory in physics.

While this is not a proof of free will (without a scientific breakthrough, I don’t see how the existence of free will can be proved), it destroys the most common arguement against free will – the success of present day science (physics in particular).

3 Responses

1. Does Penrose say where he came across this argument – a rather straight-forward extension of Turing’s theorem? It is of course possible that he discovered it independently, but I published it back in 1973 (An Obituary for Machines of Loving Grace, Reason, October 1973, 25-27.) I first thought of it earlier – I think it was when I took Marvin Minsky’s Discrete Systems class at MIT in 1966, and I had discussed it with Marvin and with several other people at MIT. Now I may need to get Penrose’s book…

2. >Does Penrose say where he came across this argument?

From the book

The argument I shall present in the next chapter provides what I believe to be a very clear-cut argument for a non-computational ingredient in our conscious thinking. This depends upon a simple form of the famous and powerful theorem of mathematical logic, due to the great Czech-born logician Kurt Godel. I shall need only a very simplified form of this argument, requiring only very little mathematics (where I also borrow from an important later idea due to Alan Turing). Any reasonably dedicated reader should find no great difficulty in following it. However Godel-type arguments, used in this kind of way, have sometimes been vigorously disputed. Consequently, some readers might have gained an impression that this argument from Godel’s theorem has been fully refuted. I should make it clear that this is not so. It is true that many counter-arguments have been put forward over the years. Many of these were aimed at a pioneering earlier argument – in favour of mentalism and opposed to physicalism – that had been advanced by the Oxford philosopher John Lucas (1961). Lucas had argued from the Godel theorem that mental faculties must indeed lie beyond what can be achieved computationally. (others, such as Nagel and Newmann (1958), had previously argued in a similar vein.) My own argument, though following similar lines, is presented somewhat differently from that of Lucas – and not necessarily as support for mentalism. I believe that my form of presentation is better able to withstand the different criticisms that have been raised against the Lucas argument, and to show up their various inadequacies.

>Now I may need to get Penrose’s book…
For your information, the first part of the book is a detailed presentaion of this argument considering a number of objections that may be raised. The second part contains a description of the physical structure of the brain (that goes way beyond simple networks of neurons), a brief introduction to current physical theory and an outline of where it may be modified to incorporate a non-computational aspect.
Throughout the book, Penrose seems to be a Platonist. But he is not really one. He ends the book with

These are deep issues and we are yet very far from explanations. I would argue that no clear answers will come forward unless the interrelating features of all these worlds are seen to come into play. no one of these issues will be resolved in isolation from the others. I have referred to three worlds [Platonic world, Physical world and Mental world] and the mysteries that relate them one to another. No doubt, there are not really three worlds but one, the true nature of which we do not even glimpse at present.

Overall, the book is definitely worth reading.

3. Hi, sorry to be late to the show, but I had a problem understanding one aspect of this article. How are we as humans able to determine that B(m) does not stop? From my understanding of the halting problem B(m) should effectively just crash?
Thanks very much,
Harry Fox