Behavior of busy beavers

Contents

Turing machines with 5 states and 2 symbols

1990
1990 		  Marxen and Buntrock  
Marxen and Buntrock 		s = 47,176,870, sigma = 4098
s = 23,554,764, sigma = 4097
Turing machines with 6 states and 2 symbols
May 2022
June 2010
May 2010
December 2007
November 2007
March 2001
October 2000
October 2000
September 1997 		Kropitz
Kropitz
Kropitz
T. and S. Ligocki
T. and S. Ligocki
  Marxen and Buntrock  
Marxen and Buntrock
Marxen and Buntrock
Marxen and Buntrock
 s > sigma > 10^^15
s > 7.4 × 10^36534, sigma > 3.5 × 10^18267
s > 3.8 × 10^21132, sigma > 3.1 × 10^10566
s > 2.5 × 10^2879, sigma > 4.6 × 10^1439
s > 8.9 × 10^1762, sigma > 2.5 × 10^881
s > 3.0 × 10^1730, sigma > 1.2 × 10^865
s > 6.1 × 10^925, sigma > 6.4 × 10^462
s > 6.1 × 10^119, sigma > 1.4 × 10^60
s > 8.6 × 10^15, sigma = 95,524,079
Turing machines with 3 states and 3 symbols
November 2007
August 2006
April 2006
September 2005
August 2005
July 2005
July 2005
December 2004 		T. and S. Ligocki
T. and S. Ligocki
  Lafitte and Papazian  
Lafitte and Papazian
Lafitte and Papazian
Souris
Souris
Brady 		s = 119,112,334,170,342,540, sigma = 374,676,383
s = 4,345,166,620,336,565, sigma = 95,524,079
s = 4,144,465,135,614, sigma = 2,950,149
s = 987,522,842,126, sigma = 1,525,688
s = 4,939,345,068, sigma = 107,900
s = 544,884,219, sigma = 32,213
s = 310,341,163, sigma = 36,089
s = 92,649,163, sigma = 13,949
Turing machines with 2 states and 4 symbols
February 2005
1988 		  T. and S. Ligocki  
Brady 		s = 3,932,964, sigma = 2,050
s = 7,195, sigma = 90
Turing machines with 2 states and 5 symbols
November 2007
August 2006
June 2006
May 2006
December 2005
October 2005 		T. and S. Ligocki
T. and S. Ligocki
  Lafitte and Papazian  
Lafitte and Papazian
Lafitte and Papazian
Lafitte and Papazian 		s > 1.9 × 10^704, sigma > 1.7 × 10^352
s = 7,069,449,877,176,007,352,687, sigma = 172,312,766,455
s = 14,103,258,269,249, sigma = 4,848,239
s = 3,793,261,759,791, sigma = 2,576,467
s = 924,180,005,181, sigma = 1,137,477
s = 912,594,733,606, sigma = 1,957,771

Collatz-like problems

Non-Collatz-like behaviors

Similar behaviors

Created by Pascal Michel in 2004
Last update: April 2024

Introduction

How do good machines behave?
We give below the tricks that allow them to reach high scores.

A configuration of the Turing machine M is a description of the tape.
The position of the tape head and the state are indicated by writing together between parentheses the state and the symbol currently read by the tape head.
For example, the initial configuration on a blank tape is:

. . . 0(A0)0 . . .
You can see the introduction to Turing machines for more informations.
We denote by ak the string a . . . a, k times.
We write C --( t )--> D if the next move function leads from configuration C to configuration D in t computation steps.

Turing machines with 5 states and 2 symbols

Marxen and Buntrock's champion

See also the simulation by Heiner Marxen. This machine was analyzed by Buro (1991) (p.64-67), and independently by Michel (1993).

This machine is the record holder in the Busy Beaver Competition for machines with 5 states and 2 symbols, since 1990.

Marxen and Buntrock (1990)
s(M) = 47,176,870 =? S(5,2)
sigma(M) = 4098 =? Sigma(5,2)
M=
0 1
A 1RB 1LC
B 1RC 1RB
C 1RD 0LE
D 1LA 1LD
E 1RH 0LA

Let C(n) = . . . 0(A0)1n0 . . .
Then we have:

C(3k) --( 5k2 + 19k + 15 )--> C(5k + 6)
C(3k + 1) --( 5k2 + 25k + 27 )--> C(5k + 9)
C(3k + 2) --( 6k + 12 )--> . . . 01(H0)1(001)k+110 . . .

So we have:

. . . 0(A0)0 . . . = C( 0 ) --( 15 )-->
C( 6 ) --( 73 )-->
C( 16 ) --( 277 )-->
C( 34 ) --( 907 )-->
C( 64 ) --( 2,757 )-->
C( 114 ) --( 7,957 )-->
C( 196 ) --( 22,777 )-->
C( 334 ) --( 64,407 )-->
C( 564 ) --( 180,307 )-->
C( 946 ) --( 504,027 )-->
C( 1,584 ) --( 1,403,967 )-->
C( 2,646 ) --( 3,906,393 )-->
C( 4,416 ) --( 10,861,903 )-->
C( 7,366 ) --( 30,196,527 )-->
C( 12,284 ) --( 24,576 )-->
. . . 01(H0)1(001)409510 . . .

Marxen and Buntrock's runner-up

See also the simulation by Heiner Marxen.
Marxen and Buntrock (1990)
s(M) = 23,554,764
sigma(M) = 4097
M=
0 1
A 1RB 0LD
B 1LC 1RD
C 1LA 1LC
D 1RH 1RE
E 1RA 0RB

Let C(n) = . . . 0(A0)1n0 . . .
Then we have:

C(3k) --( 10k2 + 10k + 4 )--> C(5k + 3)
C(3k + 1) --( 3k + 3 )--> . . . 01(110)k11(H0)0 . . .
C(3k + 2) --( 10k2 + 26k + 12 )--> C(5k + 7)

So we have:

. . . 0(A0)0 . . . = C( 0 ) --( 4 )-->
C( 3 ) --( 24 )-->
C( 8 ) --( 104 )-->
C( 17 ) --( 392 )-->
C( 32 ) --( 1,272 )-->
C( 57 ) --( 3,804 )-->
C( 98 ) --( 11,084 )-->
C( 167 ) --( 31,692 )-->
C( 282 ) --( 89,304 )-->
C( 473 ) --( 250,584 )-->
C( 792 ) --( 699,604 )-->
C( 1,323 ) --( 1,949,224 )-->
C( 2,208 ) --( 5,424,324 )-->
C( 3,683 ) --( 15,087,204 )-->
C( 6,142 ) --( 6,144 )-->
. . . 01(110)204711(H0)0 . . .

Turing machines with 6 states and 2 symbols

Kropitz's machine found in May 2022

See also the analysis by Shawn Ligocki.

This machine is the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, since May 2022.

Kropitz (2022)
s(M) and S(6,2) > 10^^15
sigma(M) and Sigma(6,2) > 10^^15
M=
0 1
A 1RB 0LD
B 1RC 0RF
C 1LC 1LA
D 0LE 1RH
E 1LF 0RB
F 0RC 0RE

Analysis from Pavel Kropitz, Shawn Ligocki and Pascal Michel

Let C(n) = . . . 010n1105(C0)0 . . .
Then we have:

. . . 0(A0)0 . . . --( 45 )--> C(5)
C(4k) --( (3 × 9k+3 - 80 × 3k+3 + 712 k + 261)/32 )--> . . . 01(H0)1n-10 . . .
C(4k + 1) --( (3 × 9k+3 - 64 × 3k+3 + 712 k + 981)/32 )--> C((3k+3 - 11)/2)
C(4k + 2) --( (3 × 9k+3 - 64 × 3k+3 + 712 k + 1045)/32 )--> C((3k+3 - 11)/2)
C(4k + 3) --( (3 × 9k+3 - 64 × 3k+3 + 712 k + 1749)/32 )--> C((3k+3 + 1)/2)
with n = (3k+3 -11)/2

So we have (the final configuration is reached in 17 transitions):

. . . 0(A0)0 . . . --( 45 )-->
C( 5 ) --( 506 )-->
C( 35 ) --( 2,941,620,277 )-->
C( 88574 ) --( )-->
. . .
. . . 01(H0)1n0 . . .

with n > 10^^15.

Kropitz's machine found in June 2010

See also the simulation by Heiner Marxen. See detailed analysis in Michel (2015), Section 6.

This machine was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, from June 2010 to May 2022.

Kropitz (2010)
s(M) > 7.4 × 1036534
sigma(M) > 3.5 × 1018267
M=
0 1
A 1RB 1LE
B 1RC 1RF
C 1LD 0RB
D 1RE 0LC
E 1LA 0RD
F 1RH 1RC

Let C(n) = . . . 0(A0)1n 0 . . .
Then we have:

. . . 0(A0)0 . . . --( 29 )--> C(9)
C(3k + 1) --( 3k + 3 )--> . . . 0111(011)k(H0)0 . . .
C(9k + 9) --( (125 × 16k+2 + 325 × 4k+2 + 228 k - 2289)/27 )--> C((50 × 4k+1 - 11)/3)
C(9k + 12) --( (125 × 16k+2 + 325 × 4k+2 + 228 k - 912)/27 )--> C((50 × 4k+1 + 1)/3)

So we have:

. . . 0(A0)0 . . . --( 29 )-->
C( 9 ) --( 1293 )-->
C( 63 ) --( 19,884,896,677 )-->
C( 273063 ) --( T1 )-->
C( (50 × 4^30340 + 1)/3 ) --( T2 )-->
. . . 0111(011)K(H0)0 . . .

with T1 = (125 × 16^30341 + 325 × 4^30341 + 6,916,380)/27,
T2 = (50 × 4^30340 + 7)/3,
K = (50 × 4^30340 - 2)/9.

So the total time is: s(M) = (125 × 16^30341 + 1750 × 4^30340 + 15)/27 + 19,885,154,163,
and the final number of 1 is: sigma(M) = (25 × 4^30341 + 23)/9.

Some configurations take a long time to halt.
For example, C(2) --( t )--> END with t > 10^(10^(10^(10^18705352))).
A proof of this fact is given by "Cloudy176".
This property was used by "Wythagoras", in March 2014, to define a (7,2)-TM that extends the present (6,2)-TM and enters in two steps this configuration C(2).

Kropitz's machine found in May 2010

See also the simulation by Heiner Marxen. See detailed analysis in Michel (2015), Section 7.

This machine was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, from May 2010 to June 2010.

Kropitz (2010)
s(M) > 3.8 × 1021132
sigma(M) > 3.1 × 1010566
M=
0 1
A 1RB 0LD
B 1RC 0RF
C 1LC 1LA
D 0LE 1RH
E 1LA 0RB
F 0RC 0RE

Analysis adapted from Shawn Ligocki:

Let C(n, k) = . . . 010n1(C1)13k0 . . .
Then we have:

. . . 0(A0)0 . . . --( 47 )--> C(5, 2)
C(0, k) --( 3 )--> . . . 01(H0)13k+10 . . .
C(1, k) --( 3k + 37 )--> C(3k + 2, 2)
C(2, k) --( 12k + 44 )--> C(4, k + 2)
C(3, k) --( 3k + 57 )--> C(3k + 8, 2)
C(n + 4, k) --( 27k2 + 105k + 112 )--> C(n, 3k + 5)

So we have (the final configuration is reached in 22158 transitions):

. . . 0(A0)0 . . . --( 47 )-->
C( 5, 2 ) --( 430 )-->
C( 1, 11 ) --( 70 )-->
C( 35, 2 ) --( 430 )-->
C( 31, 11 ) --( 4,534 )-->
C( 27, 38 ) --( 43,090 )-->
C( 23, 119 ) --( 394,954 )-->
C( 19, 362 ) --( 3,576,310 )-->
C( 15, 1091 ) --( 32,252,254 )-->
C( 11, 3278 ) --( 290,466,970 )-->
C( 7, 9839 ) --( 2,614,793,074 )-->
C( 3, 29522 ) --( 88,623 )-->
C( 88574, 2 ) --( 430 )-->
C( 88570, 11 ) --( 4,534 )-->
C( 88566, 38 ) --( 43,090 )-->
. . .

Note that C(4n + r, 2) --( tn )--> C(r, un),
with un = (3n+2 - 5)/2,
and tn = (3 × 9n+3 - 80 × 3n+3 + 584 n - 27)/32.

Some configurations take a long time to halt.
For example, C(1, 9) --( t )--> END with t > 10^(10^(10^(10^(10^3520)))).

T. and S. Ligocki's machine found in December 2007

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, from December 2007 to May 2010.

Terry and Shawn Ligocki (2007)
s(M) > 2.5 × 102879
sigma(M) > 4.6 × 101439
M=
0 1
A 1RB 0LE
B 1LC 0RA
C 1LD 0RC
D 1LE 0LF
E 1LA 1LC
F 1LE 1RH

Let C(n, p) = . . . 0(A0)(10)nR(bin(p))0 . . ., where R(bin(p)) is the number p written in binary in reverse order, so that C(n, 4m + 1) = C(n + 1, m).
The number of transitions between configurations C(n, p) is infinite, but only 18 transitions are used in the computation on a blank tape:

C(k, 4m + 3) --( 4k + 6 )--> C(k + 2, m)
C(2k + 1, 4m) --( 6k2 + 52k + 98 )--> C(3k + 8, m)
C(4k, 4m) --( 24k2 + 36k + 13 )--> C(6k + 2, 2m + 1)
C(4k + 2, 4m) --( 24k2 + 60k + 27 )--> C(6k + 2, 128m + 86)
C(k, 8m + 2) --( 4k + 14 )--> C(k + 2, 2m + 1)
C(2k + 1, 32m + 22) --( 6k2 + 64k + 160 )--> C(3k + 10, 2m + 1)
C(4k, 32m + 22) --( 24k2 + 36k + 29 )--> C(6k + 4, m)
C(4k + 2, 32m + 22) --( 24k2 + 60k + 43 )--> C(6k + 2, 1024m + 342)
C(k, 64m + 46) --( 4k + 30 )--> C(k + 4, m)
C(k + 1, 128m + 6) --( 8k + 66 )--> C(k + 6, 2m + 1)
C(2k, 256m + 14) --( 6k2 + 64k + 172 )--> C(3k + 11, m)
C(4k + 1, 256m + 14) --( 24k2 + 84k + 89 )--> C(6k + 8, 2m + 1)
C(4k + 3, 256m + 14) --( 24k2 + 108k + 127 )--> C(6k + 8, 128m + 86)
C(4k, 512m + 30) --( 24k2 + 156k + 173 )--> C(6k + 11, m)
C(4k + 2, 512m + 30) --( 24k2 + 60k + 57 )--> C(6k + 2, 16384m + 11134)
C(4k + 2, 131072m + 11134) --( 24k2 + 60k + 89 )--> C(6k + 2, 4194304m + 2848638)
C(4k, 131072m + 96126) --( 24k2 + 36k + 109 )--> C(6k + 10, m)
C(k + 1, 512m + 94) --( 2k + 61 )--> . . . 0(10)k1(H0)1110110101R(bin(m))0 . . .

So we have (the final configuration is reached in 11026 transitions):

. . . 0(A0)0 . . . = C( 0, 0 ) --( 13 )-->
C( 3, 0 ) --( 156 )-->
C( 11, 0 ) --( 508 )-->
C( 23, 0 ) --( 1396 )-->
C( 41, 0 ) --( 3538 )-->
C( 68, 0 ) --( 7,561 )-->
C( 105, 0 ) --( 19,026 )-->
C( 164, 0 ) --( 41,833 )-->
C( 249, 0 ) --( 98,802 )-->
C( 380, 0 ) --( 220,033 )-->
C( 573, 0 ) --( 505,746 )-->
C( 866, 0 ) --( 1,132,731 )-->
C( 1298, 86 ) --( 2,538,907 )-->
C( 1946, 2390 ) --( 5,697,907 )-->
C( 2918, 76118 ) --( 12,798,367 )-->
C( 4376, 2435414 ) --( 1,034,066,333 )-->
C( 6568, 76106 ) --( 26,286 )-->
C( 6570, 19027 ) --( 26,286 )-->
C( 6572, 4756 ) --( 64,845,937 )-->
C( 9860, 2379 ) --( 39,446 )-->
C( 9862, 594 ) --( 39,462 )-->
C( 9867, 2 ) --( 39,482 )-->
. . .

T. and S. Ligocki's machine found in November 2007

See also the simulation by Heiner Marxen. See detailed analysis in Michel (2015), Section 8.

This machine was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, from November to December 2007.

Terry and Shawn Ligocki (2007)
s(M) > 8.9 × 101762
sigma(M) > 2.5 × 10881
M=
0 1
A 1RB 0RF
B 0LB 1LC
C 1LD 0RC
D 1LE 1RH
E 1LF 0LD
F 1RA 0LE

Let C(n, p) = . . . 0(F0)(10)nR(bin(p))0 . . ., where R(bin(p)) is the number p written in binary in reverse order, so that C(n, 4m + 1) = C(n + 1, m).
The number of transitions between configurations C(n, p) is infinite, but only 12 transitions are used in the computation on a blank tape:

. . . 0(A0)0 . . . --( 6 )--> C(0, 15)
C(k, 4m + 3) --( 4k + 6 )--> C(k + 2, m)
C(2k, 4m) --( 30k2 + 20k + 15 )--> C(5k + 2, 2m + 1)
C(2k + 1, 4m) --( 30k2 + 40k + 25 )--> C(5k + 2, 32m + 20)
C(k, 8m + 2) --( 8k + 20 )--> C(k + 3, 2m + 1)
C(2k, 16m + 6) --( 30k2 + 40k + 23 )--> C(5k + 2, 32m + 20)
C(2k + 1, 16m + 6) --( 30k2 + 80k + 63 )--> C(5k + 7, 2m + 1)
C(k, 32m + 14) --( 4k + 18 )--> C(k + 3, 2m + 1)
C(2k, 128m + 94) --( 30k2 + 40k + 39 )--> C(5k + 2, 256m + 84)
C(2k + 1, 128m + 94) --( 30k2 + 80k + 79 )--> C(5k + 9, m)
C(k, 256m + 190) --( 4k + 34 )--> C(k + 5, m)
C(k, 512m + 30) --( 2k + 43 )--> . . . 0(10)k1(H0)10100101R(bin(m))0 . . .

So we have (the final configuration is reached in 3346 transitions):

. . . 0(A0)0 . . . --( 6 )-->
C( 0, 15 ) --( 6 )-->
C( 2, 3 ) --( 14 )-->
C( 4, 0 ) --( 175 )-->
C( 13, 0 ) --( 1,345 )-->
C( 32, 20 ) --( 8,015 )-->
C( 82, 11 ) --( 334 )-->
C( 84, 2 ) --( 692 )-->
C( 88, 0 ) --( 58,975 )-->
C( 223, 0 ) --( 374,095 )-->
C( 557, 20 ) --( 2,329,665 )-->
C( 1392, 180 ) --( 14,546,415 )-->
C( 3482, 91 ) --( 13,934 )-->
C( 3484, 22 ) --( 91,106,623 )-->
C( 8712, 52 ) --( 569,329,215 )-->
C( 21782, 27 ) --( 87,134 )-->
C( 21784, 6 ) --( 3,559,505,623 )-->
C( 54462, 20 ) --( 22,246,365,465 )-->
C( 136157, 11 ) --( 544,634 )-->
C( 136159, 2 ) --( 1,089,292 )-->
C( 136163, 0 ) --( 139,053,400,095 )-->
C( 340407, 20 ) --( 869,078,644,415 )-->
. . .

Marxen and Buntrock's machine found in March 2001

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, from March 2001 to November 2007.

Marxen and Buntrock (2001)
s(M) > 3.0 × 101730
sigma(M) > 1.2 × 10865
M=
0 1
A 1RB 0LF
B 0RC 0RD
C 1LD 1RE
D 0LE 0LD
E 0RA 1RC
F 1LA 1RH

Let C(n, p) = . . . 0(A0)(01)nR(bin(p))0 . . ., where R(bin(p)) is the number p written in binary in reverse order, so that C(n, 4m + 2) = C(n + 1, m).
The number of transitions between configurations C(n, p) is infinite, but only 20 transitions are used in the computation on a blank tape:

C(2k, 4m) --( 9k2 + 25k + 9 )--> C(3k + 1, 2m + 1)
C(2k, 16m + 1) --( 9k2 + 25k + 17 )--> C(3k + 2, 2m + 1)
C(2k, 4m + 3) --( 9k2 + 25k + 9 )--> C(3k + 1, 2m)
C(2k, 64m + 53) --( 9k2 + 25k + 25 )--> C(3k + 3, 2m)
C(2k, 256m + 9) --( 9k2 + 25k + 29 )--> C(3k + 4, 2m + 1)
C(2k, 1024m + 57) --( 9k2 + 25k + 33 )--> C(3k + 2, 128m + 104)
C(2k, 1024m + 85) --( 9k2 + 25k + 41 )--> C(3k + 5, 2m + 1)
C(2k + 1, 16m) --( 9k2 + 25k + 21 )--> C(3k + 3, 2m + 1)
C(2k + 1, 4m + 1) --( 9k2 + 25k + 13 )--> C(3k + 1, 8m + 4)
C(2k + 1, 64m + 4) --( 9k2 + 25k + 29 )--> C(3k + 4, 2m + 1)
C(2k + 1, 64m + 3) --( 9k2 + 25k + 25 )--> C(3k + 1, 128m + 104)
C(2k + 1, 1024m + 104) --( 9k2 + 43k + 75 )--> C(3k + 7, 2m + 1)
C(2k + 1, 16m + 12) --( 9k2 + 25k + 21 )--> C(3k + 3, 2m)
C(2k + 1, 16m + 7) --( 9k2 + 25k + 17 )--> C(3k + 1, 32m + 16)
C(2k + 1, 256m + 15) --( 9k2 + 25k + 29 )--> C(3k + 1, 512m + 416)
C(2k + 1, 64m + 52) --( 9k2 + 25k + 29 )--> C(3k + 4, 2m)
C(2k + 1, 256m + 20) --( 9k2 + 25k + 37 )--> C(3k + 5, 2m + 1)
C(2k + 1, 4096m + 420) --( 9k2 + 43k + 89 )--> C(3k + 8, 2m + 1)
C(2k + 1, 256m + 211) --( 9k2 + 25k + 33 )--> C(3k + 1, 512m + 168)
C(2k + 1, 16m + 11) --( 9k2 + 13k + 10 )--> . . . 0(10)3k+111(H0)10R(bin(m))0 . . .

So we have (the final configuration is reached in 4911 transitions):

. . . 0(A0)0 . . . = C( 0, 0 ) --( 9 )-->
C( 1, 1 ) --( 13 )-->
C( 1, 4 ) --( 29 )-->
C( 4, 1 ) --( 103 )-->
C( 8, 1 ) --( 261 )-->
C( 14, 1 ) --( 633 )-->
C( 23, 1 ) --( 1,377 )-->
C( 34, 4 ) --( 3,035 )-->
C( 52, 3 ) --( 6,743 )-->
C( 79, 0 ) --( 14,685 )-->
C( 120, 1 ) --( 33,917 )-->
C( 182, 1 ) --( 76,821 )-->
C( 275, 1 ) --( 172,359 )-->
C( 412, 4 ) --( 387,083 )-->
C( 619, 3 ) --( 867,079 )-->
C( 928, 104 ) --( 1,949,273 )-->
C( 1393, 53 ) --( 4,377,157 )-->
C( 2089, 108 ) --( 9,835,545 )-->
C( 3135, 12 ) --( 22,138,597 )-->
C( 4704, 0 ) --( 49,845,945 )-->
C( 7057, 1 ) --( 112,109,269 )-->
C( 10585, 4 ) --( 252,179,705 )-->
. . .

Note: Clive Tooth posted an analysis of this machine on Google Groups (sci.math>The Turing machine known as #r), on June 28, 2002.
He used the configurations S(n, x) = . . . 0101(B1)010(01)nx0 . . .
His analysis can be easily connected to the present one, by noting that

C(n, p) --( 15 )--> S(n - 2, R(bin(p))).

Marxen and Buntrock's second machine

See also the simulation by Heiner Marxen and the analyses by Robert Munafo (the short one and the detailed one). See detailed analysis in Michel (2015), Section 9.

This machine was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols, from October 2000 to March 2001.

Marxen and Buntrock (2000)
s(M) > 6.1 × 10925
sigma(M) > 6.4 × 10462
M=
0 1
A 1RB 0LB
B 0RC 1LB
C 1RD 0LA
D 1LE 1LF
E 1LA 0LD
F 1RH 1LE

Let C(n) = . . . 01n(B0)0 . . .
Then we have:

. . . 0(A0)0 . . . --( 1 )--> C(1)
C(3k) --( 54 × 4k+1 - 27 × 2k+3 + 26k + 86 )--> C(9 × 2k+1 - 8)
C(3k + 1) --( 2048 × (4k-1)/3 - 3 × 2k+7 + 26k + 792 )--> C(2k+5 - 8)
C(3k + 2) --( 3k + 8 )--> . . . 01(H1)(011)k(0101)0 . . .

So we have:

. . . 0(A0)0 . . . --( 1 )-->
C( 1 ) --( 408 )-->
C( 24 ) --( 14,100,774 )-->
C( 4600 ) --( 2048 × (4^1533 - 1)/3 - 3 × 2^1540 + 40650 )-->
C( 2^1538 - 8 ) --( 2^1538 - 2 )-->
. . . 01(H1)(011)p(0101)0 . . .
with p = (2^1538 - 10)/3.

So the total time is T = 2048 × (4^1533 - 1)/3 - 11 × 2^1538 + 14141831,
and the final number of 1 is: 2 × (2^1538 - 10)/3 + 4.

Note that
C(6k + 1) --(   )--> C(3m) --(   )--> C(6p + 4) --(   )--> C(3q + 2) --(   )--> END,
with m = (2^(2k+5) - 8)/3,
p = 3 × 2^m - 2,
q = (2^(2p+6) - 10)/3.

So all configurations C(n) lead to a halting configuration.
Those taking the most time are C(6k + 1).
For example: C(7) --( t )--> END with t > 10^(3.9 × 10^12).
More generally: C(6k + 1) --( t(k) )--> END with t(k) > 10^(10^(10^((3k + 2)/5))).

Marxen and Buntrock's third machine

See also the simulation by Heiner Marxen.
Marxen and Buntrock (2000)
s(M) > 6.1 × 10119
sigma(M) > 1.4 × 1060
M=
0 1
A 1RB 0LC
B 1LA 1RC
C 1RA 0LD
D 1LE 1LC
E 1RF 1RH
F 1RA 1RE

Let C(n, x) = . . . 0(E0)1000(10)nx0 . . ., so that C(n, 10y) = C(n + 1, y).
The number of transitions between configurations C(n, x) is infinite, but only 9 transitions are used in the computation on a blank tape:

. . . 0(A0)0 . . . --( 18 )--> C(1, 01)
C(2k, 01n) --( 6k2 + 22k + 15 )--> C(3k + 1, 01n+1)
C(2k, 11) --( 6k2 + 34k + 41 )--> C(3k + 4, 01)
C(2k, 111) --( 6k2 + 34k + 45 )--> C(3k + 5, 01)
C(2k, 1111) --( 6k2 + 28k + 25 )--> . . . 016k+11(H0)0 . . .
C(2k + 1, 0) --( 6k2 + 34k + 43 )--> C(3k + 4, 0)
C(2k + 1, 01) --( 6k2 + 22k + 27 )--> C(3k + 4, 01)
C(2k + 1, 01n+2) --( 6k2 + 22k + 23 )--> C(3k + 4, 1n)
C(2k + 1, 1n+2) --( 6k2 + 34k + 41 )--> C(3k + 4, 01n)

So we have (final configuration is reached in 337 transitions):

. . . 0(A0)0 . . . --( 18 )-->
C( 1, 01 ) --( 27 )-->
C( 4, 01 ) --( 83 )-->
C( 7, 011 ) --( 143 )-->
C( 13, 0 ) --( 463 )-->
C( 22, 0 ) --( 983 )-->
C( 34, 01 ) --( 2,123 )-->
C( 52, 011 ) --( 4,643 )-->
C( 79, 0111 ) --( 10,007 )-->
C( 122, 0 ) --( 23,683 )-->
C( 184, 01 ) --( 52,823 )-->
C( 277, 011 ) --( 117,323 )-->
C( 418, 0 ) --( 266,699 )-->
C( 628, 01 ) --( 598,499 )-->
C( 943, 011 ) --( 1,341,431 )-->
C( 1417, 0 ) --( 3,031,699 )-->
C( 2128, 0 ) --( 6,815,999 )-->
C( 3193, 01 ) --( 15,318,435 )-->
C( 4792, 01 ) --( 34,497,623 )-->
C( 7189, 011 ) --( 77,580,107 )-->
C( 10786, 0 ) --( 174,625,355 )-->
. . .

Note that, if C(n, m) = . . . 0(E0)1000(10)nR(bin(m))0 . . ., where R(bin(m)) is the number m written in binary in reverse order, so that C(n, 4m + 1) = C(n + 1, m), then we have also:

. . . 0(A0)0 . . . --( 18 )--> C(1, 2)
C(2k, 2m) --( 6k2 + 22k + 15 )--> C(3k + 1, 4m + 2)
C(2k, 32m + 3) --( 6k2 + 34k + 41 )--> C(3k + 4, 4m + 2)
C(2k, 128m + 7) --( 6k2 + 34k + 45 )--> C(3k + 5, 4m + 2)
C(2k, 32m + 15) --( 6k2 + 28k + 25 )--> . . . 016k+11(H0)R(bin(m))0 . . .
C(2k + 1, 4m) --( 6k2 + 34k + 43 )--> C(3k + 4, 2m)
C(2k + 1, 32m + 2) --( 6k2 + 22k + 27 )--> C(3k + 4, 4m + 2)
C(2k + 1, 8m + 6) --( 6k2 + 22k + 23 )--> C(3k + 4, m)
C(2k + 1, 4m + 3) --( 6k2 + 34k + 41 )--> C(3k + 4, 2m)

Another Marxen and Buntrock's machine

See also the simulation by Heiner Marxen.

This machine was discovered in January 1990, and was published on the web (Google groups) on September 3, 1997.
It was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols up to July 2000.
Marxen and Buntrock (1997)
s(M) = 8,690,333,381,690,951
sigma(M) = 95,524,079
M=
0 1
A 1RB 1RA
B 1LC 1LB
C 0RF 1LD
D 1RA 0LE
E 1RH 1LF
F 0LA 0LC

Note the likeness to the machine N with 3 states and 3 symbols discovered, in August 2006, by Terry and Shawn Ligocki.
For this machine N, we have s(N) = 4,345,166,620,336,565 and sigma(N)= 95,524,079, that is, same value of sigma, and almost half the value of s. See analysis of this similarity.

Analysis by Robert Munafo:

Let C(n) = . . . 0(D0)1n0 . . .
Then we have:

. . . 0(A0)0 . . . --( 3 )--> C(2)
C(4k) --( 8k + 6 )--> . . . 01(H0)(10)2k110 . . .
C(4k + 1) --( 20k2 + 56k + 30 )--> C(10k + 9)
C(4k + 2) --( 20k2 + 56k + 33 )--> C(10k + 9)
C(4k + 3) --( 20k2 + 68k + 51 )--> C(10k + 12)

So we have:

. . . 0(A0)0 . . . --( 3 )-->
C( 2 ) --( 33 )-->
C( 9 ) --( 222 )-->
C( 29 ) --( 1,402 )-->
C( 79 ) --( 8,563 )-->
C( 202 ) --( 52,833 )-->
C( 509 ) --( 329,722 )-->
C( 1,279 ) --( 2,056,963 )-->
C( 3,202 ) --( 12,844,833 )-->
C( 8,009 ) --( 80,272,222 )-->
C( 20,029 ) --( 501,681,402 )-->
C( 50,079 ) --( 3,135,358,563 )-->
C( 125,202 ) --( 19,595,552,833 )-->
C( 313,009 ) --( 122,471,892,222 )-->
C( 782,529 ) --( 765,448,543,902 )-->
C( 1,956,329 ) --( 4,784,051,443,102 )-->
C( 4,890,829 ) --( 29,900,316,628,602 )-->
C( 12,227,079 ) --( 186,876,942,247,563 )-->
C( 30,567,702 ) --( 1,167,980,782,060,333 )-->
C( 76,419,259 ) --( 7,299,879,658,619,323 )-->
C( 191,048,152 ) --( 382,096,310 )-->
. . . 01(H0)(10)95524076110 . . .

Turing machines with 3 states and 3 symbols

Ligockis' champion

See also the simulation by Heiner Marxen. See detailed analysis in Michel (2015), Section 3.

This machine is the record holder in the Busy Beaver Competition for machines with 3 states and 3 symbols, since November 2007.

Terry and Shawn Ligocki (2007)
s(M) = 119,112,334,170,342,540 =? S(3,3)
sigma(M) = 374,676,383 =? Sigma(3,3)
M=
0 1 2
A 1RB 2LA 1LC
B 0LA 2RB 1LB
C 1RH 1RA 1RC
Let C(n) = . . . 0(A0)2n0 . . .
Then we have:

. . . 0(A0)0 . . . --( 3 )--> C(1)
C(8k + 1) --( 112k2 + 116k + 13 )--> C(14k + 3)
C(8k + 2) --( 112k2 + 144k + 38 )--> C(14k + 7)
C(8k + 3) --( 112k2 + 172k + 54 )--> C(14k + 8)
C(8k + 4) --( 112k2 + 200k + 74 )--> C(14k + 9)
C(8k + 5) --( 112k2 + 228k + 97 )--> . . . 01(H1)214k+90 . . .
C(8k + 6) --( 112k2 + 256k + 139 )--> C(14k + 14)
C(8k + 7) --( 112k2 + 284k + 169 )--> C(14k + 15)
C(8k + 8) --( 112k2 + 312k + 203 )--> C(14k + 16)

So we have (in 34 transitions):

. . . 0(A0)0 . . . --( 3 )-->
C( 1 ) --( 13 )-->
C( 3 ) --( 54 )-->
C( 8 ) --( 203 )-->
C( 16 ) --( 627 )-->
C( 30 ) --( 1915 )-->
. . .
 
C( 122,343,306 ) --( 26,193,799,261,043,238 )-->
C( 214,100,789 ) --( 80,218,511,093,348,089 )-->
. . . 01(H1)23746763810 . . .

Ligockis' machine found in August 2006

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for machines with 3 states and 3 symbols, from August 2006 to November 2007.

Terry and Shawn Ligocki (2006)
s(M) = 4,345,166,620,336,565
sigma(M) = 95,524,079
M=
0 1 2
A 1RB 2RC 1LA
B 2LA 1RB 1RH
C 2RB 2RA 1LC

Note the likeness to the machine N with 6 states and 2 symbols discovered, in January 1990, by Heiner Marxen and Jürgen Buntrock.
For this machine N, we have s(N) = 8,690,333,381,690,951 and sigma(N)= 95,524,079, that is, same value of sigma, and almost twice the value of s. See analysis of this similarity.

Analysis by Shawn Ligocki:

Let C(n, 0) = . . . 0(A0)12n0 . . . ,
and C(n, 1) = . . . 0(C0)12n0 . . .
Then we have:

C(2k, 0) --( 40k2 + 32k + 5 )--> C(5k + 1, 1)
C(2k + 1, 0) --( 40k2 + 82k + 42 )--> . . . 0110k+9(H0)0 . . .
C(2k + 1, 1) --( 40k2 + 52k + 19 )--> C(5k + 3, 1)
C(2k + 2, 1) --( 40k2 + 92k + 53 )--> C(5k + 5, 0)

So we have:

. . . 0(A0)0 . . . = C( 0, 0 ) --( 5 )-->
C( 1, 1 ) --( 19 )-->
C( 3, 1 ) --( 111 )-->
C( 8, 1 ) --( 689 )-->
C( 20, 0 ) --( 4,325 )-->
C( 51, 1 ) --( 26,319 )-->
C( 128, 1 ) --( 164,609 )-->
C( 320, 0) --( 1,029,125 )-->
C( 801, 1 ) --( 6,420,819 )-->
C( 2003, 1 ) --( 40,132,111 )-->
C( 5008, 1 ) --( 250,830,689 )-->
C( 12520, 0 ) --( 1,567,704,325 )-->
C( 31301, 1 ) --( 9,797,713,819 )-->
C( 78253, 1 ) --( 61,235,789,611 )-->
C( 195633, 1 ) --( 382,723,880,691 )-->
C( 489083, 1 ) --( 2,392,024,743,391 )-->
C( 1222708, 1 ) --( 14,950,155,868,889 )-->
C( 3056770, 0 ) --( 93,438,477,237,325 )-->
C( 7641926, 1 ) --( 582,990,375,746,317 )-->
C( 19104815, 0 ) --( 3,649,939,963,043,376 )-->
. . . 0195524079(H0)0 . . .

Lafitte and Papazian's machine found in April 2006

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for machines with 3 states and 3 symbols, from April to August 2006.

Lafitte and Papazian (2006)
s(M) = 4,144,465,135,614
sigma(M) = 2,950,149
M=
0 1 2
A 1RB 1RH 2LC
B 1LC 2RB 1LB
C 1LA 2RC 2LA

Let C(n, 0) = . . . 0(A0)1n0 . . . ,
and C(n, 1) = . . . 0(A0)1n210 . . .
Then we have (note the likeness to Brady's machine):

. . . 0(A0)0 . . . --( 16 )--> C(6, 0)
C(2k + 1, 0) --( 4k + 5 )--> . . . 01(H2)22k10 . . .
C(2k + 2, 0) --( 10k2 + 27k + 23 )--> C(5k + 6, 1)
C(2k, 1) --( 10k2 + 27k + 18 )--> C(5k + 5, 1)
C(2k + 1, 1) --( 10k2 + 51k + 60 )--> C(5k + 12, 0)

So we have:

. . . 0(A0)0 . . . --( 16 )-->
C( 6, 0 ) --( 117 )-->
C( 16, 1 ) --( 874 )-->
C( 45, 1 ) --( 6,022 )-->
C( 122, 0 ) --( 37,643 )-->
C( 306, 1 ) --( 238,239 )-->
C( 770, 1 ) --( 1,492,663 )-->
C( 1930, 1 ) --( 9,338,323 )-->
C( 4830, 1 ) --( 58,387,473 )-->
C( 12080, 1 ) --( 364,979,098 )-->
C( 30205, 1 ) --( 2,281,474,302 )-->
C( 75522, 0 ) --( 14,259,195,543 )-->
C( 188806, 1 ) --( 89,121,812,989 )-->
C( 472020, 1 ) --( 557,013,573,288 )-->
C( 1180055, 1 ) --( 3,481,348,698,727 )-->
C( 2950147, 0 ) --( 5,900,297 )-->
. . . 01(H2)2295014610 . . .

Note that we have also:

. . . 0(A0)0 . . . --( 133 )--> C(16, 1)
C(2k, 1) --( 10k2 + 27k + 18 )--> C(5k + 5, 1)
C(4k + 1, 1) --( 290k2 + 737k + 468 )--> C(25k + 31, 1)
C(4k + 3, 1) --( 40k2 + 162k + 158 )--> . . . 01(H2)210k+1610 . . .

Lafitte and Papazian's machine found in September 2005

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for machines with 3 states and 3 symbols, from September 2005 to April 2006.

Lafitte and Papazian (2005)
s(M) = 987,522,842,126
sigma(M) = 1,525,688
M=
0 1 2
A 1RB 2LA 1RA
B 1RC 2RB 0RC
C 1LA 1RH 1LA

Let C(n, 0) = . . . 0(A0)2n0 . . . ,
and C(n, 1) = . . . 0(A0)2n10 . . .
Then we have:

C(4k, 0) --( 14k2 + 16k + 5 )--> C(7k + 2, 1)
C(4k + 1, 0) --( 14k2 + 30k + 15 )--> C(7k + 5, 0)
C(4k + 2, 0) --( 14k2 + 30k + 15 )--> C(7k + 5, 0)
C(4k + 3, 0) --( 14k2 + 44k + 35 )--> C(7k + 9, 1)
C(2k + 1, 1) --( 4k + 3 )--> . . . 01(12)k01(H0)0 . . .
C(4k, 1) --( 14k2 + 26k + 11 )--> C(7k + 4, 0)
C(4k + 2, 1) --( 14k2 + 40k + 29 )--> C(7k + 8, 1)

So we have:

. . . 0(A0)0 . . . = C( 0, 0 ) --( 5 )-->
C( 2, 1 ) --( 29 )-->
C( 8, 1 ) --( 119 )-->
C( 18, 0 ) --( 359 )-->
C( 33, 0 ) --( 1,151 )-->
C( 61, 0 ) --( 3,615 )-->
C( 110, 0 ) --( 11,031 )-->
C( 194, 0 ) --( 33,711 )-->
C( 341, 0 ) --( 103,715 )-->
C( 600, 0 ) --( 317,405 )-->
C( 1052, 1 ) --( 975,215 )-->
C( 1845, 0 ) --( 2,989,139 )-->
C( 3232, 0 ) --( 9,153,029 )-->
C( 5658, 1 ) --( 28,048,133 )-->
C( 9906, 1 ) --( 85,927,133 )-->
C( 17340, 1 ) --( 263,203,871 )-->
C( 30349, 0 ) --( 806,103,591 )-->
C( 53114, 0 ) --( 2,468,672,331 )-->
C( 92951, 0 ) --( 7,560,436,829 )-->
C( 162668, 1 ) --( 23,154,325,799 )-->
C( 284673, 0 ) --( 70,910,514,191 )-->
C( 498181, 0 ) --( 217,164,134,715 )-->
C( 871820, 0 ) --( 665,064,835,635 )-->
C( 1525687, 1 ) --( 3,051,375 )-->
. . . 01(12)76284301(H0)0 . . .

Lafitte and Papazian's machine found in August 2005

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for machines with 3 states and 3 symbols, from August to September 2005.

Lafitte and Papazian (2005)
s(M) = 4,939,345,068
sigma(M) = 107,900
M=
0 1 2
A 1RB 1RH 2RB
B 1LC 0LB 1RA
C 1RA 2LC 1RC

Let C(n, 0) = . . . 0(C0)2n0 . . . ,
and C(n, 1) = . . . 0(C0)2n10 . . .
Then we have:

. . . 0(A0)0 . . . --( 3 )--> C(1, 1)
C(4k, 0) --( 14k2 + 16k + 5 )--> C(7k + 2, 1)
C(4k + 1, 0) --( 14k2 + 22k + 7 )--> C(7k + 3, 0)
C(4k + 2, 0) --( 14k2 + 30k + 15 )--> C(7k + 5, 0)
C(4k + 3, 0) --( 14k2 + 36k + 23 )--> C(7k + 7, 1)
C(2k, 1) --( 2k + 2 )--> . . . 01(21)k1(H0)0 . . .
C(4k + 1, 1) --( 14k2 + 20k + 9 )--> C(7k + 3, 1)
C(4k + 3, 1) --( 14k2 + 34k + 21 )--> C(7k + 6, 0)

So we have:

. . . 0(A0)0 . . . --( 3 )-->
C( 1, 1 ) --( 9 )-->
C( 3, 1 ) --( 21 )-->
C( 6, 0 ) --( 59 )-->
C( 12, 0 ) --( 179 )-->
C( 23, 1 ) --( 541 )-->
C( 41, 0 ) --( 1,627 )-->
C( 73, 0 ) --( 4,939 )-->
C( 129, 0 ) --( 15,047 )-->
C( 227, 0 ) --( 45,943 )-->
C( 399, 1 ) --( 140,601 )-->
C( 699, 0 ) --( 430,151 )-->
C( 1225, 1 ) --( 1,317,033 )-->
C( 2145, 1 ) --( 4,032,873 )-->
C( 3755, 1 ) --( 12,349,729 )-->
C( 6572, 0 ) --( 37,818,579 )-->
C( 11503, 1 ) --( 115,816,521 )-->
C( 20131, 0 ) --( 354,675,511 )-->
C( 35231, 1 ) --( 1,086,184,945 )-->
C( 61655, 0 ) --( 3,326,402,857 )-->
C( 107898, 1 ) --( 107,900 )-->
. . . 01(21)539491(H0)0 . . .

Souris's machine for S(3,3)

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for S(3,3), from July to August 2005.

Souris (2005)
s(M) = 544,884,219
sigma(M) = 32,213
M=
0 1 2
A 1RB 1LB 2LA
B 1LA 1RC 1RH
C 0LA 2RC 1LC

Let C(n, 0) = . . . 0(A0)1n0 . . . ,
and C(n, 1) = . . . 0(A0)1n20 . . .
Then we have:

. . . 0(A0)0 . . . --( 4 )--> C(3, 0)
C(3k + 2, 0) --( 21k2 + 43k + 19 )--> . . . 011(H2)27k + 10 . . .
C(3k + 3, 0) --( 21k2 + 43k + 24 )--> C(7k + 7, 0)
C(3k + 4, 0) --( 21k2 + 43k + 26 )--> C(7k + 7, 1)
C(3k + 1, 1) --( 21k2 + 61k + 35 )--> . . . 011(H2)27k + 30 . . .
C(3k + 2, 1) --( 21k2 + 61k + 42 )--> C(7k + 9, 0)
C(3k + 3, 1) --( 21k2 + 61k + 46 )--> C(7k + 9, 1)

So we have:

. . . 0(A0)0 . . . --( 4 )-->
C( 3, 0 ) --( 24 )-->
C( 7, 0 ) --( 90 )-->
C( 14, 1 ) --( 622 )-->
C( 37, 0 ) --( 3,040 )-->
C( 84, 1 ) --( 17,002 )-->
C( 198, 1 ) --( 92,736 )-->
C( 464, 1 ) --( 507,472 )-->
C( 1087, 0 ) --( 2,752,290 )-->
C( 2534, 1 ) --( 15,010,582 )-->
C( 5917, 0 ) --( 81,666,440 )-->
C( 13804, 1 ) --( 444,833,917 )-->
. . . 011(H2)2322100 . . .

Souris's machine for Sigma(3,3)

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for Sigma(3,3), from July to August 2005.

Souris (2005)
s(M) = 310,341,163
sigma(M) = 36,089
M=
0 1 2
A 1RB 2RA 2RC
B 1LC 1RH 1LA
C 1RA 2LB 1LC

Let C(n, 0) = . . . 0(C0)1n0 . . .,
and C(n, 1) = . . . 0(C0)1n210 . . .
Then we have:

. . . 0(A0)0 . . . --( 4 )--> C(1, 1)
C(2k + 2, 0) --( 5k2 + 32k + 17 )--> C(5k + 5, 0)
C(2k + 3, 0) --( 5k2 + 32k + 21 )--> C(5k + 4, 1)
C(2k + 1, 1) --( 5k2 + 32k + 15 )--> C(5k + 4, 0)
C(2k + 2, 1) --( 5k2 + 37k + 30 )--> . . . 0125k + 51(H2)10 . . .

So we have:

. . . 0(A0)0 . . . --( 4 )-->
C( 1, 1 ) --( 15 )-->
C( 4, 0 ) --( 54 )-->
C( 10, 0 ) --(225 )-->
C( 25, 0 ) --( 978 )-->
C( 59, 1 ) --( 5,148 )-->
C( 149, 0 ) --( 29,002 )-->
C( 369, 1 ) --( 175,183 )-->
C( 924, 0 ) --( 1,077,374 )-->
C( 2310, 0 ) --( 6,695,525 )-->
C( 5775, 0 ) --( 41,737,353 )-->
C( 14434, 1 ) --( 260,620,302 )-->
. . . 012360851(H2)10 . . .

Note that we have also:

. . . 0(A0)0 . . . --( 19 )--> C(4, 0)
C(2k + 2, 0) --( 5k2 + 32k + 17 )--> C(5k + 5, 0)
C(4k + 3, 0) --( 145k2 + 299k + 93 )--> . . . 01225k + 101(H2)10 . . .
C(4k + 5, 0) --( 145k2 + 444k + 281 )--> C(25k + 24, 0)

Brady's machine

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for machines with 3 states and 3 symbols, from December 2004 to July 2005.

Brady (2004)
s(M) = 92,649,163
sigma(M) = 13,949
M=
0 1 2
A 1RB 1RH 2LC
B 1LC 2RB 1LB
C 1LA 0RB 2LA

Let C(n, 0) = . . . 0(A0)1n0 . . .,
and C(n, 1) = . . . 0(A0)1n210 . . .
Then we have:

. . . 0(A0)0 . . . --( 6 )--> C(0, 1)
C(2k + 1, 0) --( 4k + 5 )--> . . . 01(H2)22k10 . . .
C(2k + 2, 0) --( 10k2 + 15k + 10 )--> C(5k + 3, 1)
C(2k, 1) --( 10k2 + 27k + 18 )--> C(5k + 5, 1)
C(2k + 1, 1) --( 10k2 + 51k + 60 )--> C(5k + 12, 0)

So we have:

. . . 0(A0)0 . . . --( 6 )-->
C( 0, 1 ) --( 18 )-->
C( 5, 1 ) --( 202 )-->
C( 22, 0 ) --( 1,160 )-->
C( 53, 1 ) --( 8,146 )-->
C( 142, 0 ) --( 50,060 )-->
C( 353, 1 ) --( 318,796 )-->
C( 892, 0 ) --( 1,986,935 )-->
C( 2228, 1 ) --( 12,440,056 )-->
C( 5575, 1 ) --( 77,815,887 )-->
C( 13947, 0 ) --( 27,897 )-->
. . . 01(H2)21394610 . . .

Note that we have also:

. . . 0(A0)0 . . . --( 6 )--> C(0, 1)
C(2k, 1) --( 10k2 + 27k + 18 )--> C(5k + 5, 1)
C(4k + 1, 1) --( 290k2 + 677k + 395 )--> C(25k + 28, 1)
C(4k + 3, 1) --( 40k2 + 162k + 158 )--> . . . 01(H2)210k+1610 . . .

Turing machines with 2 states and 4 symbols

Ligockis' champion

See also the simulation by Heiner Marxen. See detailed analysis in Michel (2015), Section 4.

This machine is the record holder in the Busy Beaver Competition for machines with 2 states and 4 symbols, since February 2005.

Terry and Shawn Ligocki (2005)
s(M) = 3,932,964 =? S(2,4)
sigma(M) = 2,050 =? Sigma(2,4)
M=
0 1 2 3
A 1RB 2LA 1RA 1RA
B 1LB 1LA 3RB 1RH

Let C(n, 1) = . . . 0(A0)2n10 . . . ,
and C(n, 2) = . . . 0(A0)2n110 . . .
Then we have:

. . . 0(A0)0 . . . --( 6 )--> C(1, 2)
C(3k, 1) --( 15k2 + 9k + 3 )--> C(5k + 1, 1)
C(3k + 1, 1) --( 15k2 + 24k + 13 )--> . . . 0135k+21(H1)0 . . .
C(3k + 2, 1) --( 15k2 + 29k + 17 )--> C(5k + 4, 2)
C(3k, 2) --( 15k2 + 11k + 3 )--> C(5k + 1, 2)
C(3k + 1, 2) --( 15k2 + 21k + 7 )--> C(5k + 3, 1)
C(3k + 2, 2) --( 15k2 + 36k + 23 )--> . . . 0135k+41(H1)0 . . .

So we have:

. . . 0(A0)0 . . . --( 6 )-->
C( 1, 2 ) --( 7 )-->
C( 3, 1 ) --( 27 )-->
C( 6, 1 ) --( 81 )-->
C( 11, 1 ) --( 239 )-->
C( 19, 2 ) --( 673 )-->
C( 33, 1 ) --( 1,917 )-->
C( 56, 1 ) --( 5,399 )-->
C( 94, 2 ) --( 15,073 )-->
C( 158, 1 ) --( 42,085 )-->
C( 264, 2 ) --( 117,131 )-->
C( 441, 2 ) --( 325,755 )-->
C( 736, 2 ) --( 905,527 )-->
C( 1228, 1 ) --( 2,519,044 )-->
. . . 01320471(H1)0 . . .

Brady's runner-up

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for machines with 2 states and 4 symbols, from 1988 to February 2005.

Brady (1988)
s(M) = 7,195
sigma(M) = 90
M=
0 1 2 3
A 1RB 3LA 1LA 1RA
B 2LA 1RH 3RA 3RB

Let C(n, 0) = . . . 0(A0)3n0 . . . ,
and C(n, 1) = . . . 0(A0)3n20 . . .
Then we have:

C(3k, 0) --( 15k2 + 7k + 3 )--> C(5k + 1, 1)
C(3k + 1, 0) --( 15k2 + 22k + 11 )--> . . . 0135k+11(H0)0 . . .
C(3k + 2, 0) --( 15k2 + 27k + 13 )--> C(5k + 4, 0)
C(3k, 1) --( 15k2 + 28k + 16 )--> . . . 0135k+31(H0)0 . . .
C(3k + 1, 1) --( 15k2 + 33k + 19 )--> C(5k + 5, 0)
C(3k + 2, 1) --( 15k2 + 43k + 33 )--> C(5k + 7, 1)

So we have:

. . . 0(A0)0 . . . = C( 0, 0 ) --( 3 )-->
C( 1, 1 ) --( 19 )-->
C( 5, 0 ) --( 55 )-->
C( 9, 0 ) --( 159 )-->
C( 16, 1 ) --( 559 )-->
C( 30, 0 ) --( 1,573 )-->
C( 51, 1 ) --( 4,827 )-->
. . . 013881(H0)0 . . .

Turing machines with 2 states and 5 symbols

Ligockis' champion

See also the simulation by Heiner Marxen. See detailed analysis in Michel (2015), Section 5.

This machine was the record holder in the Busy Beaver Competition for machines with 2 states and 5 symbols, from November 2007 to July 2023.

Terry and Shawn Ligocki (2007)
s(M) and S(2,5) > 1.9 × 10704
sigma(M) and Sigma(2,5) > 1.7 × 10352
M=
0 1 2 3 4
A 1RB 2LA 1RA 2LB 2LA
B 0LA 2RB 3RB 4RA 1RH

Let C(n, 1) = . . . 013n(B0)0 . . .,
and C(n, 2) = . . . 023n(B0)0 . . .,
and C(n, 3) = . . . 03n(B0)0 . . .,
and C(n, 4) = . . . 04113n(B0)0 . . .,
and C(n, 5) = . . . 04123n(B0)0 . . .,
and C(n, 6) = . . . 0413n(B0)0 . . .,
and C(n, 7) = . . . 0423n(B0)0 . . .,
and C(n, 8) = . . . 043n(B0)0 . . ..
Then we have:

. . . 0(A0)0 . . . --( 1 )--> C(0, 1)
C(2k, 1) --( 3k2 + 8k + 4 )--> C(3k + 1, 1)
C(2k + 1, 1) --( 3k2 + 8k + 4 )--> C(3k + 1, 2)
C(2k, 2) --( 3k2 + 14k + 9 )--> C(3k + 2, 1)
C(2k + 1, 2) --( 3k2 + 8k + 4 )--> C(3k + 2, 3)
C(2k, 3) --( 3k2 + 8k + 2 )--> C(3k, 1)
C(2k + 1, 3) --( 3k2 + 8k + 22 )--> C(3k + 1, 4)
C(2k, 4) --( 3k2 + 8k + 8 )--> C(3k + 3, 1)
C(2k + 1, 4) --( 3k2 + 8k + 4 )--> C(3k + 1, 5)
C(2k, 5) --( 3k2 + 14k + 13 )--> C(3k + 4, 1)
C(2k + 1, 5) --( 3k2 + 8k + 4 )--> C(3k + 2, 6)
C(2k, 6) --( 3k2 + 8k + 6 )--> C(3k + 2, 1)
C(2k + 1, 6) --( 3k2 + 8k + 4 )--> C(3k + 1, 7)
C(2k, 7) --( 3k2 + 14k + 11 )--> C(3k + 3, 1)
C(2k + 1, 7) --( 3k2 + 8k + 4 )--> C(3k + 2, 8)
C(2k, 8) --( 3k2 + 8k + 4 )--> C(3k + 1, 1)
C(2k + 1, 8) --( 3k2 + 5k + 3 )--> . . . 01(H2)23k0 . . .

So we have (final configuration is reached in 2002 transitions):

. . . 0(A0)0 . . . --( 1 )-->
C( 0, 1 ) --( 4 )-->
C( 1, 1 ) --( 4 )-->
C( 1, 2 ) --( 4 )-->
C( 2, 3 ) --( 13 )-->
C( 3, 1 ) --( 15 )-->
C( 4, 2 ) --( 49 )-->
C( 8, 1 ) --( 84 )-->
C( 13, 1 ) --( 160 )-->
C( 19, 2 ) --( 319 )-->
C( 29, 3 ) --( 722 )-->
C( 43, 4 ) --( 1495 )-->
C( 64, 5 ) --( 3533 )-->
C( 100, 1 ) --( 7904 )-->
. . .

Ligockis' machine found in August 2006

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for machines with 2 states and 5 symbols, from August 2006 to October 2007.

Terry and Shawn Ligocki (2006)
s(M) = 7,069,449,877,176,007,352,687
sigma(M) = 172,312,766,455
M=
0 1 2 3 4
A 1RB 0RB 4RA 2LB 2LA
B 2LA 1LB 3RB 4RA 1RH

Analysis by Shawn Ligocki:

Let C(n, 1) = . . . 03n(B0)0 . . .,
and C(n, 2) = . . . 013n(B0)0 . . .,
and C(n, 3) = . . . 01403n(B0)0 . . .,
and C(n, 4) = . . . 01413n(B0)0 . . ..
Then we have:

. . . 0(A0)0 . . . --( 1 )--> C(0, 2)
C(2k, 1) --( 5k2 + 14k + 3 )--> C(5k + 1, 2)
C(2k + 1, 1) --( 5k2 + 14k + 7 )--> C(5k + 3, 2)
C(2k, 2) --( 5k2 + 14k + 3 )--> C(5k + 1, 1)
C(2k + 1, 2) --( 5k2 + 14k + 11 )--> C(5k + 2, 3)
C(2k, 3) --( 5k2 + 14k + 3 )--> C(5k + 1, 4)
C(2k + 1, 3) --( 5k2 + 14k + 9 )--> C(5k + 4, 1)
C(2k, 4) --( 5k2 + 14k + 3 )--> C(5k + 1, 3)
C(2k + 1, 4) --( 5k2 + 9k + 4 )--> . . . 011(H1)25k+20 . . .

So we have:

. . . 0(A0)0 . . . --( 1 )-->
C( 0, 2 ) --( 3 )-->
C( 1, 1 ) --( 7 )-->
C( 3, 2 ) --( 30 )-->
C( 7, 3 ) --( 96 )-->
C( 19, 1 ) --( 538 )-->
C( 48, 2 ) --( 3,219 )-->
C( 121, 1 ) --( 18,847 )-->
C( 303, 2 ) --( 116,130 )-->
C( 757, 3 ) --( 719,721 )-->
C( 1894, 1 ) --( 4,497,306 )-->
C( 4736, 2 ) --( 28,070,275 )-->
C( 11841, 1 ) --( 175,314,887 )-->
C( 29603, 2 ) --( 1,095,555,230 )-->
C( 74007, 3 ) --( 6,846,628,096 )-->
C( 185019, 1 ) --( 42,790,870,538 )-->
C( 462548, 2 ) --( 267,441,553,219 )-->
C( 1156371, 1 ) --( 1,671,497,565,722 )-->
C( 2890928, 2 ) --( 10,446,851,112,979 )-->
C( 7227321, 1 ) --( 65,292,743,569,247 )-->
C( 18068303, 2 ) --( 408,079,547,932,130 )-->
C( 45170757, 3 ) --( 2,550,496,813,209,721 )-->
C( 112926894, 1 ) --( 15,940,605,026,097,306 )-->
C( 282317236, 2 ) --( 99,628,779,154,570,275 )-->
C( 705793091, 1 ) --( 622,679,862,305,236,762 )-->
C( 1764482728, 2 ) --( 3,891,749,134,114,281,579 )-->
C( 4411206821, 1 ) --( 24,323,432,041,896,588,247 )-->
C( 11028017053, 2 ) --( 152,021,450,201,199,582,755 )-->
C( 27570042632, 3 ) --( 950,134,063,605,862,157,707 )-->
C( 68925106581, 4 ) --( 5,938,337,896,640,612,100,114 )-->
. . . 011(H1)21723127664520 . . .

Lafitte and Papazian's machine found in June 2006

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for Sigma(2,5), from June to August 2006.

G. Lafitte and C. Papazian (2006)
s(M) = 14,103,258,269,249
sigma(M) = 4,848,239
M=
0 1 2 3 4
A 1RB 3LB 4LB 4LA 2RA
B 2LA 1RH 3RB 4RA 3RB

Let C(n, 1) = . . . 0132n33(B0)0 . . .,
and C(n, 2) = . . . 01342n33(B0)0 . . .,
and C(n, 3) = . . . 0142n33(B0)0 . . .,
and C(n, 4) = . . . 012n33(B0)0 . . ..
Then we have:

. . . 0(A0)0 . . . --( 10 )--> C(0, 1)
C(2k, 1) --( 3k2 + 12k + 15 )--> C(3k + 2, 2)
C(2k + 1, 1) --( 3k2 + 12k + 11 )--> C(3k + 2, 3)
C(2k, 2) --( 3k2 + 12k + 9 )--> C(3k + 2, 1)
C(2k + 1, 2) --( 3k2 + 18k + 30 )--> C(3k + 5, 2)
C(2k, 3) --( 3k2 + 12k + 9 )--> C(3k + 2, 4)
C(2k + 1, 3) --( 3k2 + 18k + 28 )--> C(3k + 4, 2)
C(2k, 4) --( 3k2 + 12k + 13 )--> C(3k + 1, 2)
C(2k + 1, 4) --( 3k2 + 9k + 5 )--> . . . 01(H4)43k+220 . . .

So we have:

. . . 0(A0)0 . . . --( 10 )-->
C( 0, 1 ) --( 15 )-->
C( 2, 2 ) --( 24 )-->
C( 5, 1 ) --( 47 )-->
C( 8, 3 ) --( 105 )-->
C( 14, 4 ) --( 244 )-->
C( 22, 2 ) --( 504 )-->
C( 35, 1 ) --( 1,082 )-->
C( 53, 3 ) --( 2,524 )-->
C( 82, 2 ) --( 5,544 )-->
C( 125, 1 ) --( 12,287 )-->
C( 188, 3 ) --( 27,645 )-->
C( 284, 4 ) --( 62,209 )-->
C( 427, 2 ) --( 139,971 )-->
C( 644, 2 ) --( 314,925 )-->
C( 968, 1 ) --( 708,591 )-->
C( 1454, 2 ) --( 1,594,320 )-->
C( 2183, 1 ) --( 3,583,946 )-->
C( 3275, 3 ) --( 8,068,801 )-->
C( 4915, 2 ) --( 18,154,803 )-->
C( 7376, 2 ) --( 40,848,297 )-->
C( 11066, 1 ) --( 91,908,678 )-->
C( 16601, 2 ) --( 206,819,430 )-->
C( 24905, 2 ) --( 465,381,078 )-->
C( 37361, 2 ) --( 1,047,163,470 )-->
C( 56045, 2 ) --( 2,356,201,878 )-->
C( 84071, 2 ) --( 5,301,580,335 )-->
C( 126110, 2 ) --( 11,928,555,744 )-->
C( 189167, 1 ) --( 26,838,966,674 )-->
C( 283751, 3 ) --( 60,388,100,653 )-->
C( 425629, 2 ) --( 135,873,226,470 )-->
C( 638447, 2 ) --( 305,715,717,231 )-->
C( 957674, 2 ) --( 687,860,363,760 )-->
C( 1436513, 1 ) --( 1,547,683,663,691 )-->
C( 2154770, 3 ) --( 3,482,288,243,304 )-->
C( 3232157, 4 ) --( 7,835,138,850,959 )-->
. . . 01(H4)4484823620 . . .

Lafitte and Papazian's machine found in May 2006

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for machines with 2 states and 5 symbols, from May to June 2006.

G. Lafitte and C. Papazian (2006)
s(M) = 3,793,261,759,791
sigma(M) = 2,576,467
M=
0 1 2 3 4
A 1RB 3RA 4LB 2RA 3LA
B 2LA 1RH 4RB 4RB 2LB

Let C(n, 1) = . . . 014n(B0)0 . . .,
and C(n, 2) = . . . 034n(B0)0 . . .
Then we have:

. . . 0(A0)0 . . . --( 1 )--> C(0, 1)
C(3k, 1) --( 4k2 + 17k + 11 )--> C(4k + 3, 1)
C(3k + 1, 1) --( 4k2 + 25k + 20 )--> C(4k + 4, 1)
C(3k + 2, 1) --( 4k2 + 17k + 13 )--> C(4k + 3, 2)
C(3k, 2) --( 4k2 + 17k + 11 )--> C(4k + 3, 1)
C(3k + 1, 2) --( 4k2 + 25k + 20 )--> C(4k + 4, 1)
C(3k + 2, 2) --( 4k2 + 21k + 24 )--> . . . 01(H2)234k+320 . . .

So we have:

. . . 0(A0)0 . . . --( 1 )-->
C( 0, 1 ) --( 11 )-->
C( 3, 1 ) --( 32 )-->
C( 7, 1 ) --( 86 )-->
C( 12, 1 ) --( 143 )-->
C( 19, 1 ) --( 314 )-->
C( 28, 1 ) --( 569 )-->
C( 40, 1 ) --( 1,021 )-->
C( 56, 1 ) --( 1,615 )-->
C( 75, 2 ) --( 2,936 )-->
C( 103, 1 ) --( 5,494 )-->
C( 140, 1 ) --( 9,259 )-->
C( 187, 2 ) --( 16,946 )-->
C( 252, 1 ) --( 29,663 )-->
C( 339, 1 ) --( 53,008 )-->
C( 455, 1 ) --( 93,784 )-->
C( 607, 2 ) --( 168,286 )-->
C( 812, 1 ) --( 296,203 )-->
C( 1083, 2 ) --( 527,432 )-->
C( 1447, 1 ) --( 941,366 )-->
C( 1932, 1 ) --( 1,669,903 )-->
C( 2579, 1 ) --( 2,966,140 )-->
C( 3439, 2 ) --( 5,281,934 )-->
C( 4588, 1 ) --( 9,389,609 )-->
C( 6120, 1 ) --( 16,681,091 )-->
C( 8163, 1 ) --( 29,661,632 )-->
C( 10887, 1 ) --( 52,740,268 )-->
C( 14519, 1 ) --( 93,745,960 )-->
C( 19359, 2 ) --( 166,674,548 )-->
C( 25815, 1 ) --( 296,330,396 )-->
C( 34423, 1 ) --( 526,897,574 )-->
C( 45900, 1 ) --( 936,620,111 )-->
C( 61203, 1 ) --( 1,665,150,032 )-->
C( 81607, 1 ) --( 2,960,475,286 )-->
C( 108812, 1 ) --( 5,262,668,203 )-->
C( 145083, 2 ) --( 9,355,967,432 )-->
C( 193447, 1 ) --( 16,633,325,366 )-->
C( 257932, 1 ) --( 29,570,327,561 )-->
C( 343912, 1 ) --( 52,569,433,021 )-->
C( 458552, 1 ) --( 93,455,088,463 )-->
C( 611403, 2 ) --( 166,142,855,032 )-->
C( 815207, 1 ) --( 295,364,260,408 )-->
C( 1086943, 2 ) --( 525,094,796,254 )-->
C( 1449260, 1 ) --( 933,496,546,059 )-->
C( 1932347, 2 ) --( 1,659,550,059,339 )-->
. . . 01(H2)23257646320 . . .

Note that we have also:

. . . 0(A0)0 . . . --( 1 )--> C(0, 1)
C(3k, 1) --( 4k2 + 17k + 11 )--> C(4k + 3, 1)
C(3k + 1, 1) --( 4k2 + 25k + 20 )--> C(4k + 4, 1)
C(9k + 2, 1) --( 100k2 + 151k + 45 )--> C(16k + 7, 1)
C(9k + 5, 1) --( 100k2 + 239k + 120 )--> C(16k + 12, 1)
C(9k + 8, 1) --( 100k2 + 279k + 186 )--> . . . 01(H2)2316k+1520 . . .

Note: The machine obtained by replacing B4 --> 2LB by B4 --> 3LB has the same behavior but final configuration . . . 01(H3)3257646420 . . .

Lafitte and Papazian's machine found in December 2005

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for S(2,5), from December 2005 to May 2006.

G. Lafitte and C. Papazian (2005)
s(M) = 924,180,005,181
sigma(M) = 1,137,477
M=
0 1 2 3 4
A 1RB 3RA 1LA 1LB 3LB
B 2LA 4LB 3RA 2RB 1RH

Let C(n, 1) = . . . 012n(B0)0 . . .,
and C(n, 2) = . . . 032n(B0)0 . . .
Then we have:

. . . 0(A0)0 . . . --( 69 )--> C(8, 1)
C(2k + 1, 1) --( 15k2 + 37k + 31 )--> . . . 01221(H1)15k+120 . . .
C(2k + 2, 1) --( 15k2 + 32k + 19 )--> C(5k + 3, 2)
C(2k, 2) --( 15k2 + 32k + 19 )--> C(5k + 3, 1)
C(2k + 1, 2) --( 15k2 + 62k + 70 )--> C(5k + 9, 1)

So we have:

. . . 0(A0)0 . . . --( 69 )-->
C( 8, 1 ) --( 250 )-->
C( 18, 2 ) --( 1,522 )-->
C( 48, 1 ) --( 8,690 )-->
C( 118, 2 ) --( 54,122 )-->
C( 298, 1 ) --( 333,315 )-->
C( 743, 2 ) --( 2,087,687 )-->
C( 1864, 1 ) --( 13,031,226 )-->
C( 4658, 2 ) --( 81,438,162 )-->
C( 11648, 1 ) --( 508,796,290 )-->
C( 29118, 2 ) --( 3,179,933,122 )-->
C( 72798, 1 ) --( 19,873,380,815 )-->
C( 181993, 2 ) --( 124,209,722,062 )-->
C( 454989, 1 ) --( 776,311,217,849 )-->
. . . 01221(H1)1113747120 . . .

Note that we have also:

. . . 0(A0)0 . . . --( 69 )--> C(8, 1)
C(2k + 1, 1) --( 15k2 + 37k + 31 )--> . . . 01221(H1)15k+120 . . .
C(4k + 2, 1) --( 435k2 + 524k + 166 )--> C(25k + 14, 1)
C(4k + 4, 1) --( 435k2 + 884k + 453 )--> C(25k + 23, 1)

Lafitte and Papazian's machine found in October 2005

See also the simulation by Heiner Marxen.

This machine was the record holder in the Busy Beaver Competition for Sigma(2,5), from October 2005 to May 2006.

G. Lafitte and C. Papazian (2005)
s(M) = 912,594,733,606
sigma(M) = 1,957,771
M=
0 1 2 3 4
A 1RB 3LB 1RH 1LA 1LA
B 2LA 3RB 4LB 4LB 3RA

Let C(n, 1) = . . . 0(A0)1n20 . . .,
and C(n, 2) = . . . 0(A0)1n40 . . .,
and C(n, 3) = . . . 0(A0)1n320 . . .
Then we have:

. . . 0(A0)0 . . . --( 11 )--> C(3, 1)
C(2k + 1, 1) --( 5k2 + 28k + 26 )--> C(5k + 6, 1)
C(2k + 2, 1) --( 5k2 + 18k + 11 )--> C(5k + 3, 2)
C(2k, 2) --( 5k2 + 18k + 11 )--> C(5k + 3, 1)
C(2k + 1, 2) --( 5k2 + 18k + 13 )--> C(5k + 3, 3)
C(2k + 1, 3) --( 5k2 + 18k + 9 )--> C(5k + 3, 1)
C(2k + 2, 3) --( 5k2 + 23k + 17 )--> . . . 0135k+41(H0)0 . . .

So we have:

. . . 0(A0)0 . . . --( 11 )-->
C( 3, 1 ) --( 59 )-->
C( 11, 1 ) --( 291 )-->
C( 31, 1 ) --( 1,571 )-->
C( 81, 1 ) --( 9,146 )-->
C( 206, 1 ) --( 53,867 )-->
C( 513, 2 ) --( 332,301 )-->
C( 1283, 3 ) --( 2,065,952 )-->
C( 3208, 1 ) --( 12,876,910 )-->
C( 8018, 2 ) --( 80,432,578 )-->
C( 20048, 1 ) --( 502,483,070 )-->
C( 50118, 2 ) --( 3,140,218,478 )-->
C( 125298, 1 ) --( 19,624,987,195 )-->
C( 313243, 2 ) --( 122,653,507,396 )-->
C( 783108, 3 ) --( 766,577,764,781 )-->
. . . 01319577691(H0)0 . . .

Note that we have also:

. . . 0(A0)0 . . . --( 11 )--> C(3, 1)
C(2k + 1, 1) --( 5k2 + 28k + 26 )--> C(5k + 6, 1)
C(2k + 2, 1) --( 5k2 + 18k + 11 )--> C(5k + 3, 2)
C(2k, 2) --( 5k2 + 18k + 11 )--> C(5k + 3, 1)
C(4k + 1, 2) --( 145k2 + 176k + 45 )--> C(25k + 8, 1)
C(4k + 3, 2) --( 145k2 + 321k + 167 )--> . . . 01325k+191(H0)0 . . .

Collatz-like problems

  • Sameness of behaviors of the Turing machines above is striking.
    Their behaviors depend on transitions in the following form:
    C(ak + b) --(   )--> C(ck + d),
    where a, c are fixed, and b = 0, ..., a-1.
    Sometimes, another parameter is added: C(ak + b, p).

  • These transitions can be compared to the following problem.
    Let T be defined by
    T(x) = x/2,   if x is even,
    T(x) = (3x + 1)/2,   if x is odd.
    This can also be written
    T(2m) = m,
    T(2m + 1) = 3m + 2.
    When T is iterated over positive integers, do we always reach the loop: T(2) = 1, T(1) = 2 ?
    This question is a famous open problem in mathematics, called 3x + 1 problem, or Collatz problem.

  • A similar question can be asked about iterating transitions of configurations C(ak + b, p) on positive integers. Do the iterated transitions always reach a halting configuration?
    For all the machines above (except for the machine with 6 states and 2 symbols, found in October 2000), this question is presently an open problem in mathematics.
    Because of likeness to Collatz problem, these problems are called Collatz-like problems.
    Thus, for each machine above (except for the machine with 6 states and 2 symbols, found in October 2000) the halting problem (that is, on what inputs does this machine stop?) depends on an open Collatz-like problem.

Non-Collatz-like behaviors

Some Turing machines run a large number of steps on a small piece of tape.
Such machines do not seem to be Collatz-like.
We list below some interesting machines with this sort of behavior.

  • Turing machines with 3 states and 3 symbols

    A. H. Brady (November 2004)
    s(M) = 2,315,619
    sigma(M) = 31
    		M=
    0 1 2
    A 1RB 2LB 1LC
    B 1LA 2RB 1RB
    C 1RH 2LA 0LC

    Brady called this machine "Surprise-in-a-Box".

    See also the simulation by Heiner Marxen.

  • Turing machines with 2 states and 5 symbols

    G. Lafitte and C. Papazian (July 2006)
    s(M) = 26,375,397,569,930
    sigma(M) = 143
    M=
    0 1 2 3 4
    A 1RB 3LA 1LA 4LA 1RA
    B 2LB 2RA 1RH 0RA 0RB

    This machine was the record holder for S(2,5), from July to August 2006.

    See also the simulation by Heiner Marxen.

    G. Lafitte and C. Papazian (July 2006)
    s(M) = 7,021,292,621
    sigma(M) = 37
    M=
    0 1 2 3 4
    A 1RB 4LA 1LA 1RH 2RB
    B 2LB 3LA 1LB 2RA 0RB

Turing machines in distinct classes with similar behaviors

(2,4)-TM and (3,3)-TM

Terry and Shawn Ligocki (2005)
s(M) = 3,932,964 =? S(2,4)
sigma(M) = 2,050 =? Sigma(2,4)
M=
0 1 2 3
A 1RB 2LA 1RA 1RA
B 1LB 1LA 3RB 1RH

This machine is the record holder in the Busy Beaver Competition for machines with 2 states and 4 symbols, since February 2005.

A. H. Brady (2004)
s(M) = 3,932,964
sigma(M) = 2,050
M=
0 1 2
A 1RB 1LC 1RH
B 1LA 1LC 2RB
C 1RB 2LC 1RC

There is a step-by-step correspondence between the configurations of these machines.

(6,2)-TM and (3,3)-TM

Marxen and Buntrock (1997)
s(M) = 8,690,333,381,690,951
sigma(M) = 95,524,079
M=
0 1
A 1RB 1RA
B 1LC 1LB
C 0RF 1LD
D 1RA 0LE
E 1RH 1LF
F 0LA 0LC

This machine was discovered in January 1990, and was published on the web (Google groups) on September 3, 1997.
It was the record holder in the Busy Beaver Competition for machines with 6 states and 2 symbols up to July 2000.

Terry and Shawn Ligocki (2006)
s(M) = 4,345,166,620,336,565
sigma(M) = 95,524,079
M=
0 1 2
A 1RB 2RC 1LA
B 2LA 1RB 1RH
C 2RB 2RA 1LC

This machine was the record holder in the Busy Beaver Competition for machines with 3 states and 3 symbols, from August 2006 to November 2007.

Note that these machines have same sigma value, and the s value of the first one is almost twice the s value of the second one.

The behaviors of these machines can be linked as follows.

Given the analyses of the (6,2)-TM and the (3,3)-TM, the following functions can be defined:

f(4k) undefined,
f(4k + 1) = 10k + 9,
f(4k + 2) = 10k + 9,
f(4k + 3) = 10k + 12.

g(2k, 0) = (5k + 1, 1),
g(2k + 1, 0) undefined,
g(2k, 1) = (5k, 0),
g(2k + 1, 1) = (5k + 3, 1).

Now, let h be defined by

h(n, 0) = 10n + 2,
h(n, 1) = 10n - 1.

Then: h o g = f o h

There is no step-by-step correspondence between these machines, but there is a phase correspondence, according to functions f and g.

Link to Pascal Michel's home page