Careers | Phone Book | A - Z Index

Busy Beaver Problem

The Busy Beaver, BB, problem for Turing machines, TMs, was first posed by Rado in the early 1960's. A nice list of references is given on Michael Somos' webpage. Pascal Michel has a number of webpages devoted to the Busy Beaver problem with links on his homepage including Turing machines: an Introduction, The Busy Beaver Competitions, Histortical survey of Busy Beavers, and Behavior of busy beavers. Mathworld and Wikipedia also have entries for the busy beaver problem. H.J.M Wijers provides additional WWW links.

Heiner Marxen and Juergen Buntrock have obtained some amazing results for TMs which use have 5 or 6 states and 2 symbols - the (5,2) and (6,2) BB problems, respectively. Heiner has a website which documents their results and lists other interesting results for other TMs. It also includes some nice references and some simulators written in "awk" that can handle TMs which run for an astronomical number of steps and use an astronomical amount of tape! Very interesting results for (3,3) TMs can be found on Allen Brady's webpage . Georgi Georgiev has worked on many aspects of the 5-state, 2-symbol problem and Rensselaer Polytechnic Institute has a New Millennium Attack on the BB problem. .

My son, Shawn Ligocki, and I have contributed to the BB investigation. Using simulated annealing techniques for optimization, we have found a new, best result for the (2,4) BB problem and some initial candidates for the (2,5) and (2,6) problems. The latter are almost certainly not maximal. Of our original work, only our (2,4) result stood the test of time - see below. We have made more progress and currently hold the record for the (2,4), (3,3), and (2,5) BB problems. Documentation and details of these results can be found on Pascal Michel's Histortical survey of Busy Beavers, and Heiner Marxen's Busy Beaver Simulations. Our codes are currently written on a combination of Python and C.

We improved our initial results for the (2,5) and (2,6) BB problems but they were still just lower bounds and not maximal. In addition, we have generated results for the (4,3) and (3,4) BB problems. All these initial results were exceeded (considerably) by the current work of Gregory Lafitte and Christophe Papazian! Their current, best (2,5) TM exceeded our initial results (for (2,5) AND (2,6)) by over a factor of 1,000. Their current, best (3,3) TM exceeded our (4,3) and (3,4) results by over a factor of 10,000!

We still had the (2,4) champion and we started working on proving this result. In the process we were able to further analyze (3,3) and (2,5) TMs and we found TMs that are current BB champions in both cases!

In 2007 and 2008, Shawn and I were able to make more extensive runs using better simulation acceleration and find BB champions for following cases: (6,2), (3,3), (4,3), (3,4), (2,5), and (2,6). Our (2,4) champion looks like the true BB but we have not yet proved this although our results are almost complete and now include a proof of the (2,3) case (unpublished).

Again, documentation and details of the current results (and histories) can be found on Pascal Michel's Histortical survey of Busy Beavers, and Heiner Marxen's Busy Beaver Simulations.