User:Azerty/Busy Beaver Functions

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)	242	1RB0LA_1RC0LA_1LD0RE_---1LA_---0RB (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 10^{17}$	0RB2LA1RA_1LA2RB1RC_---1LB1LC (bbch)
BB(3,4,2)	$6.889\times 10^{1,565}$	1RB1LA------_1RC3LB1RB---_2LA2LC---0LC (bbch)
BB(2,5)	$10\uparrow 10\uparrow 10\uparrow 3,314,360$	1RB3LA4RB0RB2LA_1LB2LA3LA1RA--- (bbch)
BB(2,6)	$10{\uparrow }^{2}10{\uparrow }^{2}10^{10^{115}}$	1RB3RB5RA1LB5LA2LB_2LA2RA4RB---3LB2LA (bbch)
BB(6,2)	$10{\uparrow }^{2}10{\uparrow }^{2}10{\uparrow }^{2}8$	1RB1RA_1RC---_1LD0RF_1RA0LE_0LD1RC_1RA0RE (bbch)
BB(4,3)	$10{\uparrow }^{3}10{\uparrow }^{3}10{\uparrow }^{3}10^{28}$	1RB1RD1LC_2LB1RB1LC_---1LA1LD_0RB2RA2RD (bbch)
BB(7,2)	$10{\uparrow }^{11}10{\uparrow }^{10}4$	1RB0RA_1LC1LF_1RD0LB_1RA1LE_---0LC_1RG1LD_0RG0RF (bbch)
BB(3,4)	$10{\uparrow }^{15}4$	1RB3LB---2RA_2LC3RB1LC2RA_3RB1LB3LC2RC (bbch)
BB(9,2)	$f_{\omega }(10{\uparrow }^{7}10{\uparrow }^{7}2)$	1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_1LB0LH (bbch)
BB(3,5)	$f_{\omega }(10{\uparrow }^{15}4)$	1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC (bbch)
BB(10,2)	$f_{\omega }^2(25)$	1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ (bbch)
BB(11,2)	$f_{\omega }^2(10{\uparrow }^{2}10)$	1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE (bbch)
BB(12,2)	$f_{\omega }^4(10{\uparrow }^{2}65,534)$	0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_---1LA_1RF1LL (bbch)
BB(14,2)	$f_{\omega +1}(65,536)$	1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM---_0LN1LF_0LJ--- (bbch)
BB(15,2)	$f_{\omega +1}(f_{\omega }(10^{57}))$	0RH1LD_1RI0RC_1RB1LD_0LD1LE_1LF1RA_1RG0LE_1RB1RG_1RD1RA_0LN0RJ_---0LK_0LK1LL_1RG1LM_0LL0LL_1LO1LN_0LG1LN (bbch)
BB(16,2)	$f_{\omega +1}^2(10^{10^{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 10^{1,565}$	1RB1LA------_1RC3LB1RB---_2LA2LC---0LC (bbch)
BBi(9)	$10\uparrow 10\uparrow 10\uparrow 3,314,360$	1RB3LA4RB0RB2LA_1LB2LA3LA1RA--- (bbch)
BBi(11)	$10{\uparrow }^{15}4$	1RB3LB---2RA_2LC3RB1LC2RA_3RB1LB3LC2RC (bbch)
BB(14)	$f_{\omega }(10{\uparrow }^{15}4)$	1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC (bbch)
BBi(19)	$f_{\omega }^2(25)$	1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ (bbch)
BBi(21)	$f_{\omega }^2(10{\uparrow }^{2}10)$	1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_---0LI_0LD1LE (bbch)
BBi(23)	$f_{\omega }^4(10{\uparrow }^{2}65,534)$	0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_---1LA_1RF1LL (bbch)
BBi(27)	$f_{\omega +1}(65,536)$	1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM---_0LN1LF_0LJ--- (bbch)
BBi(29)	$f_{\omega +1}(f_{\omega }(10^{57}))$	0RH1LD_1RI0RC_1RB1LD_0LD1LE_1LF1RA_1RG0LE_1RB1RG_1RD1RA_0LN0RJ_---0LK_0LK1LL_1RG1LM_0LL0LL_1LO1LN_0LG1LN (bbch)
BBi(31)	$f_{\omega +1}^2(10^{10^{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(5,2,1)	70	0RB---_0RC1LC_1RD0RE_1RE1RD_1LE1LB (bbch)
BBt(3,3,2)	93	1RB------_0RC0RB1LC_1LB2RC0LB (bbch)
BBt(3,3)	202	1RB2RC1LC_0RC0RB1LA_2LA2RC1LB (bbch)
BBt(4,3,2)	425	1RB------_1RC------_0RD0RC1LD_1LC2RD0LC (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(8)	425	1RB------_1RC------_0RD0RC1LD_1LC2RD0LC (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 10^{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 10^{12}$	1RB2RA1RA2RB_2LB3LA0RB0RA (bbch)

Restricted move per state

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

Domain	Lower Bound	Champion
BBms(2,2,1)	4	0RB_1LA (bbch)
BBms(2,2)	6	1RB---_1LB1LA (bbch)
BBms(3,2,1)	17	1RB---_0RC---_1LC0LA (bbch)
BBms(3,2)	19	1RB1RA_0RC---_1LC0LA (bbch)
BBms(4,2,1)	32	1RB---_1LC---_0LD0LC_1RD0RA (bbch)
BBms(4,2)	75	1RB0RD_0RC0RA_1LC0LA_0RB--- (bbch)
BBms(5,2,1)	87	1RB1RD_1RC---_1RD0RA_1LE0LD_---0LA (bbch)
BBms(5,2)	422	1RB1RA_1RC1RE_1LD---_1LA1LD_---0RB (bbch)

Restricted move per state instructions

Maximum number of steps done by a Turing machine with n defined instructions before halting. TMs must go to the same direction per state. TMs halt when they are on an undefined transititon.

Domain	Lower Bound	Champion
BBmsi(2)	4	0RB_1LA (bbch)
BBmsi(3)	6	1RB---_1LB1LA (bbch)
BBmsi(4)	17	1RB---_0RC---_1LC0LA (bbch)
BBmsi(5)	23	1RB------_0RC------_1LC2LB0LA (bbch)
BBmsi(6)	66	1RB------_1LB0LC---_1RC2RA1RB (bbch)
BBmsi(7)	75	1RB0RD_0RC0RA_1LC0LA_0RB--- (bbch)
BBmsi(8)	87	1RB1RD_1RC---_1RD0RA_1LE0LD_---0LA (bbch)
BBmsi(9)	422	1RB1RA_1RC1RE_1LD---_1LA1LD_---0RB (bbch)

Restricted write per state

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

Domain	Lower Bound	Champion
BBws(2,2)	6	1RB1LB_1LA--- (bbch)
BBws(3,2)	20	1RB---_0LC0RC_1LC1LA (bbch)
BBws(4,2)	53	1RB1LB_1LC1RD_1RA1LA_---0RC (bbch)
BBwsms(5,2)	422	1RB1RA_1RC1RE_1LD---_1LA1LD_---0RB (bbch)

Restricted move and write per state

Maximum number of steps done by a n-state, m-symbol Turing machine with k+1 undefined instructions before halting. TMs must write the same symbol and go to the same direction per state. TMs halt when they are on an undefined transititon.

Domain	Lower Bound	Champion
BBwsms(2,2)	6	1RB---_1LB1LA (bbch)
BBwsms(3,2)	17	1RB---_0RC0RC_1LC1LA (bbch)
BBwsms(4,2)	29	1RB1RD_0LC0LA_1LC1LA_0RC--- (bbch)
BBwsms(5,2)	422	1RB1RA_1RC1RE_1LD---_1LA1LD_---0RB (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)	$10^{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(3,2)	6	1RB1LC_1RC---_1LA0LB (bbch)
BBn(2,3)	9	1RB2LB---_2LA2RB1LB (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{\uparrow }^{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 10^{23}$	1RB2LA1RA1LB_0LB2RB3RB1LA (bbch)
BBP(5,2,1)	$5.418\times 10^{51}$	1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC (bbch)
BBP(5,2)	$10^{14,006}$	1RB1LE_0LC0LB_0LD1LC_1RD1RA_0RC0LA (bbch)
BBP(3,3)	$10{\uparrow }^{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)	45,153	1PB1PA1TA_2TB2PB2PC_---2PA1TC

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)	45,153	1PB1PA1TA_2TB2PB2PC_---2PA1TC

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
TTt(2,2,1)	3	0PB---_1TB1PB
TTt(2,2)	4	1PB0TB_1TA0PB
TTt(2,3,1)	9	1PB2TB---_1TA0PB0TB
TTt(3,2,1)	9	0PB---_1PC1TC_1TB0PC
TTt(3,2)	23	0PB0PC_1PC0TA_1TB1TC
TTt(2,3)	39	2PB1TA1TB_2TA0TA0PB
TTt(2,4,1)	44	1PB2PB0PB---_2TB2TA3TA1TB
TTt(4,2,1)	48	0PB---_1TB1PC_0TB1TD_0PC0PD
TTt(3,3,2)	70	1PB---0PB_0PC---1PC_2TC0TA2PC
TTt(3,3)	134	1PB2PC2TB_1TC0TA0PB_2TC1TA2TA
TTt(4,2)	166	1PB0TB_0PC0TA_0PD0PB_1TB1TA
TTt(2,4)	194	0PB2PB3TB0PA_1TB2TB3PB3TA

Turmite semi-infinite tape instructions

Maximum number of right steps done by a Turmite 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
TTti(3)	3	0PB---_1TB1PB
TTti(4)	8	0PB---_0PC---_1TC1PC
TTti(5)	21	0PB---_0PC---_0PD---_1TC0TD
TTti(6)	39	2PB1TA1TB_2TA0TA0PB
TTti(7)	70	1PB---0PB_0PC---1PC_2TC0TA2PC
TTti(8)	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(4,2)	267	1TB0TD_1PC0PA_0PA0TD_1PD0PB
TLT(2,4)	357	1TB2TB0TB2PA_3TA2PA0PA3PB
TLT(3,3)	2,122	1TB2PA0TA_1TA0TB2PC_2PB0PA0TC

Turmite blanking instructions

Maximum number of steps done by a turmite 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
TLTi(3)	7	1TB0TB_0PA---
TLTi(4)	12	1PB0PA_1TA0TA
TLTi(5)	24	1TB2PB0PA_2TA---0TA
TLTi(6)	108	1TB0TA0PB_2PA2PB0PA
TLTi(8)	357	1TB2TB0TB2PA_3TA2PA0PA3PB
TLTi(9)	2,122	1TB2PA0TA_1TA0TB2PC_2PB0PA0TC

Turmite restricted move per state

Maximum number of steps done by a n-state, m-symbol turmite machine with k+1 undefined instructions before halting. TMs must go to the same direction per state. TMs halt when they are on an undefined transititon.

Domain	Lower Bound	Champion
TTms(2,2,1)	4	1TA0TB
TTms(2,2)	10	1TA1TB_---0PA
TTms(3,2,1)	12	1TA1TB_---0PC_0PA---
TTms(3,2)	25	1TA1TB_0PC0PA_---0PA
TTms(4,2,1)	30	1TA1TB_1PD0PC_0PA---_0PB---
TTms(4,2)	247	1TA1TB_0PD0PC_0PA0PB_0PC---

Turmite restricted move per state instructions

Maximum number of steps done by a turmite machine with n defined instructions before halting. TMs must go to the same direction per state. TMs halt when they are on an undefined transititon.

Domain	Lower Bound	Champion
TTmsi(2)	4	1TA0TB
TTmsi(3)	10	1TA1TB_---0PA
TTmsi(4)	16	1TA1TB_2PB0PA
TTmsi(5)	26	1TA1TB0TA_2PB0PA---
TTmsi(6)	36	1TA1TB0TC_2PB0PA---_0TB------
TTmsi(7)	247	1TA1TB_0PD0PC_0PA0PB_0PC---

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 10^{12}$	(\1 1 1) (\\2 (2 (2 1)))
BBL(11)	$10^{7.625\times 10^{12}}$	(\1 1 1 1) (\\2 (2 (2 1)))
BBL(12)	$10{\uparrow }^{3}16$	(\1 1 1) (\1 (\\2 (2 1)) 1)
BBL(13)	$10{\uparrow }^{3}10{\uparrow }^{3}10{\uparrow }^{2}6$	(\1 1) (\1 (\1 (\\2 (2 1)) 2))
BBL(14)	$10{\uparrow }^{3}10{\uparrow }^{3}10{\uparrow }^{3}16$	(\1 1 1 1 1) (\1 (\\2 (2 1)) 1)
BBL(15)	$f_{\omega +1}(10^{10^{19,727}})$	(\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))
BBL(23)	$f_{{\omega }^2}(4)$	(\1 1 (\\1 (\\1 2 1) 2 1) (\1 1) 1) 1) (\\2 (2 1))
BBL(24)	$f_{{\omega }^2}(27)$	(\1 1 (\\1 (\\1 2 1) 2 1) (\1 1) 1) 1) (\\2 (2 (2 1)))
BBL(25)	$f_{{\omega }^{\omega }}(4)$	(\1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 1))
BBL(26)	$f_{{\omega }^{\omega }}(27)$	(\1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))
BBL(27)	$f_{{\omega }^{\omega }}(10^{12})$	(\1 1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))
BBL(28)	$f_{{\omega }^{\omega }}(10^{10^{12}})$	(\1 1 1 1 (\\\1 3 2 1) (\\1 2 1) (\1 1) 1) (\\\2 (2 (2 1)))
BBL(34)	$f_{{\omega }^{{\omega }^{\omega }}}(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\uparrow 10\uparrow 10\uparrow 10\uparrow 54$	Δ: (())(()()) P: (()()) > (()())(()), (()()) > (()())(()), ()(()) > (())((())), ((())) > ((()))()(), () > _
TRBB(45)	$10{\uparrow }^{3}130$	Δ: ((()))((())) P: ((())) > ((()))(()()), (()()) > (()())(()), (()) > (())(()()()), (()()()) > (()()())()(), ()()() > _, () > _
TRBB(69)	$10{\uparrow }^{4}10{\uparrow }^{2}10{\uparrow }^{2}4$	Δ: ((()))((()())) P: ((()())) > ((()()))((())), ((())) > ((()))(()()()), ((())) > ((()))(()()()), (()()()) > (()()())(()()), (()()) > (()())(())(()), (()) > (())()()()()(), () > _

Fractran

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 10^{62}$	[1/12, 9/10, 14/3, 11/2, 5/7, 3/11]

Brainfuck

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

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*