A collection of Busy Beaver Champions including Champions for BB-Adjacent functions . Note that for all functions with the input format f(n,m), n denotes the number of states and m denotes the number of symbols of the relevant Busy Beaver domain. Note that for functions with this input format f(n) = f(n,2).
Note: highest ref name in use: 4
State-and-Symbol-Limited Busy Beaver functions
Busy Beaver functions where the programs size is limited by the amount of states and symbols.
Original Busy Beaver Functions
Maximum Shifts Function (S(n,m) , also commonly called BB(n,m))
Maximum amount of steps a Turing machine with n states and m symbols can run for before halting when started on the blank tape.
2 Symbols:
Runtime
Champions
BB(1)
1
1RZ--- (bbch )
BB(2)
6
1RB1LB_1LA1RZ (bbch ) 1RB0LB_1LA1RZ (bbch ) 1RB1RZ_1LB1LA (bbch ) 1RB1RZ_0LB1LA (bbch ) 0RB1RZ_1LA1RB (bbch )
BB(3)
21
1RB1RZ_1LB0RC_1LC1LA (bbch )
BB(4)
107
1RB1LB_1LA0LC_1RZ1LD_1RD0RA (bbch )
BB(5)
47,176,870
1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA (bbch )
BB(6)
> 10 ↑↑ 10 ↑↑ 10 ↑↑ 8.10237
1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE (bbch )
BB(7)
> 2 ↑ 1 1 2 ↑ 1 1 3
1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF (bbch )
BB(8)
BB(9)
> f ω ( f 9 ( 2 ) )
1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_1LB0LH (bbch )
BB(10)
> f ω 2 ( 2 5 )
1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ (bbch )
BB(11)
> f ω 2 ( 2 ↑ ↑ 1 2 ) > f ω 2 ( f 3 ( 9 ) )
1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RZ0LI_0LD1LE (bbch )
BB(12)
> f ω 4 ( 2 ↑ ↑ ↑ 4 − 3 ) > f ω 4 ( f 4 ( 2 ) )
0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL (bbch )
BB(13)
> f ω + 1 ( 2 0 4 6 ) > g 6 4
1RB1RA_1LC1RD_1LA1LC_1LG0RE_1LC1RB_0RL1LG_0LM0RH_1RI1RH_1LK0RI_---0LK_1LF1LK_1LJ1RL_1RZ1RH (bbch )
BB(14)
> f ω + 1 ( 6 5 5 3 6 )
1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LF_0LJ--- (bbch )
BB(15)
> f ω + 1 ( f ω ( 1 0 5 7 ) )
0RH1LD_1RI0RC_1RB1LD_0LD1LE_1LF1RA_1RG0LE_1RB1RG_1RD1RA_0LN0RJ_1RZ0LK_0LK1LL_1RG1LM_0LL0LL_1LO1LN_0LG1LN (bbch )
BB(16)
> f ω + 1 2 ( 1 0 1 0 5 7 )
BB(18)
> f ω + 2 ( f ω + 1 3 ( f ω 2 ( 6 0 ) ) )
BB(20)
> f ω + 2 2 ( 2 1 )
BB(21)
> f ω 2 2 ( 4 ↑ ↑ 3 4 1 )
BB(40)
> f ω ω ( 7 5 5 0 0 )
BB(41)
> f ω ω 4 ( 3 2 )
BB(51)
> f ε 0 + 1 ( 8 )
Maximum Score Function (Σ(n,m) )
Maximum amount of non-zero symbols a Turing machine with n states and m symbols can leave on the tape before halting when started on the blank tape.
Beeping Busy Beavers
Beeping Busy Beaver (BBB (n,m))
Considering beep states
4 Symbols:
Steps taken
Champions
BBB(1,4)
BBB(2,4)
≥ 2 0 5 7 7 0 0 7 6 4 3 3 0 4 4 2 4 2 2 4 7 8 5 9 > 2 × 1 0 2 3 [ 5]
1RB2LA1RA1LB_0LB2RB3RB1LA (bbch )
Beeping Booping Busy Beaver (BBBB (n,m))
2 Symbols:
Steps taken
Champions
BBBB(1)
2
BBBB(2)
17
Maximum Consecutive Ones Function (Num (n,m))
Maximum Space Function (BBspace (n,m))
2 Symbols:
Cells visited
Champions
BBspace (1,2)
1
1RZ--- (bbch )
BBspace (2,2)
4
1RB1LB_1LA1RZ (bbch ) and 1RB0LB_1LA1RZ (bbch )
BBspace (3,2)
7
1RB1RC_1LC1RZ_1RA0LB (bbch ) and 1RB0RC_1LC1RZ_1RA0LB (bbch )
BBspace (4,2)
16
1RB0RA_1LC0RD_0LD0LB_1RA1RZ (bbch )
BBspace (5,2)
12289
1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA (bbch )
Size of the runtime spectrum (R(n,m))
There currently doesn't seem to be any available information about values of this function.
Reversible Turing Machines
Maximum Shifts Function (BBrev (n,m))
2 Symbols:
Steps
Champions
BBrev (1)
BBrev (2)
6
0RB1RZ_1LA1RB (bbch )
BBrev (3)
17
0RB1RZ_0LC1RA_1RB1LC (bbch )
BBrev (4)
48
1RB0LD_0LC0RB_1LA1LD_1LC1RZ (bbch )
BBrev (5)
388
1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA (bbch )
BBrev (6)
≥ 537,556
1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA1RZ_1RF1RA (bbch )
BBrev (7)
> 1 0 1 9
1RB1LD_0LC0LD_1LC1LA_0LA1RE_0RF0RE_0RG1RF_0RB1RZ (bbch )
Maximum Score Function (Σrev (n,m))
2 Symbols:
Score
Champions
Σrev (1)
Σrev (2)
≥ 2
0RB1RZ_1LA1RB (bbch )
Σrev (3)
≥ 4
0RB1RZ_0LC1RA_1RB1LC (bbch )
Σrev (4)
≥ 6
1RB0LD_0LC0RB_1LA1LD_1LC1RZ (bbch )
Σrev (5)
≥ 16
1RB0RD_1RC0RB_1RD1RZ_1LE1LA_0LE0LA (bbch )
Σrev (6)
≥ 1161
1RB1LD_1LC1RE_0LD0LC_0RE0RF_0RA1RZ_1RF1RA (bbch )
Blanking Busy Beaver (BLB(n,m) )
5 Symbols:
Steps
Champions
BLB(2,5)
> 1032
1RB2RB4RA0RB2RA_2LB3LA0RB0RA1RB (bbch )
Lazy Beaver
Shifts Function (LB (n,m))
1 State
2 States
3 States
4 States
5 States
6 States
2 Symbols
2
7
22
72
427
8407
3 Symbols
2
23
351
189,270
4 Symbols
2
93
242,789
5 Symbols
2
956
6 Symbols
2
33,851
Period-oriented Busy Beavers
Busy Preperiodic Beaver (BBS (n,m))
4 Symbols:
Preperiod
Champions
BBS(1,4)
0
1RA--------- (bbch )
BBS(2,4)
≥ 205,770,076,433,044,242,247,860
1RB2LA1RA1LB_0LB2RB3RB1LA (bbch )
Busy Periodic Beaver (BBP (n,m))
2 Symbols:
Period
Champions
BBP(1,2)
1
1RA--- (bbch )
BBP(2,2)
≥ 9
1RB0RB_1LB1RA (bbch ) proven winner?
BBP(3,2)
92
1RB0LA_0RC1LA_1LC0RB (bbch )
BBP(4,2)
≥ 212,081,736
1RB0LA_0RC1RD_1LD0RB_1LA1RB (bbch )
3 Symbols:
Period
Champions
BBP(1,3)
1
1RA------ (bbch )
BBP(2,3)
BBP(3,3)
≥ 1,195
1RB2RC1LC_0RC0RB1LA_2LA2RC1LB (bbch )
4 Symbols:
Period
Champions
BBP(1,4)
1
1RA--------- (bbch )
BBP(2,4)
≥ 33,209,131
1RB0RA3LB1RB_2LA0LB1RA2RB (bbch )
Instruction-Limited Busy Beaver
Instruction-Limited Classical Busy Beaver Functions
Instruction-Limited Maximum Shifts Function (BBi (n))
Instruction-Limited Maximum Score Function (Σi (n))
Instruction-Limited Blanking Busy Beaver (BLBi(n) )
Steps
Champions
BLBi(1)
nonexistent
nonexistent
BLBi(2)
nonexistent
nonexistent
BLBi(3)
4
1RB0RA_1LA--- (bbch )
BLBi(4)
12
1RB---_1RC---_1LC0RC (bbch )
BLBi(5)
30
1RB------_1RC------_2LC2RC0RC (bbch )
BLBi(6)
77
1RB2LA0RB_1LA0LB1RA (bbch )
BLBi(7)
808
1RB------_1RC------_0RD2LC---_1LD2RD0RC (bbch )
BLBi(8)
≥ 1,367,361,263,049
1RB2RA1RA2RB_2LB3LA0RB0RA (bbch )
BLBi(9)
> 1042,745
1RB2RB1LA_2LC0LB2LB_2RC2RA0LC (bbch )
Instruction-Limited Greedy Busy Beaver (gBBi(n) )
Steps
Champions
gBBi(1)
1
gBBi(2)
3
gBBi(3)
5
gBBi(4)
13
gBBi(5)
19
gBBi(6)
25
gBBi(7)
41
gBBi(8)
55
gBBi(9)
238
gBBi(10)
941
gBBi(11)
1341
gBBi(12)
10465
gBBi(13)
10675
gBBi(14)
≥ 9,874,580
0RB6RB1LB---3LA1RB7RB2LB_1LA2RB3LA4RB5RB1LB5LA--- (bbch )
Program-Limited Busy Beaver
Busy Beaver for Lambda Calculus
Regular Busy Beaver for Lambda Calculus (BBλ (n))
For n = 0,1,2,3,5 BBλ(n) is undefined, while for the rest of 2 0 ≥ n BBλ(n) = n.
BBλ(n)
Champions
BBλ(4)
4
λ 1
BBλ(6)
6
λ λ 1
BBλ(7)
7
λ λ 2
BBλ(8)
8
λ λ λ 1
BBλ(9)
9
λ λ λ 2
BBλ(10)
10
λ λ λ λ 1
BBλ(11)
11
λ λ λ λ 2
BBλ(12)
12
λ λ λ λ λ 1
BBλ(13)
13
λ λ λ λ λ 2
BBλ(14)
14
λ λ λ λ λ λ 1
BBλ(15)
15
λ λ λ λ λ λ 2
BBλ(16)
16
λ λ λ λ λ λ λ 1
BBλ(17)
17
λ λ λ λ λ λ λ 2
BBλ(18)
18
λ λ λ λ λ λ λ λ 1
BBλ(19)
19
λ λ λ λ λ λ λ λ 2
BBλ(20)
20
λ λ λ λ λ λ λ λ λ 1
BBλ(21)
22
λ ( 1 ( λ 2 ) ) ( 1 ( λ 2 ) )
BBλ(22)
24
λ ( 1 1 ) ( 1 1 ) ( 1 1 )
BBλ(23)
26
λ ( 1 ( λ λ 2 ) ) ( 1 ( λ λ 2 ) )
BBλ(24)
30
λ ( 1 ( λ 1 ) ) ( 1 ( λ 1 ) ) ( 1 ( λ 1 ) )
BBλ(25)
42
λ 1 ( λ 1 ( 2 1 ) ) ( 1 ( 1 ( λ 1 ( 2 1 ) ) ) )
BBλ(26)
52
λ λ 2 ( λ λ 2 ( 1 2 ) ) ( 1 ( 2 ( λ λ 2 ( 1 2 ) ) ) )
BBλ(27)
44
λ λ 1 ( λ 1 ( 2 1 ) ) ( 1 ( 1 ( λ 1 ( 2 1 ) ) ) )
BBλ(28)
58
λ 1 ( λ λ 1 ( 3 ( λ 2 ) ) ) ( 1 ( λ 2 ( λ λ 1 ( 4 ( λ 2 ) ) ) ) )
BBλ(29)
223
λ ( λ 1 1 ) ( λ 1 ( 1 ( 2 1 ) ) )
BBλ(30)
160
( λ 1 1 1 ) ( λ λ 2 ( 1 2 ) )
BBλ(31)
267
( λ 1 1 ) ( λ λ 2 ( 2 ( 1 2 ) ) )
BBλ(32)
298
λ ( λ 1 1 ) ( λ 1 ( 1 ( 2 ( λ 2 ) ) ) )
BBλ(33)
1812
λ ( λ 1 1 ) ( λ 1 ( 1 ( 1 ( 2 1 ) ) ) )
BBλ(34)
327,686
( λ 1 1 1 1 ) ( λ λ 2 ( 2 1 ) )
BBλ(35)
5 × 3 3 3 + 6 = 3 8 1 2 7 9 8 7 4 2 4 9 4 1 > 3 . 8 × 1 0 1 3
( λ 1 1 1 ) ( λ λ 2 ( 2 ( 2 1 ) ) )
BBλ(36)
5 × 2 2 2 3 + 6 > 5 . 7 × 1 0 7 7
( λ 1 1 ) ( λ 1 ( 1 ( λ λ 2 ( 2 1 ) ) ) )
BBλ(37)
B B λ ( 3 5 ) + 2 = 5 × 3 3 3 + 8 = 3 8 1 2 7 9 8 7 4 2 4 9 4 3 > 3 . 8 × 1 0 1 3
λ ( λ 1 1 1 ) ( λ λ 2 ( 2 ( 2 1 ) ) )
BBλ(38)
5 × 2 2 2 2 2 + 6 > 1 0 1 9 7 2 9
( λ 1 1 1 1 1 ) ( λ λ 2 ( 2 1 ) )
BBλ(39)
5 × 3 3 3 3 + 6 > 1 0 3 6 3 8 3 3 4 6 4 0 0 2 4
( λ 1 1 1 1 ) ( λ λ 2 ( 2 ( 2 1 ) ) )
BBλ(40)
≈ ( 2 ↑ ↑ ) 1 5 3 3 > 1 0 ↑ ↑ ↑ 1 6
( λ 1 1 1 ) ( λ 1 ( λ λ 2 ( 2 1 ) ) 1 )
BBλ(41)
5 × 3 3 8 5 + 6 > 1 0 1 . 7 × 1 0 4 0
( λ 1 ( λ 1 1 ) 1 ) ( λ λ 2 ( 2 ( 2 1 ) ) )
BBλ(42)
≥ B B λ ( 4 0 ) + 2 > ( 2 ↑ ↑ ) 1 5 3 3 > 1 0 ↑ ↑ ↑ 1 6
λ ( λ 1 1 1 ) ( λ 1 ( λ λ 2 ( 2 1 ) ) 1 )
BBλ(43)
> 2 ↑ ↑ ↑ 2 ↑ ↑ ↑ 2 ↑ ↑ 8
( λ 1 1 ) ( λ 1 ( λ 1 ( λ λ 2 ( 2 1 ) ) 2 ) )
BBλ(44)
> 1 0 ↑ ↑ ↑ 1 0 ↑ ↑ ↑ 1 6
( λ 1 1 1 1 ) ( λ 1 ( λ λ 2 ( 2 1 ) ) 1 )
BBλ(45)
≥ B B λ ( 4 3 ) + 2 > 2 ↑ ↑ ↑ 2 ↑ ↑ ↑ 2 ↑ ↑ 8
λ ( λ 1 1 ) ( λ 1 ( λ 1 ( λ λ 2 ( 2 1 ) ) 2 ) )
BBλ(46)
≥ B B λ ( 4 4 ) + 2 > 1 0 ↑ ↑ ↑ 1 0 ↑ ↑ ↑ 1 6
λ ( λ 1 1 1 1 ) ( λ 1 ( λ λ 2 ( 2 1 ) ) 1 )
BBλ(47)
> f ω ( f 5 ( 2 ) )
( λ 1 1 1 ) ( λ λ 1 ( 1 2 ) ( λ λ 2 ( 2 1 ) ) )
BBλ(48)
> 1 0 ↑ ↑ ↑ 1 0 ↑ ↑ ↑ 1 0 ↑ ↑ ↑ 1 6
( λ 1 1 1 1 1 ) ( λ 1 ( λ λ 2 ( 2 1 ) ) 1 )
BBλ(49)
> f ω + 1 ( 2 ↑ ↑ 6 2 ) > Graham's Number
( λ 1 1 ) ( λ 1 ( 1 ( λ λ 1 2 ( λ λ 2 ( 2 1 ) ) ) ) )
BBλ(61)
> f ω 2 ↑ ↑ 1 8 − 1 ( 2 )
( λ 1 1 1 ) ( λ 1 ( 1 ( λ λ λ 1 3 2 ( λ λ 2 ( 2 1 ) ) ) ) )
BBλ(86)
> f ω ω 2 ( 2 )
( λ 1 ( λ λ λ λ 1 4 4 4 3 2 1 ) 1 1 1 1 ) ( λ λ 2 ( 2 1 ) )
BBλ(90)
> f ζ 0 ( 1 5 )
( λ 1 1 ( λ λ λ λ 1 4 4 4 3 2 1 ) 1 1 1 1 ) ( λ λ 2 ( 2 1 ) )
BBλ(94)
> f ψ ( Ω ω ) ( 1 2 )
( λ 1 1 1 ( λ λ λ λ 1 4 4 4 3 2 1 ) 1 1 1 1 ) ( λ λ 2 ( 2 1 ) )
BBλ(95)
> f ψ ( Ω ω ) ( 2 3 )
( λ 1 1 ( λ λ λ λ 1 4 4 4 3 2 1 ) 1 1 1 1 ) ( λ λ 2 ( 2 ( 2 1 ) ) )
BBλ(96)
> f ψ ( Ω ω ) ( f ω ω 2 ( 2 ) )
( λ 1 ( λ 1 ( λ λ λ λ 1 4 4 4 3 2 1 ) 1 1 1 1 ) 1 ) ( λ λ 2 ( 2 1 ) )
BBλ(100)
> f ψ ( Ω ω ) + 1 ( 4 )
( λ 1 1 ( λ 1 ( λ λ λ λ 1 4 4 4 3 2 1 ) 1 1 1 1 ) 1 ) ( λ λ 2 ( 2 1 ) )
BBλ(201)
> q(5)
too large to show
BBλ(331)
lim(BMS)
too large to show
BBλ(1850)
> Loader's Number
too large to show
Oracle Busy Beaver for Lambda Calculus (BBλ1 (n) )
Note that f ( n ) = 6 + 5 × B B λ ( n ) .
BBλ1 (n)
Champions
BBλ1 (1)
0
BBλ1 (2)
1
1
BBλ1 (3)
0
BBλ1 (4)
4
λ 1
BBλ1 (5)
5
λ 2
BBλ1 (6)
6
λ λ 1
BBλ1 (7)
7
λ λ 2
BBλ1 (8)
26
1 ( λ 1 )
BBλ1 (9)
9
λ λ 2
BBλ1 (10)
36
1 ( λ λ 1 )
BBλ1 (11)
41
1 ( λ λ 2 )
BBλ1 (12)
266
1 ( 1 ( λ 1 ) )
BBλ1 (13)
51
1 ( λ λ 2 )
BBλ1 (14)
f ( 3 6 ) = 2 5 × 2 2 2 3 + 3 6 > 2 . 8 5 × 1 0 7 8
1 ( 1 ( λ λ 1 ) )
BBλ1 (15)
f ( 4 1 ) ≥ 2 5 × 3 3 8 5 + 3 6 > 1 0 1 . 7 × 1 0 4 0
1 ( 1 ( λ λ 2 ) )
BBλ1 (16)
f ( 2 6 6 )
1 ( 1 ( 1 ( λ 1 ) ) )
BBλ1 (17)
f ( 5 1 )
1 ( 1 ( λ λ λ 2 ) )
BBλ1 (18)
f 4 ( 4 ) = f ( f ( 2 6 6 ) )
1 ( λ 1 ) 1 ( λ 1 )
BBλ1 (19)
f 3 ( 7 ) = f ( f ( 4 1 ) )
1 ( 1 ( 1 ( λ λ 2 ) ) )
BBλ1 (20)
f 6 ( 4 ) = f 4 ( 2 6 6 )
1 ( λ λ 1 ) 1 ( λ 1 )
BBλ1 (21)
f 7 ( 4 ) = f 5 ( 2 6 6 )
1 ( λ λ 2 ) 1 ( λ 1 )
BBλ1 (22)
f 5 2 ( 4 ) = f 5 0 ( 2 6 6 )
1 ( 1 ( λ 1 ) ) 1 ( λ 1 )
BBλ1 (28)
≥ f B B λ ( f 3 ( 4 ) ) ( 4 )
1 ( λ 1 ) 1 ( λ 1 ) 1 ( λ 1 )
BBλ1 (29)
≥ f B B λ ( f B B λ ( f 4 ( 4 ) ) + 4 ( 4 ) ) + B B λ ( f 4 ( 4 ) ) + 5 ( 4 )
1 ( λ 1 ) ( λ 1 2 1 ) ( λ 1 )
Busy Beaver for De Bruijn Lambda Calculus
n
Value
Champion
7
≥ 7
\1 1 1 1 1 1
8
≥ 16
(\1 1) (\\2 (1 2))
9
≥ 68
(\1 1) (\\2 (2 (1 2)))
10
> 7 . 6 2 5 × 1 0 1 2
(\1 1 1) (\\2 (2 (2 1)))
11
> 1 0 7 . 6 2 5 × 1 0 1 2
(\1 1 1 1) (\\2 (2 (2 1)))
12
> 1 0 ↑ 3 1 6
(\1 1 1) (\1 (\\2 (2 1)) 1)
13
> 1 0 ↑ 3 1 0 ↑ 3 1 0 ↑ 2 6
(\1 1) (\1 (\1 (\\2 (2 1)) 2))
14
> f ω ( f 5 ( 2 ) )
(\1 1 1) (\\1 (1 2) (\\2 (2 1)))
15
> f ω + 1 ( 1 0 1 0 1 9 , 7 2 7 )
(\1 1) (\1 (1 (\\1 2 (\\2 (2 1)))))
18
> f ω ω ( 2 ↑ ↑ 1 8 )
(\1 1 1) (\1 (1 (\\\1 3 2 (\\2 (2 1)))))
22
> f ω ω + 2 ( 2 )
(\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 1))
23
> f ζ 0 ( 1 5 )
(\1 1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 1))
24
> f ψ ( Ω ω ) ( 1 2 )
(\1 1 1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) (\\2 (2 1))
25
> f ψ ( Ω ω ) ( f ω ω + 2 ( 2 ) )
(\1 (\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) 1) (\\2 (2 1))
26
> f ψ ( Ω ω + 1 ) ( 4 )
(\1 1 (\1 (\\\\1 4 4 4 3 2 1) 1 1 1 1) 1) (\\2 (2 1))
Busy Beaver for SKI calculus
Ξ₀(n)
Champion
Ξ₀(1)
1
S
Ξ₀(2)
2
SS
Ξ₀(3)
3
SSS
Ξ₀(4)
4
SSSS
Ξ₀(5)
6
SSS(SS)
Ξ₀(6)
17
SSS(SI)S
Ξ₀(7)
≥ 41
SSS(S(SS))S
Ξ₀(8)
≥ 80
SSK(S(SS)S)S
Ξ₀(9)
≥ 169
S(SS)(SS)(SS)SS
Ξ₀(10)
≥ 376
S(S(SS(KK)))(SS)(SS)
Ξ₀(11)
≥ 912
S(SS)S(SS)(S(S(KS))S)
Ξ₀(12)
≥ 2↑2↑513*8-2
S(SI)(SSK)(S(S(KS)K)I)
Ξ₀(13)
> 2↑↑2↑↑2↑258
SI(SI)(SSK)(S(S(KS)K)I)
Ξ₀(14)
> 2↑↑2↑↑2↑258
SI(SI)(SSK)(S(S(KS)K)I)S
Ξ₀(15)
> 2↑↑2↑↑2↑↑34
S(S(SI)I(SSK))I(S(S(KS)K)I)
Ξ₀(16)
> 2↑↑↑19
S(S(SI))I(S(SSK)(K(S(S(KS)K)I)))
Ξ₀(17)
> 2↑↑↑↑2↑↑2↑↑258
S(SS(SSS)I)(SSK)(S(S(KS)K)I)
Ξ₀(18)
> 2↑↑↑↑2↑↑2↑↑258
S(SS(SSS)I)(SSK)(S(S(KS)K)I)S
Ξ₀(19)
> 2↑↑↑↑2↑↑2↑↑258
S(SS(SSS)I)(SSK)(S(S(KS)K)I)(SS)
Ξ₀(20)
> fω+1 (2↑↑7/2-1) > Graham's Number
S(S(S(SI)))I(S(K(S(SS(K(K(S(S(KS)K)I))))))K)
Ξ₀(27)
> fω+2 (2↑2↑21)
SI(SI(SI(S(S(K(SS(KI))))I)))(S(K(S(SSK)))K)(S(S(KS)K)I)
Ξ₀(28)
> fω+2 (2↑2↑21)
S(SI(SI(SI(S(S(K(SS(KI))))I)))(S(K(S(SSK)))K)(S(S(KS)K)I))
Ξ₀(29)
> fω+3 (2↑2↑21)
SI(SI(SI(SI(S(S(K(SS(KI))))I))))(S(K(S(SSK)))K)(S(S(KS)K)I)
Ξ₀(30)
> fω+3 (2↑2↑21)
S(SI(SI(SI(SI(S(S(K(SS(KI))))I))))(S(K(S(SSK)))K)(S(S(KS)K)I))
Ξ₀(31)
> fω+4 (2↑2↑21)
SI(SI(SI(SI(SI(S(S(K(SS(KI))))I)))))(S(K(S(SSK)))K)(S(S(KS)K)I)
Ξ₀(32)
> fω+4 (2↑2↑21)
S(SI(SI(SI(SI(SI(S(S(K(SS(KI))))I)))))(S(K(S(SSK)))K)(S(S(KS)K)I))
Busy Beaver for SK calculus
Ξ₀SK(n)
Champion
Ξ₀SK(n) (1)
1
S
Ξ₀SK(n) (2)
2
SS
Ξ₀SK(n) (3)
3
SSS
Ξ₀SK(n) (4)
4
SSSS
Ξ₀SK(n) (5)
6
SSS(SS)
Ξ₀SK(n) (6)
10
SSS(SS)S
Ξ₀SK(n) (7)
≥ 41
SSS(S(SS))S
Ξ₀SK(n) (8)
≥ 80
SSK(S(SS)S)S
Ξ₀SK(n) (9)
≥ 169
S(SS)(SS)(SS)SS
Ξ₀SK(n) (10)
≥ 376
S(S(SS(KK)))(SS)(SS)
Ξ₀SK(n) (11)
≥ 912
S(SS)S(SS)(S(S(KS))S)
Ξ₀SK(n) (12)
≥ 1530
S(SS)(SS)(SS(SS(SS)))S
Ξ₀SK(n) (13)
≥ 7811
S(SS)(SS)(SS(SS(SSS)))S
Ξ₀SK(n) (14)
≥ 2↑2097156*13-2
SSS(SSK)(SS(SK)(S(KS)K))
Ξ₀SK(n) (15)
≥ 2↑2↑2097156*3-2
SSS(SSK)(SS(SK)(S(KS)K))S
Ξ₀SK(n) (16)
> 2↑2↑2↑8193
S(SS(SS))(SSK)(SS(SK)(S(KS)K))
Ξ₀SK(n) (17)
> 2↑↑2↑↑2↑258
SSS(SKS)(SSK)(SS(SK)(S(KS)K))
Ξ₀SK(n) (18)
> 2↑↑33
S(SKS)(SSK)(SSK(SS(SK)(S(KS)K)))
Ξ₀SK(n) (22)
> 2↑↑↑19
S(S(S(S(SK))))(SKS)(S(SSK)(K(SS(SK)(S(KS)K)))
Ξ₀SK(n) (23)
> 2↑↑↑↑2↑↑2↑↑258
S(SS(SSS)(SKS))(SKS)(SSK)(SS(SK)(S(KS)K))
Ξ₀SK(n) (24)
> 2↑↑↑↑2↑↑2↑↑258
S(SS(SSS)(SKS))(SKS)(SSK)(SS(SK)(S(KS)K))S
Ξ₀SK(n) (25)
> 3↑↑↑↑3↑↑3↑↑3↑↑3↑↑3↑3↑3↑82 > 3↑↑↑↑3↑↑↑6
S(SS(SSS)(SKS))(SKS)(SSK)(SS(SS(SK))(S(KS)K))
Ξ₀SK(n) (26)
> fω+1 (2↑↑7/2-1) > Graham's number
S(S(S(S(SKS))))(SKS)(S(K(S(SS(K(K(SS(SK)(S(KS)K)))))))K)
Busy Beaver for BCKW calculus
Ξ₀BCKW (n)
Champion
Ξ₀BCKW (1)
1
B
Ξ₀BCKW (2)
2
BB
Ξ₀BCKW (3)
3
BBB
Ξ₀BCKW (4)
≥ 11
WW(WB)
Ξ₀BCKW (5)
≥ 47
W(WW)(WB)
Ξ₀BCKW (6)
≥ 2↑256*6-1
WW(WC(WB))
Ξ₀BCKW (7)
> 2↑↑↑17
WW(C(WC)(WB))
Ξ₀BCKW (8)
> 2↑↑↑2↑↑↑17
W(WW)(C(WC)(WB))
Ξ₀BCKW (9)
> 2↑↑↑2↑↑↑2↑↑↑17
W(W(WW))(C(WC)(WB))
Ξ₀BCKW (10)
> fω+1 (2↑↑6/2-1)
WW(C(WB)(C(CC(WB))))
BB_brainf(n)
Champion
BB_brainf(1)
1
+
BB_brainf(2)
2
++
BB_brainf(3)
3
+++
BB_brainf(4)
4
++++
BB_brainf(5)
≥ 5
+++++
BB_brainf(6)
≥ 6
++++++
BB_brainf(7)
≥ 7
+++++++
BB_brainf(8)
≥ 8
++++++++
BB_brainf(9)
≥ 9
+++++++++
BB_brainf(10)
≥ 10
++++++++++
BB_brainf(11)
≥ 11
+++++++++++
BB_brainf(12)
≥ 12
++++++++++++
BB_brainf(13)
≥ 16
++++[->++++<]
BB_brainf(14)
≥ 20
+++++[->++++<]
BB_brainf(15)
≥ 25
+++++[->+++++<]
BB_brainf(16)
≥ 30
++++++[->+++++<]
BB_brainf(17)
≥ 36
++++++[->++++++<]
BB_brainf(18)
≥ 42
+++++++[->++++++<]
BB_brainf(19)
≥ 49
+++++++[->+++++++<]
BB_brainf(20)
≥ 56
++++++++[->+++++++<]
BB_brainf(21)
≥ 64
++++++++[->++++++++<]
BB_brainf(22)
≥ 72
+++++++++[->++++++++<]
BB_brainf(23)
≥ 81
+++++++++[->+++++++++<]
BB_brainf(24)
≥ 90
+++++++++[->++++++++++<]
BB_brainf(25)
≥ 340
++++[>+[->++<]>[-<++>]<<]
BB_brainf(26)
≥ 1364
+++++[>+[->++<]>[-<++>]<<]
BB_boolf(n)
Champion
BB_boolf(1)
1
*
BB_boolf(2)
1
*>
BB_boolf(3)
2
*>*
BB_boolf(4)
2
*>*>
BB_boolf(5)
3
*>*>*
BB_boolf(6)
3
*>*>*>
BB_boolf(7)
4
*>*>*>*
Macros for compression:
Macro
Definition
Size
Function
Constant Addition
A+=n;
increment A by n
n
A++; repeated n times
Transfer
A>>B*n;
increment B by A*n then set A to 0
n+2
while A {A--; (B++; repeated n times)}
BBCS(n)
Champion
BBCS(1)
1
A++;
BBCS(2)
2
A++; A++;
BBCS(3)
3
A++; A++; A++;
BBCS(4)
4
A++; A++; A++; A++;
BBCS(5)
5
A++; A++; A++; A++; A++;
BBCS(6)
6
A++; A++; A++; A++; A++; A++;
BBCS(7)
7
A++; A++; A++; A++; A++; A++; A++;
BBCS(8)
9
A++; A++; A++; while A {A--; B++; B++; B++;}
BBCS(9)
12
A++; A++; A++; A++; while A {A--; B++; B++; B++;}
BBCS(10)
16
A++; A++; A++; A++; while A {A--; B++; B++; B++; B++;}
BBCS(11)
≥ 20
A++; A++; A++; A++; A++; while A {A--; B++; B++; B++; B++;}
BBCS(12)
≥ 25
A++; A++; A++; A++; A++; while A {A--; B++; B++; B++; B++; B++;}
BBCS(13)
≥ 42
A++; while A {A++; while B {A--; B--; C++; C++;} C>>B*2; C++;}
BBCS(14)
≥ 129
A++; while A {A++; while B {A--; B--; C++; C++;} C>>B*3; C++;}
BBCS(15)
≥ 340
A++; A++; A++; A++; while A {A--; B++; while B {B--; C++; C++;} while C {C--; B++; B++;}}
BBCS(16)
≥ 1,554
A++; A++; A++; A++; while A {A--; B++; while B {B--; C++; C++; C++;} while C {C--; B++; B++;}}
BBCS(17)
≥ 9,330
A++; A++; A++; A++; A++; while A {A--; B++; while B {B--; C++; C++; C++;} while C {C--; B++; B++;}}
BBCS(18)
≥ 66,429
A++; A++; A++; A++; A++; while A {A--; B++; while B {B--; C++; C++; C++;} while C {C--; B++; B++; B++;}}
BBCS(19)
≥ (3^122 - 3)/2
A++; while A {A++; while B {A--; B--; C++;} while C {B++; C--; B>>D*3; D>>B;} C++;}
BBCS(20)
≥ 2^65536 - 2
A+=4; while A {A--; B++; while B {B--; C++; C>>D*2; D>>C;} C>>B;}
BBCS(21)
≥ 2^2^65536 - 2
A+=5; while A {A--; B++; while B {B--; C++; C>>D*2; D>>C;} C>>B;}
BBCS(22)
≥ 2^^7 - 2
A+=6; while A {A--; B++; while B {B--; C++; C>>D*2; D>>C;} C>>B;}
BBCS(23)
≥ 2^^8 - 2
A+=7; while A {A--; B++; while B {B--; C++; C>>D*2; D>>C;} C>>B;}
BBCS(24)
≥ 2^^65536 - 2
A++; while A {A++; while B {A--; B--; C++;} while C {B++; C--; while B {B--; D++; D>>E*2; E>>D;} D>>B;} C++;}
BBCS(25)
> 2^^2^^6
A++; while A {A++; while B {A--; B--; C+=2;} while C {B++; C--; while B {B--; D++; D>>E*2; E>>D;} D>>B;} C++;}
BBCS(26)
≥ 2^^2^^65536 - 2
A++; A++; A++; A++; while A {A--; B++; while B {B--; C++; while C {C--; D++; while D {D--; E++; E++;} while E {E--; D++;}} while D {D--; C++;}} while C {C--; B++;}}
BBCS(64)
> Graham's number
too large to show
BBCS(85)
> q(5)
too large to show, see Discord
Fractran (BBf (n))
n
BBf(n)
Example Champion
Vector Representation
BBf(2)
1
[1/2]
[ − 1 ]
BBf(3)
1
[3/2]
[ − 1 1 ]
BBf(4)
1
[9/2]
[ − 1 2 ]
BBf(5)
2
[3/2, 1/3]
[ − 1 1 0 − 1 ]
BBf(6)
3
[9/2, 1/3]
[ − 1 2 0 − 1 ]
BBf(7)
4
[27/2, 1/3]
[ − 1 3 0 − 1 ]
BBf(8)
5
[81/2, 1/3]
[ − 1 4 0 − 1 ]
BBf(9)
6
[243/2, 1/3]
[ − 1 5 0 − 1 ]
BBf(10)
7
[729/2, 1/3]
[ − 1 6 0 − 1 ]
BBf(11)
10
[27/2, 25/3, 1/5]
[ − 1 3 0 0 − 1 2 0 0 − 1 ]
BBf(12)
13
[81/2, 25/3, 1/5]
[ − 1 4 0 0 − 1 2 0 0 − 1 ]
BBf(13)
17
[81/2, 125/3, 1/5]
[ − 1 4 0 0 − 1 3 0 0 − 1 ]
BBf(14)
21
[243/2, 125/3, 1/5]
[ − 1 5 0 0 − 1 3 0 0 − 1 ]
BBf(15)
28
[1/45, 4/5, 3/2, 25/3]
[ 0 − 2 − 1 2 0 − 1 − 1 1 0 0 − 1 2 ]
BBf(16)
53
[1/45, 4/5, 3/2, 125/3]
[ 0 − 2 − 1 2 0 − 1 − 1 1 0 0 − 1 3 ]
BBf(17)
107
[5/6, 49/2, 3/5, 40/7]
[ − 1 − 1 1 0 − 1 0 0 2 0 1 − 1 0 3 0 1 − 1 ]
BBf(18)
211
[5/6, 49/2, 3/5, 80/7]
[ − 1 − 1 1 0 − 1 0 0 2 0 1 − 1 0 4 0 1 − 1 ]
BBf(19)
370
[5/6, 49/2, 3/5, 160/7]
[ − 1 − 1 1 0 − 1 0 0 2 0 1 − 1 0 5 0 1 − 1 ]
BBf(20)
746
[7/15, 22/3, 6/77, 5/2, 9/5]
[ − 1 − 1 + 1 + 1 − 1 + 1 + 1 + 1 − 1 − 1 − 1 + 1 + 2 − 1 ]
BBf(21)
≥ 31,957,632
[7/15, 4/3, 27/14, 5/2, 9/5]
[ 0 − 1 − 1 1 2 − 1 0 0 − 1 3 0 − 1 − 1 0 1 0 0 2 − 1 0 ]
BBf(22)
> 1 . 1 4 6 × 1 0 6 2
[1/12, 9/10, 14/3, 11/2, 5/7, 3/11]
[ − 2 − 1 0 0 0 − 1 2 − 1 0 0 1 − 1 0 1 0 − 1 0 0 0 1 0 0 1 − 1 0 0 1 0 0 − 1 ]
BBf(23)
> 4 . 3 9 3 × 1 0 1 2 4
[10/3, 9/14, 5/4, 121/2, 7/5, 3/11]
[ 1 − 1 1 0 0 − 1 2 0 − 1 0 − 2 0 1 0 0 − 1 0 0 0 2 0 0 − 1 1 0 0 1 0 0 − 1 ]
BBf(24)
> 9 . 2 6 3 × 1 0 9 5 9 5
[18/35, 1/10, 11/5, 75/2, 49/3, 5/11]
[ 1 2 − 1 − 1 0 − 1 0 − 1 0 0 0 0 − 1 0 1 − 1 1 2 0 0 0 − 1 0 2 0 0 0 1 0 − 1 ]
Runtime
Champions
CTBB(2)
5[ 9]
CTBB(3)
> 38[ 10]
CTBB(4)
≥ 672[ 11]
CTBB(5)
≥ 2^2^2^2^182[ 12]
CTBB(6)
> 2↑↑↑131[ 13]
CTBB(7)
> 4↑↑↑↑(4↑↑↑3)[ 14] [ 15]
n
Runtime
Champions
1
1
0
2
5
10
3
9
101
4
13
1001
5
15
10101
6
334
010111
7
404
1010111
8
670
11100101
9
12584
001101110
10
2180995
0100011110
Minsky Machines (MBB(n) )
Domain
Halting Time
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*
MBB(7)
≥ 231
0+B_0+C_0+D_1-GE_1+F_0-EC_1-A*
MBB(8)
≥ 3394
0+B_0+C_1-GD_1+E_0-DF_2-HG_2+A_2-D*
MBB(9)
≥ 9870
0+B_0+C_0+D_1-IE_1+F_0-GI_0-HC_0-E*_0+A
Pebble Automation (peBBle(n) )
n
peBBle(n)
Champion
peBBle(1)
0
00
peBBle(2)
1
00_01
peBBle(3)
3
00_01_20
peBBle(4)
6
00_01_20_03
peBBle(5)
≥ 11[ 16]
00_11_03_21_04
peBBle(6)
≥ 17[ 17]
00_11_03_21_40_15
peBBle(7)
≥ 28[ 17]
00_11_03_21_10_33_61
peBBle(8)
≥ 63[ 18]
00_11_03_21_50_30_24_70
peBBle(9)
≥ 63577[ 19]
00_02_01_40_14_12_00_52_81
n
BBWT (n)
Champion
Image
BBWT (1)
1
[1,0,0,0]
BBWT (2)
2[ 20]
[1,0,2,0] [2,0,3,0]
BBWT (3)
3[ 20]
[1,0,2,0] [2,0,3,0] [3,0,4,0]
BBWT (4)
4[ 21]
[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0]
BBWT (5)
≥ 6[ 22]
[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,6,1,5] [4,5,2,6]
BBWT (6)
≥ 8
[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0] [5,7,1,6] [5,6,2,7]
BBWT (7)
≥ 11
BBWT (8)
≥ 14
BBWT (9)
≥ 17
BBWT (10)
≥ 212
Turmites
Terminating Turmites (TT (n,k), 1D Turmites)
Where n is the amount of states and k is the amount of symbols.
Maximum steps for TT(n,k)
Domain
Runtime
Champions
TT(2)
≥ 13
1TB---_1PA0PB
TT(3)
≥ 82
1PB0PA_1TA0PC_1PA---
TT(4)
≥ 48,186
1TB1PA_1PC0PA_1TA0PD_---1TA
TT(2,3)
≥ 223
1TB0PA2PA_2PA---1PA
TT(3,3)
> 2 . 2 7 × 1 0 2 4 8 [ 23]
1PB0TC1PA_2PC1PZ2PA_2TC0PA2PC
TT(2,4)
> 3.467*1015
1TA2PB3TB---_3TA1PB1TA1PA
Maximum score for TT(n,k)
Domain
Score
Champion
TT(3,3)
≥ 32,778[ 24]
1PB2PA0PC_2TB1PC2PB_2PB1PZ0PA
There are currently no known/available Champions for this function.
doodle(1,n) = 1 and doodle(2,n) = n. Also note that doodle(c) = doodle(c,2).
2 Symbols:
Runtime
Champions
doodle(3,2)
≥ 487
Bug Function
Bug(2,2) = 2
####
#S-#
#.F#
####
Bug(3,3) = 8
#####
#S..#
#.#.#
#.#F#
#####
Bug(4,4) = 20
######
#S...#
#..###
#....#
#..#F#
######
Bug(5,5) = 42
#######
#S...##
#.....#
#.....#
#.#.###
#.#..F#
#######
Bug(6,6) = 96
########
#S.....#
#.###.##
#.#...##
#.#....#
#..#.###
#..#..F#
########
Bug(7,7) = 218
#########
#S.###..#
#......##
#.#.##..#
#..#...##
#..#....#
#...#.###
#..#-..F#
#########
Bug(8,8) = 506
##########
#S.#.....#
#.#..##.##
#.#.##..##
#....##..#
#.#.#...##
#..##....#
#....#.###
#....#..F#
##########
References