Busy Beaver

Currently Known Results

The function Sigma(n) denotes the maximal number of tape marks which a 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 > 1.29*10865 > 3*101730 Marxen and Buntrock

Note: The values for n=6 have been verified independently by Paul R. Stevens and by Clive Tooth. The exact numbers are found in the new list of 6-state record machines.

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.

Local Resources (English)

Other Resources (English)

There are numerous Turing Machine emulators, some of them written as Java applet. Here is an example TM applet. 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)


Back to the home page of Heiner Marxen.
$Date: 2002/06/24 20:18:30 $ Valid HTML 3.2!