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 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. 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 |