The Busy Beaver Problem

The Busy Beaver Problem

Department of Cognitive Science
Department of Computer Science
Bram van Heuveln
Selmer Bringsjord
Boleslaw Szymanski
Carlos Varela
Kyle Ross
Owen Kellett
Shailesh Kelkar

The Problem
What is the Busy Beaver problem? What is a Turing machine? Background information and history on this classical problem can be found here.

Our Goals
What are we trying to achieve and how do we plan to do it? It all can be found here.

Status Report
Statistics, champion machines, and what we've accomplished so far. A more detailed description of the specifics of each component of our attack can also be found here.

Current Work
What's being done right now to further our progress? All the latest news and developments can be found here.
Papers, presentations, and other documents produced by this effort. Owen's Turing machine simulator can also be found here - a Java application used to simulate and view the execution of user-definable Turing machines.

Information on the people involved in this project and what components they have contributed to.

Links to previous research on the Busy Beaver problem as well as other relevant sites on the web.

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).
Latest News