Foreword to A Computable Universe: Understanding computation and exploring nature as computation

Roger Penrose

World Scientific 2012

Penrose’s argues that Gödel’s incompleteness theorem provides a strong case for human understanding being non-computable. This relates to our ability to demonstrate the truth of certain mathematical propositions. These are described as π_{1} sentences. These sentences assert that a particular computation, such as Lagrange’s theorem which asserts that every natural number is the sum of four squares, will never terminate.

With a formal system, ‘**F’**, all the arguments that might be used to establish a π_{1} sentence are included within the algorithmic procedure, ‘**A’**. This algorithm is envisaged as a process for checking that a proof that is part of ‘**F’** has been carried out, with the answer ‘YES’ given after a finite number of steps. If we trust in ‘**A’,** to the effect that a π_{1} sentence is true, when ‘**A**‘ gives the answer ‘YES’, then one can have a π_{1} sentence ‘**G**‘, in which our trust in ‘**A**‘ allows us to trust the truth of ‘**G**‘, despite the fact that ‘**A**‘ cannot directly establish ‘**G**‘.

Penrose goes on to deal with Gödel’s second incompleteness theorem. In this the π_{1} sentence ‘**G(F)**‘ is an assertion of the consistency of the formal system ‘**F**‘, while ‘**G**‘ is the π_{1} assertion that among the theorems of ‘**F**‘ there are none that are a negation of ‘**F**‘ . Our trust in the algorithm ‘**A**‘ does not allow us to directly establish either ‘**G**‘ or the consistency of ‘**F**‘. Our trust in ‘**G**‘ which establishes the consistency of ‘**F**‘ flows from our trust in ‘**A**‘ which in turn depends on ‘**F**‘s consistency. Thus our trust in ‘**F**‘ as a way of establishing π_{1} sentences allows us to go beyond ‘**F**‘, and to assert the truth of ‘**G(F)**‘, despite the fact that ‘**F**‘ does not include ‘**G(F)**‘ among its theorems.

Penrose argues that while some human understanding can be transposed into computer procedures, Gödel has shown that such procedures cannot cover everything that is accessible to mathematical understanding, and therefore mathematical understanding is non-computable. In plainer English, Penrose is saying that the theorem shows that the human brain can access understanding that is beyond any computer however powerful. It is this claim that is controversial.

Penrose goes on to discuss various arguments against his claims. The first argument is that the fact that mathematicians can make errors invalidates Penrose’s argument. He accepts that there are errors from time-to-time, but claims it is the ideal of establishing a mathematical truth which is important. A second argument is that the complication of the algorithms governing mathematical understanding are beyond reach. Penrose counters that in common with other things in mathematics they can be known in principle.

The third argument is that the brain has an algorithm that can go beyond formal systems, but that we don’t know what it is (an unknowable algorithm). Penrose here argues from evolution. He asks how natural selection could have favoured such an algorithm when it was totally irrelevant to the survival of our ancestors.

Most logicians and philosophers are thought to be strongly opposed to Penrose’s interpretation of the theorem, and to believe they have refuted him. It is difficult to verify this one way of the other, as most accounts merely say that a great majority have refuted Penrose rather than putting forward actually arguments, and some papers that are quoted as water tight refutations turn out on examination to be closer to Penrose than his opponents.