History of Busy Beaver Turing Machine Records
You can run any of these on my turing machine simulator but be warned — the simulator is a command-line-oriented Perl program, certainly not for the faint of heart; and it does not have the major optimizations of a "macro machine" emulator.
I also discuss the busy beaver function in:
The Lin-Rado Busy Beaver Function
Notes on The Busy Beaver Function
| When | Who | Marks | Steps | Program | Published |
| 1962 | Rado | BB1 = 1 | 1 | 1,_:H,1,> 1,1:1,_,< | Rado, On non-computable functions. The Bell System Technical Journal, vol. 41, no. 3, pp. 877-884, May 1962. |
| 1962 | Rado | BB2 = 4 | 6 |
1,_:2,1,> 1,1:2,1,<
2,_:1,1,< 2,1:H,1,< | Rado (1962) |
| 1962 | Hegelman | BB3 = 6 | 21 |
1,_:2,1,< 1,1:3,1,>
2,_:1,1,> 2,1:2,1,< 3,_:2,1,> 3,1:H,1,< | Rado (1962); and proven in Lin, Computer Studies of Turing Machine Problems. Journal for the Association of Computing Machinery, vol. 12, no. 2, pp. 196-212, April 1965. |
| 1966 | Brady | BB4 = 13 | 107 |
1,_:2,1,> 1,1:2,1,<
2,_:1,1,< 2,1:3,0,< 3,_:H,1,> 3,1:4,1,< 4,_:4,1,> 4,1:1,0,> | Brady (1966), and proven in A. H. Brady. Solution of the non-computable "Busy Beaver" game for k=4. Abstracts for ACM Computer Science Conference (Washington DC), p. 27 (1975). |
| January 1983 | Uwe Schult | BB5 >= 501 | 134,467 |
1,_:2,1,> 1,1:3,_,<
2,_:3,1,> 2,1:4,1,> 3,_:1,1,< 3,1:2,_,> 4,_:5,_,> 4,1:H,1,> 5,_:3,1,< 5,1:1,1,> | J. Ludewig, U. Schult, and F. Wankmueller. Chasing the Busy Beaver — Notes and Observations on a Competition to Find the 5-state Busy Beaver Forschungsberichte des Fachbereichs Informatik, 159, Universitaet Dortmund, Dortmund, 1983. |
| December 1984 | George Uhing | BB5 >= 1915 | 2,133,492 |
1,_:2,1,> 1,1:3,1,<
2,_:1,_,< 2,1:4,_,< 3,_:1,1,< 3,1:H,1,> 4,_:2,1,< 4,1:5,1,> 5,_:4,_,> 5,1:2,_,> | A.K. Dewdney, Computer Recreations, Scientific American, vol. 252, no. 4, pp. 12-16, April 1985. |
| September 1989 | Heiner Marxen, Juergen Buntrock | BB5 >= 4098 | 47,176,870 |
1,_:2,1,< 1,1:3,1,>
2,_:3,1,< 2,1:2,1,< 3,_:4,1,< 3,1:5,_,> 4,_:1,1,> 4,1:4,1,> 5,_:H,1,> 5,1:1,_,> | H. Marxen and J. Buntrock. Attacking the Busy Beaver 5 Bulletin of the EATCS, 40, pp. 247-251, February 1990. |
| 1989? | Heiner Marxen, Juergen Buntrock | BB6 >= 136,612 | >= 13,122,572,797 |
1,_:2,1,< 1,1:1,1,<
2,_:3,1,> 2,1:2,1,> 3,_:6,_,> 3,1:4,1,> 4,_:1,1,< 4,1:5,_,> 5,_:1,_,< 5,1:3,1,> 6,_:5,1,< 6,1:H,1,> | H. Marxen and J. Buntrock. Attacking the Busy Beaver 5. Bulletin of the EATCS, 40, pp. 247-251, February 1990. |
| September 1997 | Heiner Marxen | BB6 >= 95,524,079 | 8,690,333,381,690,951 |
1,_:2,1,> 1,1:1,1,>
2,_:3,1,< 2,1:2,1,< 3,_:6,_,> 3,1:4,1,< 4,_:1,1,> 4,1:5,_,< 5,_:H,1,> 5,1:6,1,< 6,_:1,_,< 6,1:3,_,< | Heiner Marxen, web page |
| Oct 2000 | Heiner Marxen, Juergen Buntrock | BB6 >= 6.427499 × 10462 | 6.196913 × 10925 |
1,_:2,1,> 1,1:2,_,<
2,_:3,_,> 2,1:2,1,< 3,_:4,1,> 3,1:1,_,< 4,_:5,1,< 4,1:6,1,< 5,_:1,1,< 5,1:4,_,< 6,_:H,1,> 6,1:5,1,< | Heiner Marxen, web page |
| Mar 2001 | Heiner Marxen, Juergen Buntrock | BB6 >= 1.29149 × 10865 | 3.00233 × 101730 |
1,_:2,1,> 1,1:6,_,<
2,_:3,_,> 2,1:4,_,> 3,_:4,1,< 3,1:5,1,> 4,_:5,_,< 4,1:4,_,< 5,_:1,_,> 5,1:3,1,> 6,_:1,1,< 6,1:H,1,> | Heiner Marxen, web page |
This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2023 Oct 21.
s.27