User:Azerty/Busy Beaver Functions: Difference between revisions

Revision as of 10:59, 28 December 2025

This is a list of Busy Beaver functions for Turing machines and other simple Turing-complete systems and their current lower bounds.

I only add functions that follow the requirements below:

The function must grow uncomputably fast, like BB(n).
The function must not have similar champions to other function, like Σ(n).
The function must not be arbitrary complex.

Turing machines

Classic

Maximum number of steps done by a n-state, m-symbol Turing machine with k+1 undefined instructions before halting. TMs halt when they are on an undefined transititon.

Domain	Lower Bound	Champion
BB(2,2,1)	4	`0RB_1LA` (bbch)
BB(2,2)	6	`1RB1LB_1LA---` (bbch)
BB(2,3,1)	14	`0RB---1LB_1LA2RB---` (bbch)
BB(3,2,1)	17	`1RB---_0RC---_1LC0LA` (bbch)
BB(3,2)	21	`1RB---_1LB0RC_1LC1LA` (bbch)
BB(2,3)	38	`1RB2LB---_2LA2RB1LB` (bbch)
BB(4,2,1)	38	`1RB---_1LB0LC_1RD1LD_0RB---` (bbch)
BB(3,3,2)	77	`1RB---0RC_2LC------_2RC0LC1RA` (bbch)
BB(4,2)	107	`1RB1LB_1LA0LC_---1LD_1RD0RA` (bbch)
BB(2,4,1)	124	`1RB3LA1RA0LA_2LA------3RA` (bbch)
BB(5,2,1)	162	`1RB---_1LC0RE_---0LD_1RA1LE_0LD0RC` (bbch)
BB(2,4)	3,932,964	`1RB2LA1RA1RA_1LB1LA3RB---` (bbch)
BB(3,3,1)	3,932,964	`1RB2LA1RA_1LC1LA2RB_---1LA---` (bbch)
BB(5,2)	47,176,870	`1RB1LC_1RC1RB_1RD0LE_1LA1LD_---0LA` (bbch)
BB(6,2,1)	17,397,627,083	`1RB0LA_1RC1RD_1LB1RA_---0RE_1LF0RC_1LA---` (bbch)
BB(3,3)	$1.191 \times 1 0^{17}$	`0RB2LA1RA_1LA2RB1RC_---1LB1LC` (bbch)
BB(2,5)	$10 ↑ 10 ↑ 10 ↑ 3, 314, 360$	`1RB3LA4RB0RB2LA_1LB2LA3LA1RA---` (bbch)
BB(2,6)	$10 ↑^{2} 10 ↑^{2} 1 0^{1 0^{115}}$	`1RB3RB5RA1LB5LA2LB_2LA2RA4RB---3LB2LA` (bbch)
BB(6,2)	$10 ↑^{2} 10 ↑^{2} 10 ↑^{2} 8$	`1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE` (bbch)
BB(4,3)	$10 ↑^{3} 10 ↑^{3} 10 ↑^{3} 1 0^{28}$	`1RB1RD1LC_2LB1RB1LC_---1LA1LD_0RB2RA2RD` (bbch)
BB(7,2)	$10 ↑^{11} 10 ↑^{10} 4$	`1RB0RA_1LC1LF_1RD0LB_1RA1LE_---0LC_1RG1LD_0RG0RF` (bbch)
BB(3,4)	$10 ↑^{15} 4$	`1RB3LB---2RA_2LC3RB1LC2RA_3RB1LB3LC2RC` (bbch)
BB(9,2)	$f_{ω} (10 ↑^{7} 10 ↑^{7} 2)$	`1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_1LB0LH` (bbch)
BB(3,5)	$f_{ω} (10 ↑^{15} 4)$	`1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC` (bbch)
BB(10,2)	$f_{ω}^{2} (25)$	`1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ` (bbch)
BB(11,2)	$f_{ω}^{2} (10 ↑^{2} 10)$	`1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE` (bbch)
BB(12,2)	$f_{ω}^{4} (10 ↑^{2} 65, 534)$	`0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_---1LA_1RF1LL` (bbch)
BB(14,2)	$f_{ω + 1} (65, 536)$	`1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM---_0LN1LF_0LJ---` (bbch)
BB(15,2)	$f_{ω + 1} (f_{ω} (1 0^{57}))$	`0RH1LD_1RI0RC_1RB1LD_0LD1LE_1LF1RA_1RG0LE_1RB1RG_1RD1RA_0LN0RJ_---0LK_0LK1LL_1RG1LM_0LL0LL_1LO1LN_0LG1LN` (bbch)
BB(16,2)	$f_{ω + 1}^{2} (1 0^{1 0^{57}})$	`0RG1LD_0RI0RC_1RB1LD_0LD1LE_1LF1RA_1RP0LE_1RD1RA_0LP1LO_1LO1RM_0LJ1LK_1LL1LL_1RP0LK_1LH0RN_---0LJ_1LH1LO_1RB1RP` (bbch)
BB(2,7)

Instructions

Maximum number of steps done by a Turing machine with n defined instructions before halting. TMs halt when they are on an undefined transititon.

Domain	Lower Bound	Champion
BBi(2)	4	`0RB_1LA` (bbch)
BBi(3)	6	`1RB1LB_1LA---` (bbch)
BBi(4)	17	`1RB---_0RC---_1LC0LA` (bbch)
BBi(5)	38	`1RB2LB---_2LA2RB1LB` (bbch)
BBi(6)	124	`1RB3LA1RA0LA_2LA------3RA` (bbch)
BBi(7)	3,932,964	`1RB2LA1RA1RA_1LB1LA3RB---` (bbch)
BBi(8)	$6.889 \times 1 0^{1, 565}$	`1RB1LA------_1RC3LB1RB---_2LA2LC---0LC` (bbch)
BBi(9)	$10 ↑ 10 ↑ 10 ↑ 3, 314, 360$	`1RB3LA4RB0RB2LA_1LB2LA3LA1RA---` (bbch)
BBi(11)	$10 ↑^{15} 4$	`1RB3LB---2RA_2LC3RB1LC2RA_3RB1LB3LC2RC` (bbch)
BB(14)	$f_{ω} (10 ↑^{15} 4)$	`1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC` (bbch)
BBi(19)	$f_{ω}^{2} (25)$	`1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ` (bbch)
BBi(21)	$f_{ω}^{2} (10 ↑^{2} 10)$	`1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE` (bbch)
BBi(23)	$f_{ω}^{4} (10 ↑^{2} 65, 534)$	`0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_---1LA_1RF1LL` (bbch)
BBi(27)	$f_{ω + 1} (65, 536)$	`1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM---_0LN1LF_0LJ---` (bbch)
BBi(29)	$f_{ω + 1} (f_{ω} (1 0^{57}))$	`0RH1LD_1RI0RC_1RB1LD_0LD1LE_1LF1RA_1RG0LE_1RB1RG_1RD1RA_0LN0RJ_---0LK_0LK1LL_1RG1LM_0LL0LL_1LO1LN_0LG1LN` (bbch)
BBi(31)	$f_{ω + 1}^{2} (1 0^{1 0^{57}})$	`0RG1LD_0RI0RC_1RB1LD_0LD1LE_1LF1RA_1RP0LE_1RD1RA_0LP1LO_1LO1RM_0LJ1LK_1LL1LL_1RP0LK_1LH0RN_---0LJ_1LH1LO_1RB1RP` (bbch)

Semi-infinite tape

Maximum number of right steps done by a n-state, m-symbol Turing machine with k undefined instructions on a semi-infinite tape before its head leave the tape. The head starts in the first cell. TMs are disqualified if they halt before blanking the tape.

Domain	Lower Bound	Champion
BBt(2,2,1)	3	`1RB---_1LB0RB` (bbch)
BBt(2,2)	3	`1RB---_1LB0RB` (bbch)
BBt(2,3,1)	9	`1RB---2RB_2LB2RA0RB` (bbch)
BBt(3,2,1)	11	`1RB---_0RC0RB_1LB1LC` (bbch)
BBt(3,2)	12	`0RB0LB_0RC1RC_1LA0LC` (bbch)
BBt(2,3)	17	`1RB0RA0RB_2LA2RB1LB` (bbch)
BBt(2,4,1)	36	`1RB3RA0RB0RA_2LA2RB1LB---` (bbch)
BBt(2,4)	49	`1RB2RA2RB2LA_2LB0RA3RB0LA` (bbch)
BBt(4,2,1)	55	`0RB---_1RC0LD_1RD1RB_1LB0RC` (bbch)
BBt(4,2)	63	`0RB0LD_0RC1LC_0RD1LA_1LB1RD` (bbch)
BBt(3,3,2)	93	`1RB------_0RC0RB1LC_1LB2RC0LB` (bbch)
BBt(3,3)	202	`1RB2RC1LC_0RC0RB1LA_2LA2RC1LB` (bbch)

Semi-infinite tape instructions

Maximum number of right steps done by a Turing machine with n defined instructions on a semi-infinite tape before its head leave the tape. The head starts in the first cell. TMs are disqualified if they halt before blanking the tape.

Domain	Lower Bound	Champion
BBti(3)	3	`1RB---_1LB0RB` (bbch)
BBti(4)	8	`1RB---_1RC---_1LC0RC` (bbch)
BBti(5)	18	`1RB------_1RC------_2LC2RC0RC` (bbch)
BBti(6)	36	`1RB------_1RC------_1RD------_2LD2RD0RD` (bbch)
BBti(7)	93	`1RB------_0RC0RB1LC_1LB2RC0LB` (bbch)
BBti(9)	202	`1RB2RC1LC_0RC0RB1LA_2LA2RC1LB` (bbch)

Blanking

Maximum number of steps done by a n-state, m-symbol Turing machine with k undefined instructions before blanking the tape again. TMs must write a non-zero symbol on the first step. TMs are disqualified if they halt before blanking the tape.

Domain	Lower Bound	Champion
BLB(2,2,1)	4	`1RB0RA_1LA---` (bbch)
BLB(2,2)	8	`1RB0RA_1LB1LA` (bbch)
BLB(3,2,1)	16	`1RB---_1LC0LC_1RC0LB` (bbch)
BLB(2,3,1)	22	`1RB2LB---_2LA0RB1LB` (bbch)
BLB(3,2)	34	`1RB1LB_1LA1LC_1RC0LC` (bbch)
BLB(2,3)	77	`1RB2LA0RB_1LA0LB1RA` (bbch)
BLB(4,2,1)	169	`1RB---_0RC0LA_1LC1LD_0RB0RD` (bbch)
BLB(3,3,2)	173	`1RB------_2RC2RB1LB_2LC2RB0RC` (bbch)
BLB(3,3,1)	308	`1RB1RC---_1LB1RA2RB_0RB2LC0RC` (bbch)
BLB(4,2)	32,779,477	`1RB1LD_1RC1RB_1LC1LA_0RC0RD` (bbch)
BLB(5,2)	32,810,047	`1RB1LC_1RD0LE_0RD0RC_1LD1LA_1RB1RE` (bbch)
BLB(6,2)	65,538,549	`1RB1LE_1RD1RB_0RD0RE_1LD1LA_0RF1RF_0LC1LC` (bbch)
BLB(2,4)	$1.367 \times 1 0^{12}$	`1RB2RA1RA2RB_2LB3LA0RB0RA` (bbch)

Blanking instructions

Maximum number of steps done by a Turing machine with n defined instructions before blanking the tape again. TMs must write a non-zero symbol on the first step. TMs are disqualified if they halt before blanking the tape.

Domain	Lower Bound	Champion
BLBi(3)	4	`1RB0RA_1LA---` (bbch)
BLBi(4)	12	`1RB---_1RC---_1LC0RC` (bbch)
BLBi(5)	30	`1RB------_1RC------_2LC2RC0RC` (bbch)
BLBi(6)	77	`1RB2LA0RB_1LA0LB1RA` (bbch)
BLBi(7)	173	`1RB------_2RC2RB1LB_2LC2RB0RC` (bbch)
BLBi(8)	$1.367 \times 1 0^{12}$	`1RB2RA1RA2RB_2LB3LA0RB0RA` (bbch)

Reversible

Maximum number of steps done by a n-state, m-symbol reversible Turing machine with k+1 instructions transitions before halting.

Domain	Lower Bound	Champion
BBr(2,2,1)	4	`0RB---_1LA---` (bbch)
BBr(2,2)	6	`0RB---_1LA1RB` (bbch)
BBr(3,2)	17	`0RB---_0LC1RA_1RB1LC` (bbch)
BBr(4,2)	48	`1RB0LD_0LC0RB_1LA1LD_1LC---` (bbch)
BBr(5,2)	388	`1RB0RD_1RC0RB_1RD---_1LE1LA_0LE0LA` (bbch)
BBr(6,2)	537,556	`1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA---_1RF1RA` (bbch)
BBr(7,2)	$1 0^{19}$	`1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB---` (bbch)

Consecutive ones

Maximum number of consecutive 1s left on the tape by a n-state, m-symbol Turing machine with k+1 undefined instructions after halting. TMs must leave all their 1s consecutively.

Domain	Lower Bound	Champion
BBn(2,2,1)	2	`1RB---_1LA---` (bbch)
BBn(2,2)	4	`1RB1LB_1LA---` (bbch)
BBn(2,3)	5	`1RB1LB_1RC1LC_1LA---` (bbch)
BBn(3,2)	6	`1RB1LC_1RC---_1LA0LB` (bbch)
BBn(4,2)	12	`1RB0LA_1RC1LB_1LB1RD_---0RA` (bbch)
BBn(3,3)	12	`1RB1RA---_1LC1LC2LA_2RA1LB1LA` (bbch)
BBn(5,2)	165	`1RB1LA_1RC1LE_1RD1RE_0LA1RC_---0LB` (bbch)
BBn(4,3)	$10 ↑^{4} 4$	`1RB1RD1LC_2LB1RB1LC_---1LA1LD_0RB2RA2RD` (bbch)

Preperiodic

Maximum number of steps done by a n-state, m-symbol Turing machine with k undefined instructions before turning into a translated cycler.

Domain	Lower Bound
BBS(2,2,1)	4	`1RB---_1LB0RB` (bbch)
BBS(2,2)	9	`1RB0LB_1LA0RB` (bbch)
BBS(3,2)	101	`1RB1LB_0RC0LA_1LC0LA` (bbch)
BBS(4,2)	119,120,230,102	`1RB1LC_0LA1RD_0RB0LC_1LA0RD` (bbch)
BBS(2,4)	$2 \times 1 0^{23}$	`1RB2LA1RA1LB_0LB2RB3RB1LA` (bbch)
BBP(5,2,1)	$5.418 \times 1 0^{51}$	`1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC` (bbch)
BBP(5,2)	$1 0^{14, 006}$	`1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA` (bbch)
BBP(3,3)	$10 ↑^{2} 6$	`1RB0LB2LA_1LA0RC0LB_2RC2RB0LC` (bbch)

Periodic

Maximum translated cycler period done by a n-state, m-symbol Turing Machine with k undefined instructions.

Domain	Lower Bound	Champion
BBP(2,2,1)	3	`1RB---_0LB1RA` (bbch)
BBP(2,2)	9	`1RB0RB_1LB1RA` (bbch)
BBP(3,2)	92	`1RB0LA_0RC1LA_1LC0RB` (bbch)
BBP(3,3)	1,195	`1RB2RC1LC_0RC0RB1LA_2LA2RC1LB` (bbch)
BBP(2,4)	33,209,131	`1RB0RA3LB1RB_2LA0LB1RA2RB` (bbch)
BBP(4,2)	212,081,736	`1RB0LA_0RC1RD_1LD0RB_1LA1RB` (bbch)
BBP(5,2,1)	8,468,569,863	`1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC` (bbch)

Turing machine variations

Turmite

Maximum number of steps done by a n-state, m-symbol Turmite machine with k+1 undefined instructions before halting.

Domain	Lower Bound	Champion
TT(2,2,1)	6	`0PB_1TA`
TT(2,2)	13	`1TB---_1PA0PB`
TT(2,3,1)	20	`1TB------_1PA2PB0PB`
TT(3,2,1)	20	`1TB---_1PC0PB_1PA---`
TT(3,2)	82	`1PB0PA_1TA0PC_1PA---`
TT(4,2,1)	139	`1PB---_0PD0TC_---0TA_1TA1PA`
TT(2,3)	223	`1TB0PA2PA_2PA---1PA`
TT(3,3,1)	683	`1TB0PA---_1PC1PB0TC_2PA1PA---`
TT(4,2)	758	`1TB---_0PD1PB_1PA1TA_0PC0PD`
TT(2,4)	1,068	`1TB3TB2PB---_2TB1PA0PA2TB`
TT(3,3)	3,786	`1PB2PC1PB_2TC0TA---_1PA1PC0PC`

Turmite instructions

Maximum number of steps done by a Turmite machine with n defined instructions before halting.

Domain	Lower Bound	Champion
TTi(2)	6	`0PB_1TA`
TTi(3)	13	`1TB---_1PA0PB`
TTi(4)	20	`1TB------_1PA2PB0PB`
TTi(5)	223	`1TB0PA2PA_2PA---1PA`
TTi(7)	1,068	`1TB3TB2PB---_2TB1PA0PA2TB`
TTi(8)	3,786	`1PB2PC1PB_2TC0TA---_1PA1PC0PC`

Turmite semi-infinite tape

Maximum number of right steps done by a n-state, m-symbol Turmite machine with k undefined instructions on a semi-infinite tape before its head leave the tape. The head starts in the first cell. TMs are disqualified if they halt before blanking the tape.

Domain	Lower Bound	Champion
BBt(2,2,1)	3	`0PB---_1TB1PB`
BBt(2,2)	4	`1PB0TB_1TA0PB`
BBt(2,3,1)	9	`1PB2TB---_1TA0PB0TB`
BBt(3,2,1)	9	`0PB---_1PC1TC_1TB0PC`
BBt(3,2)	23	`0PB0PC_1PC0TA_1TB1TC`
BBt(2,3)	39	`2PB1TA1TB_2TA0TA0PB`
BBt(2,4,1)	44	`1PB2PB0PB---_2TB2TA3TA1TB`
BBt(4,2,1)	48	`0PB---_1TB1PC_0TB1TD_0PC0PD`
BBt(3,3,2)	70	`1PB---0PB_0PC---1PC_2TC0TA2PC`
BBt(3,3)	134	`1PB2PC2TB_1TC0TA0PB_2TC1TA2TA`
BBt(4,2)	166	`1PB0TB_0PC0TA_0PD0PB_1TB1TA`
BBt(2,4)	194	`0PB2PB3TB0PA_1TB2TB3PB3TA`

Turmite blanking

Maximum number of steps done by a n-state, m-symbol Turmite machine with k undefined instructions before blanking the tape again. TMs must write a non-zero symbol on the first step. TMs are disqualified if they halt before blanking the tape.

Domain	Lower Bound	Champion
TLT(2,2,1)	7	`1TB0TB_0PA---`
TLT(2,2)	12	`1PB0PA_1TA0TA`
TLT(2,3,1)	24	`1TB2PB0PA_2TA---0TA`
TLT(3,2,1)	24	`1PB---_0PC0TC_1TA0TA`
TLT(3,2)	84	`1TB1PC_1TA0PA_1PA0TB`
TLT(4,2,1)	84	`1TB1PC_1TA0PA_1PA0TB_------`
TLT(2,3)	108	`1TB0TA0PB_2PA2PB0PA`
TLT(2,4)	126	`1TB2TB0TB2PA_3TA2PA0PA3PB`
TLT(4,2)	267	`1TB0TD_1PC0PA_0PA0TD_1PD0PB`
TLT(3,3)	2,122	`1TB2PA0TA_1TA0TB2PC_2PB0PA0TC`

Lambda calculus

SK calculus

Maximum normal form size of any closed SK term of size n.

Domain	Lower Bound	Champion
SKBB(4)	4	`SSSS`
SKBB(5)	6	`SSS(SS)`
SKBB(6)	8	`SSS(SSS)`
SKBB(7)	10	`SSS(SSSS)`
SKBB(8)	23	`SSS(S(SKS))S`

BCKW calculus

Maximum normal form size of any closed BCKW term of size n.

Domain	Lower Bound	Champion
BCKWBB(3)	3	`BBB`
BCKWBB(4)	5	`WB(BB)`
BCKWBB(5)	7	`WB(BBB)`
BCKWBB(6)	11	`WB(WB(BB))`
BCKWBB(7)	15	`WB(WB(BBB))`
BCKWBB(8)	23	`WB(WB(WB(BB)))`

De Bruijn

Maximum normal form size of any closed lambda term of size n.

Domain	Lower Bound	Champion
BBL(7)	7	`\1 1 1 1 1 1`
BBL(8)	16	`(\1 1) (\\2 (1 2))`
BBL(9)	68	`(\1 1) (\\2 (2 (1 2)))`
BBL(10)	$7.625 \times 1 0^{12}$	`(\1 1 1) (\\2 (2 (2 1)))`
BBL(11)	$1 0^{7.625 \times 1 0^{12}}$	`(\1 1 1 1) (\\2 (2 (2 1)))`
BBL(12)	$10 ↑^{3} 16$	`(\1 1 1) (\1 (\\2 (2 1)) 1)`
BBL(13)	$10 ↑^{3} 10 ↑^{3} 10 ↑^{2} 6$	`(\1 1) (\1 (\1 (\\2 (2 1)) 2))`
BBL(14)	$10 ↑^{3} 10 ↑^{3} 10 ↑^{3} 16$	`(\1 1 1 1 1) (\1 (\\2 (2 1)) 1)`
BBL(15)	$f_{ω + 1} (1 0^{1 0^{19, 727}})$	`(\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))`
BBL(23)	$f_{ω^{2}} (4)$	`(\1 1 (\\1 (\\1 2 1) 2 1) (\1 1) 1) 1) (\\2 (2 1))`
BBL(24)	$f_{ω^{2}} (27)$	`(\1 1 (\\1 (\\1 2 1) 2 1) (\1 1) 1) 1) (\\2 (2 (2 1)))`
BBL(25)	$f_{ω^{ω}} (4)$	`(\1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 1))`
BBL(26)	$f_{ω^{ω}} (27)$	`(\1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))`
BBL(27)	$f_{ω^{ω}} (1 0^{12})$	`(\1 1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))`
BBL(28)	$f_{ω^{ω}} (1 0^{1 0^{12}})$	`(\1 1 1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))`
BBL(34)	$f_{ω^{ω^{ω}}} (4)$	`(\1 1 (\\\\1 4 3 2 1) (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 1))`

Tag system

2-tag system

Maximum number of transformations performed with a 2-tag system of size n. Its size if the sum of the number of letters and the number of different letters.

Domain	Lower Bound	Champion
TTBB(4)	1	`Δ: aa P: a`
TTBB(5)	2	`Δ: aaa P: a`
TTBB(6)	3	`Δ: aaaa P: a`
TTBB(7)	4	`Δ: aaaaa P: a`
TTBB(8)	5	`Δ: aaaaaa P: a`
TTBB(9)	8	`Δ: aaa P: bbb, a`
TTBB(10)	13	`Δ: aaaa P: bbb, a`
TTBB(11)	20	`Δ: aaaaa P: bbb, a`
TTBB(12)	24	`Δ: aaa P: bc, a, aaa`

Cyclic tag

Maximum number of transformations that can be done with a cyclic tag system of size n. Its size if the sum of the number of bits and the number of instructions.

Domain	Lower Bound	Champion
CTBB(2)	1	`Δ: 1 P: _`
CTBB(3)	2	`Δ: 11 P: _`
CTBB(4)	4	`Δ: 11 P: 0`
CTBB(5)	6	`Δ: 111 P: 0`
CTBB(6)	9	`Δ: 111 P: 00`
CTBB(7)	12	`Δ: 1111 P: 00`
CTBB(8)	16	`Δ: 1111 P: 000`
CTBB(9)	20	`Δ: 11111 P: 000`
CTBB(10)	25	`Δ: 11111 P: 0000`

Tree rewriting

Maximum number of transformations that can be done with a tree rewriting system of size n. Its size if the number of brackets.

Domain	Lower Bound	Champion
TRBB(2)	1	`Δ: () P: () > _`
TRBB(3)	2	`Δ: ()() P: () > _`
TRBB(4)	3	`Δ: ()()() P: () > _`
TRBB(5)	4	`Δ: ()()()() P: () > _`
TRBB(6)	6	`Δ: ()()() P: () > (), () > _`
TRBB(7)	8	`Δ: ()()()() P: () > (), () > _`
TRBB(8)	10	`Δ: ()()()()() P: () > (), () > _`
TRBB(14)	38	`Δ: ()(()) P: (()) > ((())), ()()() > _, () > ()()`
TRBB(23)	672	`Δ: ()()()() P: ()() > (()())(), ()() > ()()(()), () > (()), (((()))) > _`
TRBB(38)	$10 ↑ 10 ↑ 10 ↑ 10 ↑ 54$	`Δ: (())(()()) P: (()()) > (()())(()), (()()) > (()())(()), ()(()) > (())((())), ((())) > ((()))()(), () > _`
TRBB(45)	$10 ↑^{3} 130$	`Δ: ((()))((())) P: ((())) > ((()))(()()), (()()) > (()())(()), (()) > (())(()()()), (()()()) > (()()())()(), ()()() > _, () > _`
TRBB(69)	$10 ↑^{4} 10 ↑^{2} 10 ↑^{2} 4$	`Δ: ((()))((()())) P: ((()())) > ((()()))((())), ((())) > ((()))(()()()), ((())) > ((()))(()()()), (()()()) > (()()())(()()), (()()) > (()())(())(()), (()) > (())()()()()(), () > _`

Fractran

Maximum number of instructions applied by a fractran program of size n before halting.

Domain	Lower Bound	Champion
BBf(10)	7	`[729/2, 1/3]`
BBf(11)	10	`[27/2, 25/3, 1/5]`
BBf(12)	13	`[81/2, 25/3, 1/5]`
BBf(13)	17	`[81/2, 125/3, 1/5]`
BBf(14)	21	`[243/2, 125/3, 1/5]`
BBf(15)	28	`[1/45, 4/5, 3/2, 25/3]`
BBf(16)	53	`[1/45, 4/5, 3/2, 125/3]`
BBf(17)	107	`[5/6, 49/2, 3/5, 40/7]`
BBf(18)	211	`[5/6, 49/2, 3/5, 80/7]`
BBf(19)	370	`[5/6, 49/2, 3/5, 160/7]`
BBf(20)	746	`[7/15, 22/3, 6/77, 5/2, 9/5]`
BBf(21)	31,957,632	`[7/15, 4/3, 27/14, 5/2, 9/5]`
BBf(22)	$1.146 \times 1 0^{62}$	`[1/12, 9/10, 14/3, 11/2, 5/7, 3/11]`

Brainfuck

Maximum number of instructions read by a brainfuck program with n instructions (uses +-<>[] symbols). Cells size are unbounded and can have negative values.

Domain	Lower Bound	Champion
BFBB(6)	6	`++++++`
BFBB(7)	8	`++++[-]`
BFBB(8)	12	`+++[--+]`
BFBB(9)	16	`++++[--+]`
BFBB(10)	20	`+++++[--+]`
BFBB(11)	38	`+[[>]-<+<+]`

Boolfuck

Maximum number of instructions read by a boolfuck program with n instructions (uses *<>[] symbols).

Domain	Lower Bound	Champion
BLBB(7)	7	`>>>>>>>`
BLBB(8)	9	`>[<<>]`
BLBB(9)	11	`>>>[<*]`
BLBB(10)	14	`>>*[<<>]`
BLBB(11)	17	`>>>[<<>*]`
BLBB(12)	21	`>>>>[<<>*]`
BLBB(13)	25	`>>>>>[<<>*]`
BLBB(14)	58	`+>+[<+<+[>]+<]`
BLBB(17)	109	`+>>+>>+[>>+[<]+<]`
BLBB(19)	112	`+>+>>+>>+[>>+[<]+<]`
BLBB(20)	180	`+>>+>>+>>+[>>+[<]+<]`
BLBB(22)	183	`+>+>>+>>+>>+[>>+[<]+<]`
BLBB(23)	269	`+>>+>>+>>+>>+[>>+[<]+<]`

BitChanger

Maximum number of instructions read by a bitchanger program with n instructions (uses <}[] symbols).

Domain	Lower Bound	Champion
BCBB(7)	7	`}}}}}}}`
BCBB(8)	9	`}}}}<[<]`
BCBB(9)	13	`}}}<[}<<]`
BCBB(10)	17	`}}}}<[}<<]`
BCBB(11)	21	`}}}}}<[}<<]`
BCBB(12)	25	`}}}}}}<[}<<]`

Bitter

Maximum number of instructions read by a bitter program with n instructions (uses <>[] symbols).

Domain	Lower Bound	Champion
BTBB(7)	7	`>>>>>>>`
BTBB(8)	9	`>>>><[<]`
BTBB(9)	11	`>>>>><[<]`
BTBB(10)	13	`>>>>>><[<]`
BTBB(11)	15	`>>>>>>><[<]`
BTBB(12)	17	`>>>>>>>><[<]`

Minsky machines

Maximum number of steps done by a Minsky machine before halting.

Domain	Lower Bound	Champion
MBB(1)	1	`0+*`
MBB(2)	3	`0+B_0-B*`
MBB(3)	5	`0+B_0+C_0-C*`
MBB(4)	10	`0+B_1+C_0-BD_1-C*`
MBB(5)	24	`0-DB_0+C_1-ED_1+A_1-B*`
MBB(6)	49	`0+B_1-FC_1+D_0-CE_0+A_1-A*`

@@ Line 10: / Line 10: @@
 === [[Busy Beaver Functions|Classic]] ===
-Maximum number of steps done by a n-state, m-symbol Turing Machine with k+1 undefined instructions before halting. TMs halt when they are on an undefined transititon.
+Maximum number of steps done by a n-state, m-symbol Turing machine with k+1 undefined instructions before halting. TMs halt when they are on an undefined transititon.
 {| class="wikitable"
 !Domain
@@ Line 142: / Line 142: @@
 === [[Instruction-Limited Busy Beaver|Instructions]] ===
-Maximum number of steps done by a Turing Machine with n defined instructions before halting. TMs halt when they are on an undefined transititon.
+Maximum number of steps done by a Turing machine with n defined instructions before halting. TMs halt when they are on an undefined transititon.
 {| class="wikitable"
 !Domain
@@ Line 214: / Line 214: @@
 === Semi-infinite tape ===
-Maximum number of right steps done by a n-state, m-symbol Turing Machine with k undefined instructions on a semi-infinite tape before its head leave the tape. The head starts in the first cell. TMs are disqualified if they halt before blanking the tape.
+Maximum number of right steps done by a n-state, m-symbol Turing machine with k undefined instructions on a semi-infinite tape before its head leave the tape. The head starts in the first cell. TMs are disqualified if they halt before blanking the tape.
 {| class="wikitable"
 !Domain
@@ Line 270: / Line 270: @@
 === Semi-infinite tape instructions ===
-Maximum number of right steps done by a Turing Machine with n defined instructions on a semi-infinite tape before its head leave the tape. The head starts in the first cell. TMs are disqualified if they halt before blanking the tape.
+Maximum number of right steps done by a Turing machine with n defined instructions on a semi-infinite tape before its head leave the tape. The head starts in the first cell. TMs are disqualified if they halt before blanking the tape.
 {| class="wikitable"
 !Domain
@@ Line 302: / Line 302: @@
 === [[Blanking Busy Beaver Function|Blanking]] ===
-Maximum number of steps done by a n-state, m-symbol Turing Machine with k undefined instructions before blanking the tape again. TMs must write a non-zero symbol on the first step. TMs are disqualified if they halt before blanking the tape.
+Maximum number of steps done by a n-state, m-symbol Turing machine with k undefined instructions before blanking the tape again. TMs must write a non-zero symbol on the first step. TMs are disqualified if they halt before blanking the tape.
 {| class="wikitable"
 !Domain
@@ Line 362: / Line 362: @@
 === [[Blanking Busy Beaver Function#Instruction-limited Blanking Busy Beaver (BLBi(n))|Blanking instructions]] ===
-Maximum number of steps done by a Turing Machine with n defined instructions before blanking the tape again. TMs must write a non-zero symbol on the first step. TMs are disqualified if they halt before blanking the tape.
+Maximum number of steps done by a Turing machine with n defined instructions before blanking the tape again. TMs must write a non-zero symbol on the first step. TMs are disqualified if they halt before blanking the tape.
 {| class="wikitable"
 !Domain
@@ Line 394: / Line 394: @@
 === [[Reversible Turing Machine|Reversible]] ===
-Maximum number of steps done by a n-state, m-symbol reversible Turing Machine with k+1 instructions transitions before halting.
+Maximum number of steps done by a n-state, m-symbol reversible Turing machine with k+1 instructions transitions before halting.
 {| class="wikitable"
 !Domain
@@ Line 430: / Line 430: @@
 === [[Maximum Consecutive Ones Function|Consecutive ones]] ===
-Maximum number of consecutive 1s left on the tape by a n-state, m-symbol Turing Machine with k+1 undefined instructions after halting. TMs must leave all their 1s consecutively.
+Maximum number of consecutive 1s left on the tape by a n-state, m-symbol Turing machine with k+1 undefined instructions after halting. TMs must leave all their 1s consecutively.
 {| class="wikitable"
 !Domain
@@ Line 470: / Line 470: @@
 === [[Non-halting Turing machine#Translated cycler preperiod|Preperiodic]] ===
-Maximum number of steps done by a n-state, m-symbol Turing Machine with k undefined instructions before turning into a translated cycler.
+Maximum number of steps done by a n-state, m-symbol Turing machine with k undefined instructions before turning into a translated cycler.
 {| class="wikitable"
 !Domain
@@ Line 548: / Line 548: @@
 === [[Terminating Turmite|Turmite]] ===
-Maximum number of steps done by a n-state, m-symbol Turmite Machine with k+1 undefined instructions before halting.
+Maximum number of steps done by a n-state, m-symbol Turmite machine with k+1 undefined instructions before halting.
 {| class="wikitable"
 !Domain
@@ Line 556: / Line 556: @@
 |TT(2,2,1)
 |6
-|<code>0PB---_1TA---</code>
+|<code>0PB_1TA</code>
 |-
 |TT(2,2)
@@ Line 595: / Line 595: @@
 |-
 |TT(3,3)
+|3,786
+|<code>1PB2PC1PB_2TC0TA---_1PA1PC0PC</code>
+|}
+=== Turmite instructions ===
+Maximum number of steps done by a Turmite machine with n defined instructions before halting.
+{| class="wikitable"
+!Domain
+!Lower Bound
+!Champion
+|-
+|TTi(2)
+|6
+|<code>0PB_1TA</code>
+|-
+|TTi(3)
+|13
+|<code>1TB---_1PA0PB</code>
+|-
+|TTi(4)
+|20
+|<code>1TB------_1PA2PB0PB</code>
+|-
+|TTi(5)
+|223
+|<code>1TB0PA2PA_2PA---1PA</code>
+|-
+|TTi(7)
+|1,068
+|<code>1TB3TB2PB---_2TB1PA0PA2TB</code>
+|-
+|TTi(8)
 |3,786
 |<code>1PB2PC1PB_2TC0TA---_1PA1PC0PC</code>
@@ Line 600: / Line 632: @@
 === Turmite semi-infinite tape ===
-Maximum number of right steps done by a n-state, m-symbol Turmite Machine with k undefined instructions on a semi-infinite tape before its head leave the tape. The head starts in the first cell. TMs are disqualified if they halt before blanking the tape.
+Maximum number of right steps done by a n-state, m-symbol Turmite machine with k undefined instructions on a semi-infinite tape before its head leave the tape. The head starts in the first cell. TMs are disqualified if they halt before blanking the tape.
 {| class="wikitable"
 !Domain
@@ Line 656: / Line 688: @@
 === Turmite blanking ===
-Maximum number of steps done by a n-state, m-symbol Turmite Machine with k undefined instructions before blanking the tape again. TMs must write a non-zero symbol on the first step. TMs are disqualified if they halt before blanking the tape.
+Maximum number of steps done by a n-state, m-symbol Turmite machine with k undefined instructions before blanking the tape again. TMs must write a non-zero symbol on the first step. TMs are disqualified if they halt before blanking the tape.
 {| class="wikitable"
 !Domain

User:Azerty/Busy Beaver Functions: Difference between revisions

Revision as of 10:59, 28 December 2025

Contents

Turing machines

Classic

Instructions

Semi-infinite tape

Semi-infinite tape instructions

Blanking

Blanking instructions

Reversible

Consecutive ones

Preperiodic

Periodic

Turing machine variations

Turmite

Turmite instructions

Turmite semi-infinite tape

Turmite blanking

Lambda calculus

SK calculus

BCKW calculus

De Bruijn

Tag system

2-tag system

Cyclic tag

Tree rewriting

Fractran

Fractran

Brainfuck

Brainfuck

Boolfuck

BitChanger

Bitter

Minsky machines

Minsky machines

Navigation menu

User:Azerty/Busy Beaver Functions: Difference between revisions

Revision as of 10:59, 28 December 2025

Turing machines

Semi-infinite tape

Semi-infinite tape instructions

Turing machine variations

Turmite instructions

Turmite semi-infinite tape

Turmite blanking

Lambda calculus

BCKW calculus

Tag system

2-tag system

Cyclic tag

Tree rewriting

Fractran

Brainfuck

Brainfuck

Boolfuck

BitChanger

Bitter

Minsky machines

Navigation menu

Search