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*1018276 > 7.412*1036534 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*392-1)/2 [which is >8*1044].

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:

Other Resources (English)

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)


To the home page of Heiner Marxen.
$Date: 2014/10/03 14:15:41 $ Valid HTML 3.2!