Daemonic Dispatches

The never-ending finite loop

It's easy to write a loop which looks infinite but in fact completes quite quickly; for instance, in the C code

for (int i = 1; i > 0; i++);

the variable i starts at 1 and counts upwards "infinitely", but in fact the loop terminates due to the integer type overflowing and the value i becoming negative. A recent discussion led me to ponder the opposite problem: Can we write a theoretically finite loop which is nevertheless guaranteed to not complete?

It turns out that the answer, subject to some qualifications, is yes. The 48-character line of C99 code

char i,x[99];for(x[98]=i=1;x[98];i++)i*=!++x[i];

takes a finite number of steps to complete; but nevertheless is — subject to our current understanding of physics and the assumption that the process responsible for baryogenesis can be reversed to cause proton decay — guaranteed to never be (non-erronously) completed by a baryonic computer in the observable universe.

To explain why, let's first examine what this loop does. The statement

i*=!++x[i];

is a wonderful example of C's brevity, but not very informative. Noting that !x takes the value 0 if x is non-zero and 1 if x is zero, and that ++ is the pre-increment operator, we can rewrite this as the considerably more informative

x[i] += 1;
if (x[i] != 0)
        i = 0;

Placing this into the context of the original loop, we see that it is equivalent to the following:

char i, x[99];
for (x[98] = i = 1; x[98] != 0; ) {
        x[i] += 1;
        if (x[i] != 0)
                i = 0;
        i += 1;
}

or after further transformations, the double loop

char i, x[99];
for (x[98] = 1; x[98] != 0; ) {
	for (i = 1; ; i++) {
		x[i] += 1;
		if (x[i] != 0)
			break;
	}
}

and the inner loop can be easily seen to increment the 98-byte integer (with characters treated as unsigned base-256 "digits") x[98]x[97]...x[2]x[1]. Exactly how many steps this takes to complete will depend on the initial contents of the array x; but it will be between 254 * 256^97 and 256^98, i.e., between 1.00 * 10^236 and 1.02 * 10^236.

Having now established that the loop takes a finite number of steps to complete, we turn to the the second question: Will it ever complete? The observable universe has an estimated mass of roughly 10^55 kg, or a mass-energy of roughly 10^72 J; and from Lloyd's famous paper, Ultimate physical limits to computation, we know that the number of operations per second performed by a computer with energy E is at most 4 E / h; so we conclude that a computer in the observable universe can perform no more than 10^106 operations per second.

How long can such a computer keep computing? Based on our assumption that the process responsible for baryogenesis can also cause proton decay, we have from Adams and Laughlin an upper bound of roughly 10^41 years on the proton half-life. Even if our hypothetical universe-computer can continue computing as it evaporates, the restriction that it is a baryonic computer means that its mass — and thus its maximum possible processing speed — will decrease over time, ultimately limiting it to performing no more than 10^155 operations over its life -- some 81 orders of magnitude short of of the number of iterations requred to exit our 48-character "finite" loop.

I'll conclude with a request and a challenge. The request: I'm a computer scientist, not a cosmologist, and it's entirely possible that there's a glitch in my physics or that I've used the wrong terminology somewhere. If you know this material better than I do and I've gotten something wrong, please leave a comment below.

The challenge: I can't see how to write a baryonic-universe-incomputable finite loop in less than 48 characters of C99 code. Can you do better?

blog comments powered by Disqus