Line 1:
Line 1:
A collection of Busy Beaver [[Champions]] including Champions for BB-Adjacent [[:Category:Functions|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).
A collection of Busy Beaver [[Champions]] including Champions for BB-Adjacent [[:Category:Functions|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
Note: Currently very outdated
= '''State-and-Symbol-Limited Busy Beaver functions''' =
= '''State-and-Symbol-Limited Busy Beaver functions''' =
Busy Beaver functions where the programs size is limited by the amount of states and symbols.
Busy Beaver functions where the programs size is limited by the amount of states and symbols.
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: Currently very outdated
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