## 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 codethe variablefor (int i = 1; i > 0; i++);

`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

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.char i,x[99];for(x[98]=i=1;x[98];i++)i*=!++x[i];

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

is a wonderful example of C's brevity, but not very informative. Noting thati*=!++x[i];

`!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:

or after further transformations, the double loopchar i, x[99]; for (x[98] = i = 1; x[98] != 0; ) { x[i] += 1; if (x[i] != 0) i = 0; i += 1; }

and the inner loop can be easily seen to increment the 98-byte integer (with characters treated as unsigned base-256 "digits")char i, x[99]; for (x[98] = 1; x[98] != 0; ) { for (i = 1; ; i++) { x[i] += 1; if (x[i] != 0) break; } }

`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?