BB(2,3)
Jump to navigation
Jump to search
BB(2,3) refers to the Busy Beaver function with 2 states and 3 symbols. The value was discovered by Brady in 1988 (and independently by Michel in 2004) and proven by Lafitte and Papazian in 2007.[1]
Champions
S(2,3) = 38 and Σ(2,3) = 9 and both are achieved by only one champion (in TNF):
1RB2LB1RZ_2LA2RB1LB(bbch)
Enumeration
The top 20 longest running BB(2,3) TMs (in TNF-1RB) are:
Standard Format Steps Σ 1RB2LB1RZ_2LA2RB1LB 38 9 1RB0LB1RZ_2LA1RB1RA 29 8 1RB2LA1RZ_1LB1LA0RA 26 6 1RB1LA1LB_0LA2RA1RZ 26 6 1RB1LB1RZ_2LA2RB1LB 24 7 1RB2LA1RZ_0LB1LA0RA 22 4 1RB2RB1RZ_1LB1RA0LA 21 4 1RB2LA2RB_1LA1RZ1RA 20 6 1RB2LA1RZ_2LA2RB1LB 20 6 1RB2LA0RB_1LA1RZ1RA 20 5 1RB0LB1RZ_2LA2LB1RA 19 7 1RB0RB1RZ_1LB2RA1LA 19 6 1RB2LB1LA_2LA1RZ2RB 18 7 1RB1LB2LA_1LA2RB1RZ 18 7 1RB2LB2LA_2LA1RZ0RA 18 6 1RB2LA1RZ_1LB1RA2RB 18 6 1RB2LB1RZ_2LA1RA0LB 18 5 1RB0RB1RZ_1LB2LA2RA 17 6 1RB2LB0LB_2LA1RZ2RB 17 4 1RB2RA1RZ_0LB2RB1LA 17 3
For the full list of 866 halting BB(2,3) TMs, see: https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/2x3.txt
Sources
- ↑ G. Lafitte, C. Papazian, "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, pp. 219--227.