![]() |
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:
|
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 |