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 |