User:Azerty/Busy Beaver Functions

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

All functions here grow uncomputably fast like the original Busy Beaver function. There is no function that grow much faster like the Beeping Busy Beaver function here.

Turing machines

Normal

Domain	Lower Bound	Champion
BB(2,2,1)	4	0RB---_1LA--- (bbch)
BB(2,2)	6	1RB1LB_1LA--- (bbch)
BB(3,2,1)	17	1RB---_0RC---_1LC0LA (bbch)
BB(3,2)	21	1RB---_1LB0RC_1LC1LA (bbch)
BB(2,3,1)
BB(2,3)	38	1RB2LB---_2LA2RB1LB (bbch)
BB(4,2)	107	1RB1LB_1LA0LC_---1LD_1RD0RA (bbch)
BB(2,4,1)	124	1RB3LA1RA0LA_2LA------3RA (bbch)
BB(2,4)	3,932,964	1RB2LA1RA1RA_1LB1LA3RB--- (bbch)
BB(5,2)	47,176,870	1RB1LC_1RC1RB_1RD0LE_1LA1LD_---0LA (bbch)
BB(3,3)	$1.191\times 10^{17}$	0RB2LA1RA_1LA2RB1RC_---1LB1LC (bbch)
BB(2,5)	$10{\uparrow }^{2}3|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(3,5)	$f_{\omega }(10{\uparrow }^{15}4)$	1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC (bbch)
BB(2,7)

Blanking

Domain	Lower Bound	Champion
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(2,4)	$1.367\times 10^{12}$	1RB2RA1RA2RB_2LB3LA0RB0RA (bbch)

Reversible

Domain	Lower Bound	Champion
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

Domain	Lower Bound	Champion
BBn(2,2)	4	1RB1LB_1LA--- (bbch)
BBn(3,2)	6	1RB1LC_1RC---_1LA0LB (bbch)
BBn(4,2)	11	1RB0LA_1RC1LB_1LB1RD_---0RA (bbch)
BBn(2,3)
BBn(3,3)
BBn(5,2)	164	1RB1LA_1RC1LE_1RD1RE_0LA1RC_---0LB (bbch)

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(6)	6	\1 1 1 1 1 1
BBL(7)	15	(\1 1) (\\2 (1 2))
BBL(8)	67	(\1 1) (\\2 (2 (1 2)))
BBL(9)	$7.625\times 10^{12}$	(\1 1 1) (\\2 (2 (2 1)))
BBL(10)	$10^{7\times 10^{12}}$	(\1 1 1 1) (\\2 (2 (2 1)))
BBL(11)	$10{\uparrow }^{3}16$	(\1 1 1) (\1 (\\2 (2 1)) 1)
BBL(12)	$10{\uparrow }^{3}10{\uparrow }^{3}10{\uparrow }^{2}6$	(\1 1) (\1 (\1 (\\2 (2 1)) 2))
BBL(13)	$10{\uparrow }^{3}10{\uparrow }^{3}10{\uparrow }^{3}16$	(\1 1 1 1 1) (\1 (\\2 (2 1)) 1)
BBL(14)	$f_{\omega +1}(10^{10^{19,727}})$	(\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))

Cyclic tag

Domain	Lower Bound	Champion
CTBB(1)	1	Δ: () P: () > _
CTBB(2)	5	Δ: (()) P: ()() > _, () > ()()
CTBB(3)	38	Δ: ()(()) P: (()) > ((())), ()()() > _, () > ()()
CTBB(4)	672	Δ: ()()()() P: ()() > (()())(), ()() > ()()(()), () > (()), (((()))) > _
CTBB(5)	$10{\uparrow }^{2}4|54$	Δ: (())(()()) P: (()()) > (()())(()), (()()) > (()())(()), ()(()) > (())((())), ((())) > ((()))()(), () > _
CTBB(6)	$10{\uparrow }^{3}129$	Δ: ((()))((())) P: ((())) -> ((()))(()()), (()()) -> (()())(()), (()) -> (())(()()()), (()()()) -> (()()())()(), ()()() -> _, () -> _
CTBB(7)	$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]

Brainfuck

Brainfuck

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

Boolfuck

Domain	Lower Bound	Champion
BLBB(7)	7	>>>>>>>
BLBB(8)	9	*>*[<<>]
BLBB(9)	10	*>*[<<>]>
BLBB(10)	14	*>*>*[<<>]
BLBB(11)	15	*>*>*[<<>]>
BLBB(12)	20	*>*>*[<<<>>]

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	>>>>>>>><[<]

Register machines

Domain	Lower Bound	Champion
RBB(1)	1	A- > H, 1
RBB(2)	3	A- > H, 2 / A+ > 1
RBB(3)	5	A+ > 2 / B- > H, 3 / B+ > 1
RBB(4)	8	B+ > 2 / B+ > 3 / A+ > 4 / B- > 3, H
RBB(5)	11	B+ > 2 / B+ > 3 / A+ > 4 / A+ > 5 / B- > 3, H
RBB(6)	15	B+ > 2 / B+ > 3 / B+ > 4 / A+ > 5 / A+ > 6 / B- > 4, H