## 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).