Brady's Algorithm for Program Generation

submited by

Style Pass

2022-01-15 00:30:07

The aim of the Busy Beaver game is to find the longest running Turing machine program of n states and k colors. Busy Beaver programs could in principle be written by hand, but nobody has ever succeeded in doing so. Instead, these programs are discovered through exhaustive search. This is done by a two-stage process:

Stage two raises an obvious question: run them for how long? It would be great to run them all for infinitely many steps, but that’s nonsense. Only finitely many steps can be executed. So how many? What we’re looking for is a natural number S and an nk-program P such that P halts after S steps. But there’s no way to upper-bound S in terms of n and k; for if there were, it could be used to solve the halting problem, and that’s impossible. The only way to deal with this is to pick a step limit T and run everything for that many steps. There isn’t any principled way to decide on a good T; in practice it’s determined by 1) how powerful my hardware is, 2) how long I’m willing to wait, and 3) my out-of-thin-air estimate on the upper bound of S. The history of Busy Beaver research is littered with estimates of S that turned out to be comically wrong. I’ve even made a few stupid estimates myself!

The first stage, program generation, is a little more nuanced. The difficulties here are not uncomputable; instead, they are “just” infeasible. It’s easy to write code to enumerate every n-state k-color program, but the number of nk-programs grows multiple-exponentially: there are O(nknk) of them. This is because an nk-program has one instruction per state per color, and there are 2nk possible instructions. This gets out of hand quickly.