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). A_{1}, A_{2}, A_{3} … Let A_{i}(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 A_{n}(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 = A_{m}. That is, A_{m}(n) stops if A_{n}(n) does not stop

Consider the operation of B (= A_{m}) with the input m. B(m) = A_{m}(m) stops if A_{m}(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).

Filed under: Concepts | Tagged: Algorithms, Computability, Determinism, Free will, Mind, Penrose, Physics |

Adam Reed, on October 30, 2009 at 1:17 pm said: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…

K. M., on October 30, 2009 at 5:24 pm said:>Does Penrose say where he came across this argument?

From the book

>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

Overall, the book is definitely worth reading.