8-bit busy beavers

There are lots of statements that are technically true, but where that truth is fundamentally useless. “The proof of the undecidability of the halting problem doesn’t apply to any physical computer” is one such statement.

If you make a YouTube video that states something like that with a straight face, you’ll get some really fun comments by different sets of people who think that someone else is being Wrong On The Internet^TM.

Theory

Computer science is sometimes a goofy amalgamation of hardware engineering and pure mathematics. This, and the profound explosion of computing power that has taken place over the past two generations, has some counterintuitive implications.

In the last few months of the pre-vaccine pandemic era, I got interested in physical electronics, and built Ben Eater’s 8-bit breadboard computer. I noticed that, by slightly altering this basic computer, it became simple enough that every possible state of the system could be enumerated by an only-slightly-clever search algorithm. This leads to one of those counterintuitive results: it’s straightforward to check whether a program halts or not. I explained this in a “paper,” Build your own 8-bit busy beaver on a breadboard!, presented at the “conference” SIGBOVIK, which a friend characterized as an event that “scorches (for its pointless navel-gazing) and celebrates (for its pointless navel-gazing) academia.”

Website

The proof of the undecidability of the halting problem doesn’t apply to any physical computer. This is true but useless, and the true-but-uselessness was really driven home by the fact that I had to modify Ben Eater’s design for a trivial computer into an even less powerful computer in order to make state-space enumeration practical.

To drive this home in a very strange way, I created a simple “leaderboard” website where people could submit their longest running programs for the actual Ben Eater computer design, sisyphean.glitch.me. This uses SQLite and express and is remixable on glitch.com.