User:Azerty/Busy Beaver Functions: Difference between revisions

Revision as of 18:20, 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)

Semi infinite tape

Domain	Lower Bound	Champion
BBn(2,2,1)	3	`1RB1LA_1LA---` (bbch)
BBn(2,2)	5	`1RB1RB_1LA1LB` (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 198: / Line 198: @@
 |}
-=== Consecutive Ones ===
+=== Consecutive ones ===
 {| class="wikitable"
 !Domain
@@ Line 204: / Line 204: @@
 !Champion
 |-
-|BBn(2[[BB(2)|,2]],1)
+|BBn(2,2,1)
 |2
 |{{TM|1RB---_1LA---|halt}}
 |-
-|BBn(2[[BB(2)|,2]])
+|BBn(2,2)
 |4
 |{{TM|1RB1LB_1LA---|halt}}
@@ Line 216: / Line 216: @@
 |{{TM|1RB1LB_1RC1LC_1LA---|halt}}
 |-
-|BBn(3[[BB(2)|,2]])
+|BBn(3,2)
 |6
 |{{TM|1RB1LC_1RC---_1LA0LB|halt}}
 |-
-|BBn(4[[BB(2)|,2]])
+|BBn(4,2)
 |12
 |{{TM|1RB0LA_1RC1LB_1LB1RD_---0RA|halt}}
@@ Line 228: / Line 228: @@
 |{{TM|1RB1RA---_1LC1LC2LA_2RA1LB1LA|halt}}
 |-
-|BBn(5[[BB(2)|,2]])
+|BBn(5,2)
 |165
 |{{TM|1RB1LA_1RC1LE_1RD1RE_0LA1RC_---0LB|halt}}
+|}
+=== Semi infinite tape ===
+{| class="wikitable"
+!Domain
+!Lower Bound
+!Champion
+|-
+|BBn(2,2,1)
+|3
+|{{TM|1RB1LA_1LA---|halt}}
+|-
+|BBn(2,2)
+|5
+|{{TM|1RB1RB_1LA1LB|halt}}
 |}
 == Lambda calculus ==
-=== SK Calculus ===
+=== SK calculus ===
 {| class="wikitable"
 !Domain
@@ Line 262: / Line 277: @@
 |}
-=== BCKW Calculus ===
+=== BCKW calculus ===
 {| class="wikitable"
 !Domain

User:Azerty/Busy Beaver Functions: Difference between revisions

Revision as of 18:20, 6 December 2025

Contents

Turing machines

Normal

Blanking

Reversible

Consecutive ones

Semi infinite tape

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 18:20, 6 December 2025

Turing machines

Normal

Blanking

Reversible

Consecutive ones

Semi infinite tape

Lambda calculus

SK calculus

BCKW calculus

De Bruijn

Cyclic tag

Fractran

Brainfuck

Brainfuck

Boolfuck

BitChanger

Bitter

Register machines

Navigation menu

Search