“The simplest type of computational loop occurs when the system, at some stage, arrives back in exactly the same state as it had been in on a previous occasion. With no additional input it would then simply repeat the same computation endlessly. It would not be hard to devise a system that, in principle (though perhaps very inefficiently), would guarantee to get out of loops of this kind whenever they occur (by, say, keeping a list of all the states that it had been in previously, and checking at each stage to see whether that state has occurred before). However, there are many more sophisticated types of 'looping' that are possible. basically, the loop problem is the one that the whole discussion of Chapter 2 (particularly 2.1-2.6) was all about; for a computation that loops is simply one that does not stop. An assertion that some computation actually loops is precisely what we mean by a Pi-1 sentence (cf. 2.10, response to Q10). Now, as part of the discussion of 2.5, we saw that there is no entirely algorithmic way of deciding whether a computation will fail to stop-i.e. whether it will loop. Moreover, we conclude from the discussion above that the procedures that are available to human mathematicians for ascertaining that certain computations do loop-i.e. for ascertaining the truth of Pi1-sentences-lie outside algorithmic action.

Thus we conclude that indeed some kind of 'non-computational intelligence' is needed if we wish to incorporate all humanly possible ways of ascertaining for certain that some computation is indeed looping. It might have been thought that loops could be avoided by having some mechanism that gauges how long a computation has been going on for, and it 'jumps out' if it judges that the computation has indeed been at it for too long and it has no chance of stopping. But this will not do, if we assume that the mechanism whereby it makes such decisions is something computational, for then there must be the cases where the mechanism will fail, either by erroneously coming to the conclusion that some computation is looping when indeed it is not, or else by not coming to any conclusion at all (so that the entire mechanism itself is looping). One way of understanding this comes from the fact that the entire system is something computational, so it will be subject to the loop problem itself, and one cannot be sure that the system as a whole, if it does not come to erroneous conclusions, will not itself loop.”