The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics (Oxford Landmark Science)

by Roger Penrose

As it stands, this procedure does not so readily show that we have a Gödel proposition (like Pk(k)) that is true, but not provable within the system. However, if we recall the argument given in Chapter 2 on ‘how to outdo an algorithm’ (cf. p. 83), we shall see that we can do something very similar. In that argument we were able to show that, given any algorithm for deciding whether a Turing machine action stops, we can produce a Turing machine action that we see does not stop, yet the algorithm cannot. (Recall that we insisted that the algorithm must correctly inform us when a Turing machine action will stop though it can sometimes fail to tell us that the Turing machine action will not stop – by running on forever itself.) Thus, as with the situation with Gödel’s theorem above, we have a proposition that we can see, by the use of insight, must actually be true (not-stopping of the Turing machine action), but the given algorithmic action is not capable of telling us this.