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.

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.

I will add more functions soon.

Turing Machines

Normal

Domain	Lower Bound	Champion
BB(2)	6	1RB1LB_1LA1RZ (bbch)
BB(3)	21	1RB1RZ_1LB0RC_1LC1LA (bbch)
BB(2,3)	38	1RB2LB1RZ_2LA2RB1LB (bbch)
BB(4)	107	1RB1LB_1LA0LC_1RZ1LD_1RD0RA (bbch)
BB(2,4)	3,932,964	1RB2LA1RA1RA_1LB1LA3RB1RZ (bbch)
BB(5)	47,176,870	1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA (bbch)
BB(3,3)	$1.191\times 10^{17}$	0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC (bbch)
BB(2,5)	$10^{10^{10^{3314360}}}$	1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ (bbch)
BB(2,6)	$10{\uparrow }^{2}10{\uparrow }^{2}10^{10^{115}}$	1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA (bbch)
BB(6)	$10{\uparrow }^{2}10{\uparrow }^{2}10{\uparrow }^{2}8$	1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE (bbch)
BB(4,3)	$10{\uparrow }^{3}10{\uparrow }^{3}10{\uparrow }^{3}10^{28}$	1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_0RB2RA2RD (bbch)
BB(7)	$10{\uparrow }^{11}10{\uparrow }^{10}4$	1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF (bbch)
BB(3,4)	$10{\uparrow }^{15}4$	1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC (bbch)
BB(3,5)	$f_{\omega }(10{\uparrow }^{15}4)$	1RB3LB4LC2RA4LB_2LC3RB1LC2RA1RZ_3RB1LB3LC2RC4LC (bbch)
BB(2,7)

Blanking

Domain	Lower Bound	Champion
BLB(2)	8	1RB0RA_1LB1LA (bbch)
BLB(3)	34	1RB1LB_1LA1LC_1RC0LC (bbch)
BLB(2,3)	77	1RB2LA0RB_1LA0LB1RA (bbch)
BLB(4)	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)	6	0RB1RZ_1LA1RB (bbch)
BBr(3)	17	0RB1RZ_0LC1RA_1RB1LC (bbch)
BBr(4)	48	1RB0LD_0LC0RB_1LA1LD_1LC1RZ (bbch)
BBr(5)	388	1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA (bbch)
BBr(6)	537,556	1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA1RZ_1RF1RA (bbch)
BBr(7)	$10^{19}$	1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ (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

De Bruijn

Domain	Lower Bound	Champion
BBdb(6)	6	\1 1 1 1 1 1
BBdb(7)	15	(\1 1) (\\2 (1 2))
BBdb(8)	67	(\1 1) (\\2 (2 (1 2)))
BBdb(9)	$7.625\times 10^{12}$	(\1 1 1) (\\2 (2 (2 1)))
BBdb(10)	$10^{7.625\times 10^{12}}$	(\1 1 1 1) (\\2 (2 (2 1)))
BBdb(11)	$10{\uparrow }^{3}16$	(\1 1 1) (\1 (\\2 (2 1)) 1)
BBdb(12)	$10{\uparrow }^{3}10{\uparrow }^{3}10{\uparrow }^{2}6$	(\1 1) (\1 (\1 (\\2 (2 1)) 2))
BBdb(13)	$10{\uparrow }^{3}10{\uparrow }^{3}10{\uparrow }^{3}16$	(\1 1 1 1 1) (\1 (\\2 (2 1)) 1)
BBdb(14)	$f_{\omega +1}(10^{10^{65,536}})$	(\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))

Cyclic Tag

Cyclic Tag

Domain	Lower Bound	Champion
CTBB(2)	5	Δ: (()) P: ()() > _, () > ()()
CTBB(3)	38	Δ: ()(()) P: (()) > ((())), ()()() > _, () > ()()
CTBB(4)	672	Δ: ()()()() P: ()() > (()())(), ()() > ()()(()), () > (()), (((()))) > _
CTBB(5)	$10{\uparrow }^{2}4|180$	Δ: (())(()()) P: (()()) > (()())(()), (()()) > (()())(()), ()(()) > (())((())), ((())) > ((()))()(), () > _
CTBB(6)	$10{\uparrow }^{3}129$	Δ: ((()))((())) P: ((())) -> ((()))(()()), (()()) -> (()())(()), (()) -> (())(()()()), (()()()) -> (()()())()(), ()()() -> _, () -> _
CTBB(7)	$10{\uparrow }^{4}10{\uparrow }^{2}10{\uparrow }^{2}4$	Δ: ((()))((()())) P: ((()())) > ((()()))((())), ((())) > ((()))(()()()), ((())) > ((()))(()()()), (()()()) > (()()())(()()), (()()) > (()())(())(()), (()) > (())()()()()(), () > _