In the past couple of posts, I’ve spent time showing you the most layman-friendly view I could of concepts involved in turning concepts into numbers. The idea again is that both data and instructions can be turned into numbers.

And so, algorithms and the data they operate on can be turned into numbers. And we’ve seen how using an example encoding system, we can see that there are infinite programs which add two to a number. By the same token, we’ve seen an infinite number of programs which add three, and another endless set which add four. And so on.

We’ve even broached the topic that we might want to classify programs by what they do. And I’ve mentioned that there is no way to understand what an algorithm is going to do until we “run it”—t hat is, proceed through it step by step. But if we run through it, we encounter the problem of the analytical program looping forever trying to analyze it. There are some trivial cases of looping. We can always have a loop-detecting algorithm that notes the current line number, and checks to see whether the instruction at that line branches to that line.

In this case, we’ve found one a perpetual loop IF the variable in the instruction can ever be non-zero. So we’ve found one case where a “pathological” program might be the case, but we only can know if it actually loops by considering the other code to find out whether the variable can be non-zero.

A program beginning

Store X + 1 in X
[A] If X ≠ 0 GOTO A
…

will loop forever, a program beginning

[A] If X ≠ 0 GOTO A
…

will not.

So to be a “Loop Detector” of this—perhaps the simplest—loop, we have to trace through the code to see whether or not the variable gets set. Otherwise we’ve just isolated a case where the program might loop. And if we step through the code, and the program is built its simplest, then it would likely walk blindly into any number of other types of loops.

But in programs where the variable would always be zero, we could have any number of these statements which would perform just like a null statement. So even a Always-detect-the-simplest-loop program has its problems. There are programs that it could say definitely loop, perhaps an endless number. And there are programs that it could say will never loop, perhaps also endless.

What it cannot do is partition the set of algorithms into single-line-loopers and not. It could not eliminate the single-line-looping programs from consideration, without consideration of other pathological loops not fitting its profile.

There are perhaps an endless number of programs that would have it loop forever trying to analyze.