Busy Beaver

Chapter Table:

Currently Known Results

The function Sigma(n) denotes the maximal number of tape marks which a 2-symbol Turing Machine (TM) with n internal states and a two-way infinite tape can produce onto an initially empty tape and then halt. The function S(n) denotes the maximal number of steps (shifts) which such a TM can do (it needs not produce many tape marks). The following table gives some known values:

n	Sigma(n)	S(n)	Source
1	1	1	Lin and Rado
2	4	6	Lin and Rado
3	6	21	Lin and Rado
4	13	107	Brady
5	>=�4098	>=�47,176,870	Marxen and Buntrock
6	>�3.514*10¹⁸²⁶⁷	>�7.412*10³⁶⁵³⁴	Pavel Kropitz

Note: The exact numbers for n=6 are found here.

A general method due to Milton W. Green produces (computable, but not primitive recursive) lower bounds of Sigma for every n. He gives Sigma(8) >= 3(7*3⁹²-1)/2 [which is >8*10⁴⁴].

Of course, if you find an error in the above table, or can extend it... please let me know.

News / Recent Changes

2016-May-08: S(8000) is independant of ZFC! As just recently found by Adam Yedidia and Scott Aaronson, and since 2016-May-03 explained (and discussed) on Scott's blog (linked above). Great! We have a first non-trivial upper bound of reasonable size!
07-Mar-2015: Added a link to a youtube video explaining busy beavers.
07-Mar-2015: Corrected a typo in the above table of results: Sigma(6) was given as 3.514*10¹⁸²⁷⁶ (wrong) instead of 3.514*10¹⁸²⁶⁷ (right). Note the exchanged last two digits of the exponent. Thanks to Samuel Kalbfleisch for noting it. This error has been here since 2010-Jul-06, and some have copied it, unfortunately. I apologize for the confusion.

Local Resources (English)

The author's paper

Heiner Marxen, J�rgen Buntrock, Attacking the Busy Beaver 5, Bulletin of the EATCS, Number 40, February 1990, pp. 247-251, [ISSN 0252-9742]
is not easily available at many places. You can
- download the postcript version (70K) as it were sent to the EATCS, or you can
- read the HTML version.
Old list of record TMs
The author's old list of record machines with 5 and 6 states (text file).
New list of record TMs
The author's new list of 6-state record machines as found by scanning 30% (rough estimate) of all 6-state TMs in June 2000 ... March 2001 (text file). This includes a new (since 05-Mar-2001) 6-state busy beaver champion producing more than 10⁸⁶⁵ ones.
Simulations of TMs
There are simulation results for various Turing machines, especially those mentioned in the above paper and record lists.
A proof that the TM #4 (chaotic) from our paper does not halt, received by email from Newcomb Greenleaf in 1992. In a followup email he claimed that the same proof technique also works for the TM #6 (complex counter).

In the beginning of these pages (1997) I strongly opted against writing any introductory text (TM definition etc.). I felt there were enough of them, and just wanted to present my own results. Well, now (2004) I changed my mind a bit:

TM Glossary
Here I explain my understanding and use of terms related with Turing Machines and Busy Beaver.
Macro Machines
Here I explain what are Macro Machines, and how they are constructed.
To come: Tape Representations; 4T/5T generalization

Other Resources (English)

Often referenced is the Busy Beaver Turing Machine by Michael Somos. He also has a more technical page.
Quentin F. Stout has written about The Complex Behaviour Of Simple Machines (PDF, abstract).
A 4 page handout (postscript) by Jeffrey Shallit.
There is an interesting relation between non-halting proofs for busy beaver Turing Machines and The Superset Algorithm of M.Najtiv (currently (Nov-2007) not available). Obviously he has found a useful generalization of the most powerful technique we have used.
Robert P. Munafo offers an analysis of a former 6-state record holder (producing 95524079 ones). Another analysis of the 6-state TM #q follows (producing >10⁴⁶² ones).
Another attack on Sigma(5) by Georgi Georgiev (Skelet) from Bulgaria. He even offers his Pascal program source.
Allan Brady has a page about 3-state 3-symbol machines with some really amazing results.
Pascal Michel has a very readable page, including an introduction to Turing Machines and Busy Beavers, lists of record machines, a historical survey, analysis of several TMs and references to papers. In June 2009 he presented his results as a paper.
H.J.M. Wijers offers an extensive bibliography (most of which was compiled before 1986).
Alex Holkner has written about "Acceleration Techniques for Busy Beaver Candidates" (taken from the Proceedings of the Second Australian Undergraduate Students' Computing Conference, 2004).
Terry J. Ligocki and Shawn Ligocki have contributed several record machines with 3 or more symbols.
James Harland studies several kinds of inverse busy beaver functions, and gives them interesting names.
Gregory Lafitte and Christophe Papazian in 2007 published "The Fabric of Small Turing Machines" (in Computation and Logic in the Real World, Proceedings of the Third Conference on Computability in Europe, June 2007, 219-227 ) where they claim to have computed Sigma and S for 2 states and 3 symbols: Sigma(2,3) = 9 and S(2,3) = 38. I tend to believe them, but I have not really checked their claim.
When we use 4-tuples instead of 5-tuples for the definition of the TM, we get similar but different machines. There is a similar contest for 4-tuple TMs, with some different rules. As a starter for 4-tuple TMs you can visit the page of Penousal Machado and Francisco Pereira, who contributed a new 7-state champion in August 1998. You may read about their evolutionary approach to find busy beavers.
Jon Barwise and John Etchemendy at CSLI have pictures of some 4-tupel busy beaver candidates especially from Machado/Pereira.
A group at the Rensselaer Polytechnic Institute (RPI) in New York attacks the 4-tuple busy beaver problem. They summarize their efforts and results (PDF), and also present several new record machines. Kyle Ross has written a thesis about optimization techniques (PDF).
Sigma(n) is Sequence A028444 in "The On-Line Version of the Encyclopedia of Integer Sequences" of N.J.A. Sloane. Also, S(n) is Sequence A060843. [ If you get a "permission denied" answer, just retry a bit later. ]
Mathworld of Wolfram has a busy beaver entry.
Of course there is a Wikipedia entry about busy beavers. [Last visit 2007-Nov-12]
I've also found a youtube video explaining busy beavers. It also offers a link to a video about turing machine basics.
Rick J. Griffiths in his dissertation in 2003 has adapted the busy beaver problem to Minsky's "register machines". His program is written in Java.
There exists a universal Turing Machine with just 2 states and 3 symbols. In May 2007 Wolfram announced a $25,000 research prize for a (positive or negative) proof, and now (October 2007) that prize is won. Read more at www.wolframprize.org.
Tim Hutton has translated some TMs into cellular automata, and did run them with "golly" (an advanced simulator, originally for the "game of life"). He also tried some 2D variants (Turmites).

There are numerous Turing Machine emulators, some of them written as Java applet. Here is an example TM applet. Here is the original (presumably). Those which I have tried did not fit my interests enough to really use them. Sometime I will try to craft my own TM emulator applet.

Other Resources (German/Deutsch)

Eine Gruppe an der Uni Stuttgart hat einiges gut Lesbares �ber Flei�ige Biber zusammengetragen, inklusive eines Applets, das eine eingegebene BB-TM simuliert. Am Ende findet sich noch ein Literatur-Verzeichnis (in Postscript).
Das Friedrich-Koenig-Gymnasium (W�rzburg) hat eine einfache Einf�hrung zu Turingmaschinen von StR Gerhard M�rz. Ein Simulator f�r MS-DOS ist auch dabei.
In einem PDF-Dokument Prinzipielle Grenzen der Berechenbarkeit schreibt Arno Schwarz �ber Turing Maschinen, Busy Beaver und das Collatz Problem (3n+1). Es gibt Definitionen, Beweise und ein paar Bilder, eingebettet in einen gut lesbaren Text.
Michael Buro hat sich in seiner Diplomarbeit (November 1990) ebenfalls mit flei�igen Bibern und Sigma(5) besch�ftigt. Die Dimplomarbeit ist in Postscript auf seiner Ver�ffentlichungs-Seite (Abschnitt "Theses") zu bekommen. Neben reichlich mathematischen Analysen beschreibt er auch sein Programm und die damit gewonnenen Resultate.
Es gibt sogar einen deutschen Wikipedia-Artikel zu flei�igen Bibern. [Gesehen 2005-Jul-07] Von dort aus findet man auch eine deutsche Erkl�rung von Turing-Maschinen.
Im "MathePrisma" der Uni Wuppertal finden sich gut lesbare Einf�hrungen zur Turing Maschine allgemein, und zu flei�igen Bibern im speziellen (im Abspann).
Ein h�bsche Darstellung des Themas busy beaver (PDF) gibt es auch von W.Zimmer vom Cusanus-Gymnasium Wittlich.

To the home page of Heiner Marxen.

$Date: 2016/05/08 19:56:29 $