Busy Beaver
Chapter Table:
Currently Known Results
The function
Sigma(n)
denotes the maximal number of tape marks
which a 2symbol Turing Machine (TM) with n internal states
and a twoway 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^{18276} 
> 7.412*10^{36534} 
Pavel Kropitz 
Note: The values for n=6 have not yet been verified independently.
The exact numbers 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^{92}1)/2
[which is >8*10^{44}].
Of course, if you find an error in the above table,
or can extend it... please
let me know.
News / Recent Changes
Local Resources (English)
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 nonhalting proofs
for busy beaver Turing Machines and
The Superset Algorithm
of M.Najtiv (currently (Nov2007) 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 6state record holder
(producing 95524079 ones).
Another analysis of the 6state TM #q follows
(producing >10^{462} 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
3state 3symbol 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, 219227
)
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 4tuples instead of 5tuples for the definition
of the TM, we get similar but different machines.
There is a similar contest for 4tuple TMs,
with some different rules. As a
starter for 4tuple TMs
you can visit the page of
Penousal Machado
and
Francisco Pereira,
who contributed a new 7state 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 4tupel busy beaver candidates
especially from Machado/Pereira.

A group at the Rensselaer Polytechnic Institute (RPI)
in New York attacks the 4tuple 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 OnLine 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 2007Nov12]

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 BBTM simuliert.
Am Ende findet sich noch ein LiteraturVerzeichnis (in Postscript).

Das FriedrichKoenigGymnasium (Würzburg)
hat eine einfache
Einführung zu Turingmaschinen
von StR Gerhard März.
Ein Simulator für MSDOS ist auch dabei.

In einem PDFDokument
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öffentlichungsSeite
(Abschnitt "Theses")
zu bekommen.
Neben reichlich mathematischen Analysen beschreibt er auch sein
Programm und die damit gewonnenen Resultate.

Es gibt sogar einen
deutschen WikipediaArtikel
zu fleißigen Bibern.
[Gesehen 2005Jul07]
Von dort aus findet man auch eine
deutsche Erklärung von TuringMaschinen.

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 CusanusGymnasium Wittlich.
To the
home page of Heiner Marxen.
$Date: 2014/07/09 19:39:25 $

