User:Azerty/Busy Beaver Functions: Difference between revisions

Revision as of 10:14, 6 December 2025

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.

Turing machines

Normal

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)	678	`1RB1LB1LA_2RC2RB---_0LA1RC---` (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 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)

Blanking

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(2,4)	$1.367 \times 1 0^{12}$	`1RB2RA1RA2RB_2LB3LA0RB0RA` (bbch)

Reversible

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

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)

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 1 0^{12}$	`(\1 1 1) (\\2 (2 (2 1)))`
BBL(10)	$1 0^{7 \times 1 0^{12}}$	`(\1 1 1 1) (\\2 (2 (2 1)))`
BBL(11)	$10 ↑^{3} 16$	`(\1 1 1) (\1 (\\2 (2 1)) 1)`
BBL(12)	$10 ↑^{3} 10 ↑^{3} 10 ↑^{2} 6$	`(\1 1) (\1 (\1 (\\2 (2 1)) 2))`
BBL(13)	$10 ↑^{3} 10 ↑^{3} 10 ↑^{3} 16$	`(\1 1 1 1 1) (\1 (\\2 (2 1)) 1)`
BBL(14)	$f_{ω + 1} (1 0^{1 0^{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 ↑ 10 ↑ 10 ↑ 10 ↑ 54$	Δ: (())(()()) P: (()()) > (()())(()), (()()) > (()())(()), ()(()) > (())((())), ((())) > ((()))()(), () > _
CTBB(6)	$10 ↑^{3} 130$	Δ: ((()))((())) P: ((())) -> ((()))(()()), (()()) -> (()())(()), (()) -> (())(()()()), (()()()) -> (()()())()(), ()()() -> _, () -> _
CTBB(7)	$10 ↑^{4} 10 ↑^{2} 10 ↑^{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

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`

@@ Line 94: / Line 94: @@
 |<math>10 \uparrow^{15} 4</math>
 |{{TM|1RB3LB---2RA_2LC3RB1LC2RA_3RB1LB3LC2RC|halt}}
+|-
+|BB(9,2)
+|<math>f_\omega(10 \uparrow^{7} 10 \uparrow^{7} 2)</math>
+|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_1LB0LH|halt}}
 |-
 |BB(3,5)
 |<math>f_{\omega}(10 \uparrow^{15} 4)</math>
 |{{TM|1RB3LB4LC2RA4LB_2LC3RB1LC2RA---_3RB1LB3LC2RC4LC|halt}}
-|-
-|BB(9,2)
-|<math>f_\omega(10 \uparrow^{7} 10 \uparrow^{6} 10)</math>
-|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_---0RA_1LB1LF_1LH1RE_0LI1LH_1LB0LH|halt}}
 |-
 |BB(10,2)
@@ Line 363: / Line 363: @@
 |-
 |CTBB(6)
-|<math>10 {\uparrow}^{3} 129</math>
+|<math>10 {\uparrow}^{3} 130</math>
 |Δ: ((()))((())) P: ((())) -> ((()))(()()), (()()) -> (()())(()), (()) -> (())(()()()), (()()()) -> (()()())()(), ()()() -> _, () -> _
 |-

User:Azerty/Busy Beaver Functions: Difference between revisions

Revision as of 10:14, 6 December 2025

Contents

Turing machines

Normal

Blanking

Reversible

Consecutive Ones

Lambda calculus

SK Calculus

BCKW Calculus

De Bruijn

Cyclic tag

Fractran

Brainfuck

Brainfuck

Boolfuck

BitChanger

Bitter

Register machines

Navigation menu

User:Azerty/Busy Beaver Functions: Difference between revisions

Revision as of 10:14, 6 December 2025

Turing machines

Normal

Blanking

Reversible

Consecutive Ones

Lambda calculus

SK Calculus

BCKW Calculus

De Bruijn

Cyclic tag

Fractran

Brainfuck

Brainfuck

Boolfuck

BitChanger

Bitter

Register machines

Navigation menu

Search