We Have a Winner

There are actually two winners to my nerd challenge: describe the longest running non-infinite algorithm which can be written for a digital computer. No use of I-O or clocks allowed.

Roland Turner says: “the most general non-repeating program would simply be a binary counter which uses the whole of RAM (plus registers, etc.) as its stored value, starts with all bits at zero and halts when all of the bits have reached one. Even with present-day computers, the energy cost of flipping that many bits would exceed the entire remaining energy in our sun, of course.”

Fred Wamsley says: “The next thing I'd check out would be treating all the registers and all the RAM as a single multi-precision int, zero it, and count until it overflows.”

Fred answered first but gave several possibilities. Roland was sure this was the right answer. Not sure who wins the nerdy trophy.  Both must be great programmers, though. Feel free to post job offers to them on my blog.

Here’s an informal proof:  The program has to be finite. If all of RAM and the registers as a whole are ever in the exact same state twice, the program is in a loop and is infinite. So each state may only be used once.  The number of unique states possible is two to the power of the total number of bits in RAM and the registers. You get to each of these states exactly once if you do what Roland and Fred say to do and simply count.  KISS (Keep It Simple Stupid) is very important.  The algorithm is taking space in memory. Each bit in the program CAN’T be used as part of the enormous counter. For every bit you give up, your program runs only half as long. I bet there is a good hack that lets some of the program be written over, though.