Behavior of busy beavers
Contents
Turing machines with 5 states and 2 symbols
Turing machines with 6 states and 2 symbols
1990
1990Marxen and Buntrock
Marxen and Buntrocks = 47,176,870, sigma = 4098
s = 23,554,764, sigma = 4097
Turing machines with 3 states and 3 symbols
May 2022
June 2010
May 2010
December 2007
November 2007
March 2001
October 2000
October 2000
September 1997Kropitz
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 2 states and 4 symbols
November 2007
August 2006
April 2006
September 2005
August 2005
July 2005
July 2005
December 2004T. and S. Ligocki
T. and S. Ligocki
Lafitte and Papazian
Lafitte and Papazian
Lafitte and Papazian
Souris
Souris
Bradys = 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 5 symbols
February 2005
1988T. and S. Ligocki
Bradys = 3,932,964, sigma = 2,050
s = 7,195, sigma = 90
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 |
Created by Pascal Michel in 2004
Last update: September 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.
Turing machines with 5 states and 2 symbols
Marxen and Buntrock's winner
See also the simulation by Heiner Marxen. This machine was analyzed by Buro (1991) (p.64-67), and independently by Michel (1993).This machine, found by Marxen and Buntrock in 1990, is the winner in the Busy Beaver Competition for machines with 5 states and 2 symbols, as proved by the bbchallenge collaboration in 2024.
|
M= |
|
Let C(n) = . . . 0(A0)1n0 . . .
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.
|
M= |
|
Let C(n) = . . . 0(A0)1n0 . . .
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.
|
M= |
|
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) |
. . . 0(A0)0 . . . --( 45 )-->
C( 5 ) --( 506 )-->
C( 35 ) --( 2,941,620,277 )-->
C( 88574 ) --( )-->
. . .
. . . 01(H0)1n0 . . .
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.
|
M= |
|
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) |
. . . 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.
|
M= |
|
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.
|
M= |
|
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 . . .
. . . 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.
|
M= |
|
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 . . .
. . . 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.
|
M= |
|
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 . . .
. . . 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.
|
M= |
|
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.
|
M= |
|
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 (the 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.
|
M= |
|
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.
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.
|
M= |
|
. . . 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.
|
M= |
|
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.
Let C(n, 0) = . . . 0(A0)12n0 . . . ,
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.
|
M= |
|
Let C(n, 0) = . . . 0(A0)1n0 . . . ,
. . . 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 . . .
. . . 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.
|
M= |
|
Let C(n, 0) = . . . 0(A0)2n0 . . . ,
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.
|
M= |
|
Let C(n, 0) = . . . 0(C0)2n0 . . . ,
. . . 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.
|
M= |
|
Let C(n, 0) = . . . 0(A0)1n0 . . . ,
. . . 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.
|
M= |
|
Let C(n, 0) = . . . 0(C0)1n0 . . .,
. . . 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 . . .
. . . 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.
|
M= |
|
Let C(n, 0) = . . . 0(A0)1n0 . . .,
. . . 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 . . .
. . . 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 winner in the Busy Beaver Competition for machines with 2 states and 4 symbols. It was found by Terry and Shawn Ligocki in February 2005. Shawn Ligocki and "Iijil" proved that it is the winner in April 2023.
|
M= |
|
Let C(n, 1) = . . . 0(A0)2n10 . . . ,
. . . 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.
|
M= |
|
Let C(n, 0) = . . . 0(A0)3n0 . . . ,
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.
|
||||||||||||||||||||
|
Let C(n, 1) = . . . 013n(B0)0 . . .,
. . . 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.
|
||||||||||||||||||||
|
Analysis by Shawn Ligocki:
Let C(n, 1) = . . . 03n(B0)0 . . .,
. . . 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.
|
||||||||||||||||||||
|
Let C(n, 1) = . . . 0132n33(B0)0 . . .,
. . . 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.
|
||||||||||||||||||||
|
Let C(n, 1) = . . . 014n(B0)0 . . .,
. . . 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.
|
||||||||||||||||||||
|
Let C(n, 1) = . . . 012n(B0)0 . . .,
. . . 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 . . .
. . . 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.
|
||||||||||||||||||||
|
Let C(n, 1) = . . . 0(A0)1n20 . . .,
. . . 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 . . .
. . . 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
C(ak + b) --( )--> C(ck + d),where a, c are fixed, and b = 0, ..., a-1.
T(x) = x/2, if x is even,This can also be written
T(x) = (3x + 1)/2, if x is odd.
T(2m) = m,When T is iterated over positive integers, do we always reach the loop: T(2) = 1, T(1) = 2 ?
T(2m + 1) = 3m + 2.
Non-Collatz-like behaviors
Some Turing machines run a large number of steps on a small piece of tape.Turing machines with 3 states and 3 symbols
|
M= |
|
Brady called this machine "Surprise-in-a-Box".
See also the simulation by Heiner Marxen.
Turing machines with 2 states and 5 symbols
|
||||||||||||||||||||
|
This machine was the record holder for S(2,5), from July to August 2006.
See also the simulation by Heiner Marxen.
|
||||||||||||||||||||
|
Turing machines in distinct classes with similar behaviors
(2,4)-TM and (3,3)-TM
|
M= |
|
This machine is the winner in the Busy Beaver Competition for machines with 2 states and 4 symbols, since April 2024.
|
M= |
|
There is a step-by-step correspondence between the configurations of these machines.
(6,2)-TM and (3,3)-TM
|
M= |
|
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.
|
M= |
|
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, |
g(2k, 0) = (5k + 1, 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.