next up previous
Next: Gödels's Theorem in a Up: Penrose's argument for computational Previous: Gödel's Theorem in a

Gödel's Theorem in a nutshell: Argument

The procedure A can be viewed as a particular computation that, when presented with (q,n) tries to ascertain whether the computation tex2html_wrap_inline316 will never ultimately halt i.e

equation149

It is now perfectly legitimate to write

equation153

Now as we have listed all of the computations tex2html_wrap_inline336 , A(n,n) must be one of these computations. Thus

equation160

i.e A(n,n) is identified with the computation tex2html_wrap_inline342 as A now only depends on one argument n.

Now examine the particular n = k. From (3) we have

equation164

and from (2) we may write, with n=k,

equation167

But from (4) we had that tex2html_wrap_inline356 and thus from (5) we have

equation172

Thus we must deduce that tex2html_wrap_inline362 does not in fact stop, for if it did stop it does not according to (6). Thus from (4) A(k,k) cannot stop either. Thus A is incapable of ascertaining that the specific computation (or algorithm) tex2html_wrap_inline362 does not stop even though it does not stop !

We have required that A is sound i.e always gives the correct answer. It must follow that we know that tex2html_wrap_inline362 does not stop. Thus we know something that A is unable to ascertain, namely that tex2html_wrap_inline362 does not stop.



David T J Liley
Thu Apr 9 12:39:27 EST 1998