The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
|
The Busy Beaver Problem
A NEW MILLENNIUM ATTACK
|
  |
|
 |
 |
 |
 |
 |
 |
 |
 |
|
People involved in the Busy Beaver project
Bram van Heuveln
Professor, Department of Cognitive Science Selmer Bringsjord Professor, Department of Cognitive Science Boleslaw Szymanski Professor, Department of Computer Science Carlos Varela Professor, Department of Computer Science Kyle Ross Rensselaer Graduate - Computer Science/Philosophy Dual Major PhD student at Chalmers University of Technology Research on tree normalization techniques and benefits Implementation of machine enumeration and execution strategy using tree normalization Significant contribution to superpaper Kyle's presentation on tree normalization Kyle's personal website. Owen Kellett Rensselaer Undergraduate - Computer Science Major Designed and developed Owen's Turing Machine Simulator Research on specific non-halting behaviors and detection algorithms Implementation of non-halt detection routines as extension of Kyle's code Owen's presentation on non halters Owen's Master's Thesis. Owen's personal website. Shailesh Kelkar Rensselaer Graduate - Department of Computer Science Research and implementation of distributed computational approach to the Busy Beaver problem Shailesh's presentation on the Farmer Worker model |
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 |