The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
RPI RAIR Lab Busy Beaver Focus
The Busy Beaver problem has been attacked from several different angles by various different research groups around the world. As a result, candidate BB champions have been reported with a high degree of confidence for both the quintuple and quadruple formulations of the problem up to BB(6). However, what all of these previous research efforts lack is a definitive proof which explicitly confirms that these candidate machines are in fact Busy Beavers. While the Busy Beaver function itself is by definition uncomputable, it is possible to determine BB(n) for small values of n. We intend to show this, and begin our assault by concentrating on the quadruple variants of the problem.

Faced with this monumental task we realize what our approach must entail: a complete and exhaustive attack. The reason for this is clear: any kind of optimized genetic algorithm or heuristic search strategy would immediately derail us from our objective. Without considering the full search space, we cannot confirm anything. However, not only is a total brute-force, uninformed attack not practical, it is not necessary to maintain the integrity of a complete and optimal search. With the above considerations, we have formulated an attack strategy that is modularized into three main components:
  1. Implement a machine enumeration strategy which incorporates tree normalization filters that effectively eliminates machines from the search space by proving that they are equivalent to some other machine in the tree.
  2. Implement non-halt detection routines which can definitively classify machines as non-halters according to specificly provable non-halting behaviors.
  3. Develop a distributed computing approach to handle the enormous amount of computing power necessary to achieve our goal
With the above mechanisms in place, we hope to classify every single machine in the search space as one of five types:
  1. Tree-normalized: These machines have been proven to be equivalent to some other machine in the search space and are therefore eliminated from consideration.
  2. Candidate-halter: These machines halt and satisfy the conditions specified according to the particular Busy Beaver variation in question (i.e. B, P, O, R). The most productive machine in this set is the champion.
  3. Non-candidate-halter: These machines halt, but do not satisfy the above conditions and therefore are not considered as possible "candidate" champions.
  4. Non-halter: This category will be subdivided into many different subcategories. In essence, each subcategory will contain machines that exhibit a highly specific non-halting behavior and therefore can be classified as such.
  5. Holdouts: These machines do not halt after an arbitrary step limit and do not exhibit any of the behaviors specified by each of the non-halter subcategories. When the number of machines in this category equals zero, our goal will be achieved.
Busy Beaver in a Nut Shell
Consider a binary alphabet Turing Machine which is given an infinite, blank tape as input. If this machine halts, we define its productivity as the number of 1's left on the tape after the machine is run to completion. If it does not halt, the machine is given a productivity value of zero. Now consider all of the binary alphabet Turing Machines that have n states. The machine in this set which has the highest productivity is called a Busy Beaver, and its productivity is the result of the Busy Beaver function BB(n).
Busy Beaver Research Team
Bram van Heuveln
Selmer Bringsjord
Boleslaw Szymanski
Carlos Varela
Kyle Ross
Owen Kellett
Shailesh Kelkar