The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
|
The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
|
  |
|
 |
 |
 |
 |
 |
 |
 |
 |
|
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 |