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 grow uncomputably faster than BB(n), like BBB(n).
• The function must not have similar champions to other function, like Σ(n).
• The function must not be unecessary complex.

Turing machines

Classic

Maximum number of steps done by a n-state, m-symbol Turing Machine with k+1 undefined transitions 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)	139	1RB1LB_1LA0LC_---1LD_1RE1LE_---0RA (bbch)
BB(3,3,1)	3,932,964	1RB2LA1RA_1LC1LA2RB_---1LA--- (bbch)
BB(2,4)	3,932,964	1RB2LA1RA1RA_1LB1LA3RB--- (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(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)

Blanking

Maximum number of steps done by a n-state, m-symbol Turing Machine with k undefined transitions 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)	3	1RB0LA_0LA--- (bbch)
BLB(2,2)	8	1RB0RA_1LB1LA (bbch)
BLB(3,2)	34	1RB1LB_1LA1LC_1RC0LC (bbch)
BLB(2,3)	77	1RB2LA0RB_1LA0LB1RA (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)

Reversible

Maximum number of steps done by a n-state, m-symbol reversible Turing Machine with k+1 undefined 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 transitions 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)

Semi-infinite tape

Maximum number of right steps done by a n-state, m-symbol Turing Machine with k undefined transitions 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)	22	3RB2LB1RB1RA_2LA2RB1LA--- (bbch)
BBt(4,2,1)	26	1RB---_1RC0LD_0RD0RC_1LC1LD (bbch)
BBt(2,4)	33	3RB2LB1RA2RB_3LB2RA1LA0RA (bbch)
BBt(4,2)	60	1RB1RC_0RD0RC_1RD1LD_1LA0LB (bbch)
BBt(3,3,2)	70	1RB---2RB_2RC---1RC_2LC2RA0RC (bbch)
BBt(3,3,1)	70	1RB---2RB_2RC---1RC_2LC2RA0RC (bbch)
BBt(3,3)	156	2RB0LA1RC_1LA2LB1RB_2LC0RC0RB (bbch)

Preperiodic

Maximum number of steps done by a n-state, m-symbol Turing Machine with k undefined transitions 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 transitions.

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)	336	2RB0LA1RC_1LA2LB1RB_2LC0RC0RB (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)

Turmite

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

Domain	Lower Bound	Champion
TT(2,2,1)	6	0PB---_1TA---
TT(2,2)	13	1TB---_1PA0PB
TT(3,2,1)	20	1TB---_1PC0PB_1PA---
TT(2,3,1)	20	1TB------_1PA2PB0PB
TT(3,2)	82	1PB0PA_1TA0PC_1PA---
TT(2,3)	223	1TB0PA2PA_2PA---1PA
TT(4,2)	758	1TB---_0PD1PB_1PA1TA_0PC0PD
TT(2,4)	1,068	1TB3TB2PB---_2TB1PA0PA2TB

Lambda calculus

SK calculus

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

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

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)))

Tag system

2-tag system

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

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 rewrite

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

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

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

Boolfuck

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

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

Bitter

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

Minsky machines

Domain	Lower Bound	Champion
MBB(1)	1	0+Z
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*