BusyBeaverWiki - User contributions [en]

1RB2LC1RC 2LC---2RB 2LA0LB0RA

2026-11-07T20:32:20Z

Hipparcos: revise probvious halt step estimate

{{machine|1RB2LC1RC_2LC---2RB_2LA0LB0RA}} {{unsolved|Does this TM halt? If so, how many steps does it take to halt?}}
{{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}} is a [[BB(3,3)]] [[holdout]] which appears to [[probviously]] halt. If it can be proven to halt, it will be the BB(3,3) champion in terms of both steps and tape symbols. However, it could also turn out to be a probviously halting [[Cryptid]].

This is holdout #758 on Justin's 3x3 mugshots. After about 1.8 million steps and up to some relabelling, it is equivalent to holdout #153: {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}. And if you start in state C it is a [[permutation]] of the same machine. Together, they simulate a complex set of [[Collatz-like]] rules with two decreasing parameters.

After active exploration on the #bb3x3 channel by LegionMammal and dyuan, LegionMammal found (and dyuan confirmed) a configuration A(1,c) (defined [https://discord.com/channels/960643023006490684/1259770474897080380/1259968221218607145 here]) which halts and for which a huge "wall" of previous A(1, c') values all reach it. This gives strong evidence that the TM probviously halts since jumping over this wall is very "unlikely". If this TM does in fact halt at that configuration, it is expected to do so in 10414 to 10417 steps.<ref>https://discord.com/channels/960643023006490684/1259770474897080380/1568717661494448249</ref>

The TM has been simulated for over 1027 steps<ref>https://discord.com/channels/960643023006490684/1259770474897080380/1324065684677988505</ref>, reaching A(1, 1059491543272883(~1e15)).<ref>https://discord.com/channels/960643023006490684/1259770474897080380/1390819028137803829</ref>

== dyuan01's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1224457633176486041

<pre>
A_1(a, b, c) = 0^inf 1 2^a <C (22)^b (20)^c 0^inf
A_2(a, b, c) = 0^inf 1 2^a <A2 (22)^b (20)^c 0^inf
B(a, b) = 0^inf 1 2^a <B0 (20)^b 0^inf
</pre>

{| class="wikitable"
! From !! To
|-
| A1(0, b, 2n) || A2(1, b+2n+1, 0)
|-
| A1(0, b, 2n+1) || A1(1, 0, b+2n+3)
|-
| A1(m+1, b, 0) || A1(m, 0, b+2)
|-
| A1(m+1, b, n+1) || A2(m, b+1, n)
|-
| A2(0, b, 2n) || A1(2b+3, 0, 2n+1)
|-
| A2(0, b, 2n+1) || A2(2b+3, 2n+1, 0)
|-
| A2(m+1, b, 0) || B(m, b+2)
|-
| A2(m+1, b, n+1) || A1(m, b+2, n)
|-
| B(0, b) || Halt
|-
| B(m+1, 2n) || A2(m, 2n+1, 0)
|-
| B(m+1, 2n+1) || A1(m, 0, 2n+3)
|}
Starting from A1(0, 0, 1) (at step 2).

== A(a, c) Rules and Timings ==

Let A(a, c) = A1(a, 0, c) = <code>0^∞ 1 2^a <C (20)^c 0^∞</code>, where A1(a, b, c) comes from dyuan01's rules. Then the TM satisfies the following rules once it reaches A(0, 1) after 2 steps. Note that rules (a) and (g) aren't actually reachable from the initial condition.

{| class="wikitable" style="text-align:left"
|+ Rules and associated step counts ([https://discord.com/channels/960643023006490684/1259770474897080380/1324065684677988505 source])
! !! style="text-align:left" | A(a, c) → !! Conditions !! Step count
|-
! style="text-align:right" | (a)
| A(a−c−1, 3c/2+2) || c ≤ a−1, c ≡ 0 (mod 2) || 3c2+8c+5
|-
! style="text-align:right" | (b)
| A(a−c−2, 3(c−1)/2+5) || c ≤ a−2, c ≡ 1 (mod 4) || (6c2+31c+37)/2
|-
! style="text-align:right" | (c)
| A(a−c−4, 3(c−1)/2+8) || c ≤ a−4, c ≡ 3 (mod 4) || 3c2+29c+65
|-
! style="text-align:right" | (d)
| Halt(3(c−1)/2+7) || c = a−3, c ≡ 3 (mod 4) || (6c2+43c+75)/2
|-
! style="text-align:right" | (e)
| A(3c+8, 1) || c = a−2, c ≡ 3 (mod 4) || (6c2+37c+63)/2
|-
! style="text-align:right" | (f)
| Halt(3(c−1)/2+4) || c = a−1, c ≡ 1 (mod 2) || 3c2+8c+6
|-
! style="text-align:right" | (g)
| Halt(a/2+c+4) || c ≥ a, a ≡ 0, c ≡ 0 (mod 2) || 3a2+5a+9c+24
|-
! style="text-align:right" | (h)
| A(1, a/2+c+2) || c ≥ a, a ≡ 0, c ≡ 1 (mod 2) || 3a2+3a+5c+11
|-
! style="text-align:right" | (i)
| A(3a, c−a+4) || c ≥ a, a ≡ 1, c ≡ 0 (mod 2) || 3a2−9a+14c+30
|-
! style="text-align:right" | (j)
| A(3a+2, c−a+1) || c ≥ a, a ≡ 1, c ≡ 1 (mod 2) || 3a2+5c+6
|}

== Large-scale behavior ==

Consider the behavior of this machine starting at A(0, 1). If we start a new line every time rule (h) is applied, we find that it follows ''chains'' of steps, each starting from a config of form A(1, ''c''):

A(0,1)
-h> '''A(1,3)''' -j> A(5,3) -e> A(17,1) -b> A(14,5)
-b> A(7,11) -j> A(23,5) -b> A(16,11) -c> A(1,23)
-j> A(5,23) -j> A(17,19) -j> A(53,3) -c> A(46,11)
-c> A(31,23) -c> A(4,41)
-h> '''A(1,45)''' -j> A(5,45) -j> A(17,41) -j> A(53,25)
-b> A(26,41)
-h> '''A(1,56)''' -i> A(3,59) -j> A(11,57) -j> A(35,47)
-j> A(107,13) -b> A(92,23) -c> A(65,41) -b> A(22,65)
-h> '''A(1,78)''' -i> A(3,81) -j> A(11,79) -j> A(35,69)
-j> A(107,35) -c> A(68,59) -c> A(5,95) -j> A(17,91)
-j> A(53,75) -j> A(161,23) -c> A(134,41) -b> A(91,65)
-b> A(24,101)
-h> '''A(1,115)''' -j> A(5,115) -j> A(17,111) -j> A(53,95)
-j> A(161,43) -c> A(114,71) -c> A(39,113) -j> A(119,75)
-c> A(40,119)
-h> '''A(1,141)''' -j> A(5,141) -j> A(17,137) -j> A(53,121)
-j> A(161,69) -b> A(90,107)
-h> '''A(1,154)''' -i> ...

If we look at the sequence of applied rule labels, we can see the overall structure of these chains:

A(0,1) h
A(1,3) jebbjbcjjjccch
A(1,45) jjjbh
A(1,56) ijjjbcbh
A(1,78) ijjjccjjjcbbh
A(1,115) jjjjccjch
A(1,141) jjjjbh
A(1,154) ijjjjbccbbbjch
A(1,194) ijjjjbcbh
A(1,218) ijjjjbcjccbcjbcbbjjjcbjcbch
A(1,298) ijjjjbh
A(1,315) jjjjjccch
A(1,341) jjjjjbcjcbbbjch
A(1,381) jjjjjbcjbh
A(1,405) jjjjjbcjjbh
A(1,431) jjjjjch
A(1,448) ijjjjch
A(1,467) jjjjjch
A(1,484) ijjjjjbcbbbcch
A(1,524) ijjjjjbcccch
A(1,561) jjjjjbh
A(1,576) ijjjjjbbbcjjcbjjbcjbbjch
A(1,640) ijjjjjbbbh
A(1,664) ijjjjjbbch
A(1,690) ijjjjjccjbccbjccch

Following a possible (i) and an initial run of (j), the chain alternates between runs of (b)/(c) and runs of (j). Each run of (b)/(c) is of even length, except for the final run which is of odd length. Starting from A(1, ''c''), the length of the initial run of (j) approaches (log3 ''c'' − 1). Rules (d), (f), and (h) can only occur after an odd-length run of (b)/(c), while rule (e) can only occur after an even-length run.

[[File:758 chain lengths.png|thumb|400px|right|alt=A 2D plot of blue and orange points. The values are organized into branching trees of intervals that become progressively smaller until they turn into scattered clouds of points.|Chain lengths starting at A(1, ''c'') configs. Blue points correspond to ''c'' odd, orange points to ''c'' even. The log scale for ''c'' illustrates the recursive structure.]]

Notice how in the sequence of A(1, ''c'') configs, the next ''c'' value is always greater than the previous ''c'' value, but not extraordinarily greater. In fact, the difference Δ''c'' over the course of a chain is roughly proportional to the length of the chain. We can see this if we reparameterize the rules in terms of ''t'' = ''a''+2''c'' and ''d'' = (''c''−1)/2, with the invariant that 0 ≤ ''d'' ≤ (''t''−2)/4 at all times (<code>T(t,d) = A(t-4d-2, 2d+1))</code>:

{| class="wikitable" style="text-align:left"
|+ Rules for T(t, d)
! !! style="text-align:left" | T(t, d) → !! Conditions
|-
! style="text-align:right" | (b)
| T(t+5, 3d/2+2) || 6d ≤ t−5, d ≡ 0 (mod 2)
|-
! style="text-align:right" | (c)
| T(t+9, 3(d−1)/2+5) || 6d ≤ t−7, d ≡ 1 (mod 2)
|-
! style="text-align:right" | (d)
| Halt(3d+7) || 6d = t−6, d ≡ 1 (mod 2)
|-
! style="text-align:right" | (e)
| T(t+8, 0) || 6d = t−5, d ≡ 1 (mod 2)
|-
! style="text-align:right" | (f)
| Halt(3d+4) || 6d = t−4
|-
! style="text-align:right" | (h)
| T(t+5, (t−2)/4+1) || 6d ≥ t−2, t ≡ 2 (mod 4)
|-
! style="text-align:right" | (hi)
| T(t+13, t/4+2) || 6d ≥ t−2, t ≡ 0 (mod 4)
|-
! style="text-align:right" | (j)
| T(t+4, 3d−(t−1)/2+1) || 6d ≥ t−3, t ≡ 1 (mod 2)
|}

In this form, each step increases ''t'' by a small positive value, so this explains why Δ''c'' between A(1, ''c'') configs depends on the number of steps in the chain.

What determines the number of steps in the chain? As the plot shows, the chain lengths follow a sort of fractal pattern depending on the magnitude of ''c''. To derive this pattern, we first start with our T(''t'', ''d'') parameterization, combine steps so that ''t'' is always odd, and let ''u'' = (''t''−1)/2, so that 0 ≤ ''d'' ≤ (''u''−1)/2. Looking at rules (b), (c), and (j), we find (<code>U(u,d) = T(2u+1, d))</code>:

{| class="wikitable" style="text-align:left"
|+ Rules for U(u, d)
! !! style="text-align:left" | U(u, d) → !! Conditions
|-
! style="text-align:right" | (bb)
| U(u+5, (9d+20)/4) || 0 ≤ d ≤ (2u−12)/9, d ≡ 0 (mod 4)
|-
! style="text-align:right" | (cc)
| U(u+9, (9d+35)/4) || 0 ≤ d ≤ (2u−19)/9, d ≡ 1 (mod 4)
|-
! style="text-align:right" | (bc)
| U(u+7, (9d+26)/4) || 0 ≤ d ≤ (2u−12)/9, d ≡ 2 (mod 4)
|-
! style="text-align:right" | (cb)
| U(u+7, (9d+29)/4) || 0 ≤ d ≤ (2u−17)/9, d ≡ 3 (mod 4)
|-
! style="text-align:right" | (j)
| U(u+2, 3d−u+1) || (u−1)/3 ≤ d ≤ (u−1)/2
|}

[[File:758 fractal.png|thumb|400px|right|alt=A fractal pattern similar to the ternary Cantor set. A single line appears at the top, followed by 2 shorter lines below it, followed by 4 even shorter lines below those, and so on recursively.|The fractal pattern followed by rules (b), (c), (j). The depth of a given point corresponds to the number of steps before hitting rule (h).]]

Broadly, it maps ''d'' → 9''d''/4 when 0 < ''d'' < 2''u''/9; hits rule (h) and resets when 2''u''/9 < ''d'' < ''u''/3; and maps ''d'' → 3''d''−''u'' when ''u''/3 < ''d'' < ''u''/2. These three subcases form an [[wikipedia:iterated function system|iterated function system]] describing a fractal pattern analogous to the ternary Cantor set. The machine checks which interval the ratio 2''d''/''u'' lies in: if it lies in the middle interval, rule (h) applies, but if it lies in the left or right interval, rules (b), (c), (j) expand its position within that interval, then recursively repeat the check. Similarly to the Cantor set, the fractal has Lebesgue measure 0, so almost all initial points should eventually hit rule (h). As a corollary, the number of steps after the initial (j) run should follow a geometric distribution, so the expected chain length should approach log3 ''c'' plus a constant.

The machine halts if the chain ends at rules (d) or (f), which reside at the right edge of the left intervals within the fractal. Certain configs A(1, ''c'') hit one of these rules before hitting rule (h), and these values of ''c'' are called ''halting values''. The first few halting values are:

A(1,12) -> Halt(40) via ijjccjcd
A(1,14) -> Halt(40) via ijjbcjcd
A(1,71) -> Halt(100) via jjjebbccbf
A(1,73) -> Halt(100) via jjjjbbccbf
A(1,131) -> Halt(148) via jjjjcd
A(1,133) -> Halt(148) via jjjjbd
A(1,2331) -> Halt(2377) via jjjjjjjcbccccjbf
A(1,2333) -> Halt(2377) via jjjjjjjbbccccjbf
A(1,2583) -> Halt(2620) via jjjjjjjccbcjbf
A(1,2585) -> Halt(2620) via jjjjjjjbcbcjbf

As a rule, halting values always come in pairs with a difference of 2, except in the unlikely case that a chain hits rule (e) before halting. They are common for small values of ''c'', but soon become exponentially rare. In fact, there only exist 64 total halting values up to ''c'' = 3.4×1015, and the first 58 are known not to be reached by the forward iteration.

<div class="toccolours mw-collapsible mw-collapsed">'''First 64 halting values'''<div class="mw-collapsible-content"><pre style="overflow:scroll;white-space:pre">
1. A(1,12) -> Halt(40) via ijjccjcd
2. A(1,14) -> Halt(40) via ijjbcjcd
3. A(1,71) -> Halt(100) via jjjebbccbf
4. A(1,73) -> Halt(100) via jjjjbbccbf
5. A(1,131) -> Halt(148) via jjjjcd
6. A(1,133) -> Halt(148) via jjjjbd
7. A(1,2331) -> Halt(2377) via jjjjjjjcbccccjbf
8. A(1,2333) -> Halt(2377) via jjjjjjjbbccccjbf
9. A(1,2583) -> Halt(2620) via jjjjjjjccbcjbf
10. A(1,2585) -> Halt(2620) via jjjjjjjbcbcjbf
11. A(1,3195) -> Halt(3241) via jjjjjjjcbjbbccjcf
12. A(1,3197) -> Halt(3241) via jjjjjjjbbjbbccjcf
13. A(1,6306) -> Halt(6358) via ijjjjjjjcbjcccbcd
14. A(1,6308) -> Halt(6358) via ijjjjjjjbbjcccbcd
15. A(1,7167) -> Halt(7204) via jjjjjjjjcbcbbd
16. A(1,7169) -> Halt(7204) via jjjjjjjjbbcbbd
17. A(1,11787) -> Halt(11812) via jjjjjjjjcd
18. A(1,11789) -> Halt(11812) via jjjjjjjjbd
19. A(1,13624) -> Halt(13672) via ijjjjjjjjccbbbccf
20. A(1,13626) -> Halt(13672) via ijjjjjjjjbcbbbccf
21. A(1,43122) -> Halt(43165) via ijjjjjjjjjcccbbf
22. A(1,43124) -> Halt(43165) via ijjjjjjjjjbccbbf
23. A(1,905235) -> Halt(905284) via jjjjjjjjjjjjccjjbbjbf
24. A(1,905237) -> Halt(905284) via jjjjjjjjjjjjbcjjbbjbf
25. A(1,956563) -> Halt(956596) via jjjjjjjjjjjjcd
26. A(1,956565) -> Halt(956596) via jjjjjjjjjjjjbd
27. A(1,1712679) -> Halt(1712746) via jjjjjjjjjjjjjcbcbbcjccjcf
28. A(1,1712681) -> Halt(1712746) via jjjjjjjjjjjjjbbcbbcjccjcf
29. A(1,49818027) -> Halt(49818118) via jjjjjjjjjjjjjjjjccbbjbcccccjcbcd
30. A(1,49818029) -> Halt(49818118) via jjjjjjjjjjjjjjjjbcbbjbcccccjcbcd
31. A(1,77484059) -> Halt(77484100) via jjjjjjjjjjjjjjjjcd
32. A(1,77484061) -> Halt(77484100) via jjjjjjjjjjjjjjjjbd
33. A(1,106744976) -> Halt(106745041) via ijjjjjjjjjjjjjjjjccccjjjbf
34. A(1,106744978) -> Halt(106745041) via ijjjjjjjjjjjjjjjjbcccjjjbf
35. A(1,659939159) -> Halt(659939224) via jjjjjjjjjjjjjjjjjjccjjcbjbd
36. A(1,659939161) -> Halt(659939224) via jjjjjjjjjjjjjjjjjjbcjjcbjbd
37. A(1,3822354579) -> Halt(3822354640) via jjjjjjjjjjjjjjjjjjjjccbbcf
38. A(1,3822354581) -> Halt(3822354640) via jjjjjjjjjjjjjjjjjjjjbcbbcf
39. A(1,6276211875) -> Halt(6276211924) via jjjjjjjjjjjjjjjjjjjjcd
40. A(1,6276211877) -> Halt(6276211924) via jjjjjjjjjjjjjjjjjjjjbd
41. A(1,16380092275) -> Halt(16380092362) via jjjjjjjjjjjjjjjjjjjjjccjcbjjjjbbbbcd
42. A(1,16380092277) -> Halt(16380092362) via jjjjjjjjjjjjjjjjjjjjjbcjcbjjjjbbbbcd
43. A(1,404671372119) -> Halt(404671372210) via jjjjjjjjjjjjjjjjjjjjjjjjcbjcccccccf
44. A(1,404671372121) -> Halt(404671372210) via jjjjjjjjjjjjjjjjjjjjjjjjbbjcccccccf
45. A(1,508373165611) -> Halt(508373165668) via jjjjjjjjjjjjjjjjjjjjjjjjcd
46. A(1,508373165613) -> Halt(508373165668) via jjjjjjjjjjjjjjjjjjjjjjjjbd
47. A(1,3957690125931) -> Halt(3957690126046) via jjjjjjjjjjjjjjjjjjjjjjjjjjcbjcbjjccjjcbbbbcjcd
48. A(1,3957690125933) -> Halt(3957690126046) via jjjjjjjjjjjjjjjjjjjjjjjjjjbbjcbjjccjjcbbbbcjcd
49. A(1,4444131579443) -> Halt(4444131579553) via jjjjjjjjjjjjjjjjjjjjjjjjjjcbjjjbbbcbbbbccbccf
50. A(1,4444131579445) -> Halt(4444131579553) via jjjjjjjjjjjjjjjjjjjjjjjjjjbbjjjbbbcbbbbccbccf
51. A(1,8359489573703) -> Halt(8359489573780) via jjjjjjjjjjjjjjjjjjjjjjjjjjjcccbbd
52. A(1,8359489573705) -> Halt(8359489573780) via jjjjjjjjjjjjjjjjjjjjjjjjjjjbccbbd
53. A(1,26358811020231) -> Halt(26358811020352) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjcbcbjcbcbbccbbcbcjbf
54. A(1,26358811020233) -> Halt(26358811020352) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjbbcbjcbcbbccbbcbcjbf
55. A(1,41178226418867) -> Halt(41178226418932) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjcd
56. A(1,41178226418869) -> Halt(41178226418932) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjbd
57. A(1,81795441578679) -> Halt(81795441578764) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjjcbccjcd
58. A(1,81795441578681) -> Halt(81795441578764) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjjbbccjcd
59. A(1,1326438094216110) -> Halt(1326438094216285) via ijjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjccbcbbjccjcbjcbjccbbcccccccccf
60. A(1,1326438094216112) -> Halt(1326438094216285) via ijjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjbcbcbbjccjcbjcbjccbbcccccccccf
61. A(1,2031355966425479) -> Halt(2031355966425562) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjcbbcbf
62. A(1,2031355966425481) -> Halt(2031355966425562) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjbbbcbf
63. A(1,3335436339933243) -> Halt(3335436339933316) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjcd
64. A(1,3335436339933245) -> Halt(3335436339933316) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjbd
</pre></div></div>

To determine which halting ''c'' values should get reached by the forward iteration, we can employ a form of backward reasoning. By the nature of this machine, Δ''c'' depends on both the initial (j) run length and the chain length following the run. For longer chains, the length is effectively pseudorandom, so any two sequences of A(1, ''c'') values should eventually hit each other, after which they will have the same values.

If we can find a sufficiently long stretch of consecutive A(1, ''c'') configs that all reach the same halting value, we know that any sequence that reaches that stretch will halt. Conversely, if we find a sufficiently long stretch of A(1, ''c'') configs that skip past a halting value, we know that any sequence that reaches that stretch will skip past the halting value. In the first case, we say that the halting value ''explodes'' in terms of how many A(1, ''c'') configs can reach it; in the second case, we say that the halting value ''dies out''.

The first and currently only known halting value that does not die out is ''H'' = (3307−8282708212)/13959275. It it reachable from a very long stretch of consecutive A(1, ''c'') configs up to ''c'' ≤ ''H''−3,403,055. The lower bound of this stretch is not known, but it goes at least to H-8,000,000 ≤ c thus this stretch is well over 4 million long. Thus, assuming the forward iteration reaches this very long stretch, it will halt at A(1, ''H''), unless it has already reached some earlier halting value.

However, we cannot prove that the forward iteration reaches this long stretch instead of skipping past it. Statistically, the expectation is that Δ''c'' = log3 ''c'' + O(1), but we cannot place any easy bound on how long the chain can become: in principle, there could be an undiscovered A(1, ''c'') config that goes on for 101000 steps or more. So if we want to fully prove that this machine halts at or before A(1, ''H''), we must place an upper bound on Δ''c'' for every step leading up to it. But given the size of ''H'', there is no known practical method to compute such an upper bound.

== Equivalence to 1RB0LB0RC_2LC2LA1RA_1RA1LC--- ==
{{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}, #153, eventually becomes equivalent to this machine. As found by [https://discord.com/channels/960643023006490684/1259770474897080380/1260244842999709726 @Legion], after running the #153 machine for 1,790,901 steps, if one permutes the states A,C, and B and exchanges 1 for 2 and L for R, it has the same configuration as TM #758 after it has run 1,841,608 steps.

== History ==
LegionMammal's rough timeline of this TM on 30 Apr 2025 ([https://discord.com/channels/960643023006490684/1259770474897080380/1367340727859679322 Discord link]):

# The machine (and its sibling) passed straight through various rounds of cleverly-written deciders
# dyuan posted his set of rules and looked into it a bit, Justin noted that he'd briefly looked at it some time back
# Shawn and savask wrote up some acceleration schemes, found empirical evidence that it repeatedly comes close to halting, and speculated that it might actually halt after some period of time
# I took a crack at it myself, this time in terms of chains starting from <code>A(1,c)</code> configs, found some <code>c</code> values leading to a halt (showing that there's no obvious structural barrier), and conjectured some heuristics for how long it should take to reach such a halting <code>c</code> value
# dyuan and I nailed down the ideas of 'halter families' (collections of infinitely many halting <code>c</code> values so we don't have to brute-force them) and 'reachability analysis' (obtaining a strong probvious guess of whether a <code>c</code> value will or won't occur in the machine's actual forward behavior, assuming it hasn't halted beforehand)
# dyuan and I raced to find a halting <code>c</code> value that 'explodes' (passes the reachability analysis), first within the 'trivial' halter family to no avail, then within all halter families (writing a program to enumerate halter families is extremely fiddly, at this point I treat some of my own code as a black box not to be touched)
# By dint of a somewhat more performant program, I found (and dyuan confirmed) the <math>c = \frac{3^{307}-8\,282\,708\,212}{13\,959\,275}</math> we all know and love, probviously sealing the machine's fate

== savask's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254085725138190336

Let <code>(m, b, n) = A2(m, b, n) = 0^inf 1 2^m <A2 (22)^b (20)^n 0^inf</code>

<pre>
(0, b, n) -> (2b+2, 1, n) if n is even
-> (2b, 1, n+3) if n is odd

(1, b, 0) -> Halt

(2, b, 0) -> (0, b+3, 0) if b is even
-> (0, 1, b+5) if b is odd

(m, b, 0) -> (m-2, b+3, 0) if b is even
-> (m-3, 1, b+3) if b is odd

(1, b, n) -> (0, 1, n+b+2) if n is even
-> Halt if n is odd

(2, b, 1) -> Halt if b is even
-> (0, 1, b+5) if b is odd

(m, b, 1) -> (m-3, 1, b+3)

(m, b, n) -> (m-2, b+3, n-2)
</pre>

https://discord.com/channels/960643023006490684/1084047886494470185/1254306301786198116

<pre>
step (A2 0 b n) | even n = A2 (2*b+2) 1 n
| otherwise = A2 (2*b) 1 (n+3)
-- From now on m > 0
step (A2 1 b 0) = error $ "Halt A2 1 " ++ show b ++ " 0"
step (A2 2 b 0) | even b = A2 0 (b+3) 0
| otherwise = A2 0 1 (b+5)
step (A2 m b 0) | even b = A2 (m-2) (b+3) 0
| otherwise = A2 (m-3) 1 (b+3)
-- From now on n > 0
step (A2 1 b n) | even n = A2 0 1 (n+b+2)
| otherwise = error $ "Halt A2 1 " ++ show b ++ " " ++ show n
step (A2 2 b 1) | even b = error $ "Halt A2 2 " ++ show b ++ " 1"
| otherwise = A2 0 1 (b+5)
step (A2 m b 1) = A2 (m-3) 1 (b+3)
-- Here m > 1, n > 1
step (A2 m b n) = let d2 = (min m n) `div` 2 in A2 (m - 2*d2) (b + 3*d2) (n - 2*d2) -- Accelerated
</pre>

== Shawn's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254307091863048264

We can reduce the set of rules from savask's list a bit by noticing that we can evaluate so that all rules end with c even:

<pre>
(0, b, 2c) -> (2b+2, 1, 2c)

(1, b, 0) -> Halt
(1, 2b, 2c) -> (0, 1, 2(b+c+1))
(1, 2b+1, 2c) -> (2, 1, 2(b+c+3))

(a, 2b, 0) -> (a-2, 2b+3, 0)
(2, 2b+1, 0) -> (0, 1, 2b+6)
(a, 2b+1, 0) -> (a-3, 1, 2b+4)

(a, b, c) -> (a-2, b+3, c-2)
</pre>

=== Phases ===
We can think of this going through two different phases. "Even Phase" (where <code>a</code> is even) and "Odd Phase" (where <code>a</code> is odd).

<pre>
Even Phase: a,c even:
(0, b, 2c) -> (2b+2, 1, 2c)
(2a+2, 2b, 0) -> (2a, 2b+3, 0)
(2, 2b+1, 0) -> (0, 1, 2(b+3))

To Odd Phase:
(2a+4, 2b+1, 0) -> (2a+1, 1, 2b+4)

Odd Phase: a odd, c even
To Halt:
(1, b, 0) -> Halt
(3, 2b, 0) -> (1, 2b+3, 0) -> Halt

To Even Phase:
(1, 2b, 2c+2) -> (0, 1, 2(b+c+2))
(1, 2b+1, 2c+2) -> (0, 1, 2b+2c+5) -> (2, 1, 2(b+c+4))

(2a+5, 2b, 0) -> (2a+3, 2b+3, 0) -> (2a, 1, 2b+6)
(2a+3, 2b+1, 0) -> (2a, 1, 2b+4)
</pre>

So the only way for this to halt is if it is in "Even Phase" and hits (2k+8, 2k+1, 0) or (4k+12, 4k+3, 0) (which will lead to (1, b, 0) or (3, 2b, 0) eventually).
If <code>a</code> is bigger or smaller, then "Odd Phase" will end going back to "Even Phase" again.

=== Repeated (0, b, 2c) ===

Let <math>f(n) = 3n+4</math>, then<math display="block">(0, b, 2c) \to (0, f(b), 2(c - b - 1))</math> Let<math display="block">h(n) = f^n(1) + 1 = 3^{n+1} - 1</math><math display="block">g(n) = \sum_{k=0}^{n-1} h(k) = \frac{3}{2} (3^n - 1) - n</math>

Then if <math>c > g(n)</math>:<math display="block">(0, 1, 2c) \to (0, f^n(1), 2 (c-g(n))) \to (2 h(n), 1, 2 (c-g(n)))</math>

=== Repeated (0, 1, 2c) ===
https://discord.com/channels/960643023006490684/1084047886494470185/1254635277020954705

Let <math>C(n) = (0, 1, 2n)</math> = <code>0^inf 1 <A2 22 (20)^2n 0^inf</code>

<math display="block">C(g(n) + 8k+1) \to C(g(n) + 8k+1 + n+9)</math><math display="block">\forall k: \frac{h(n) - 45}{65} < k < \frac{h(n) - 22}{38}</math>

Notably, when 8 divides (n+1) then this rule can potentially be applied repeatedly.

Ex: if n = 7, then we get:<math display="block">\forall k \in [101, 172]: C(3273 + 8k) \to C(3273 + 8(k+2))</math>

And we see this starting with <math>C(4137) = C(3273 + 8 \cdot 108)</math> which repeats this rule until we get to <math>C(4665) = C(3273 + 8 \cdot 174)</math>.

And as n gets way bigger, these ranges of repeat will increase exponentially.

== References ==

[[Category:BB(3,3)]][[Category:Potential Cryptids]]

1RB2LC1RC 2LC---2RB 2LA0LB0RA

2026-11-06T15:14:35Z

Hipparcos: add probvious rough estimated halt time

{{machine|1RB2LC1RC_2LC---2RB_2LA0LB0RA}} {{unsolved|Does this TM halt? If so, how many steps does it take to halt?}}
{{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}} is a [[BB(3,3)]] [[holdout]] which appears to [[probviously]] halt. If it can be proven to halt, it will be the BB(3,3) champion in terms of both steps and tape symbols. However, it could also turn out to be a probviously halting [[Cryptid]].

This is holdout #758 on Justin's 3x3 mugshots. After about 1.8 million steps and up to some relabelling, it is equivalent to holdout #153: {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}. And if you start in state C it is a [[permutation]] of the same machine. Together, they simulate a complex set of [[Collatz-like]] rules with two decreasing parameters.

After active exploration on the #bb3x3 channel by LegionMammal and dyuan, LegionMammal found (and dyuan confirmed) a configuration A(1,c) (defined [https://discord.com/channels/960643023006490684/1259770474897080380/1259968221218607145 here]) which halts and for which a huge "wall" of previous A(1, c') values all reach it. This gives strong evidence that the TM probviously halts since jumping over this wall is very "unlikely". If this TM does in fact halt at that configuration, it is estimated to do so in roughly 2 × 10410 steps.<ref>https://discord.com/channels/960643023006490684/1259770474897080380/1568116988470108261</ref>

The TM has been simulated for over 1027 steps<ref>https://discord.com/channels/960643023006490684/1259770474897080380/1324065684677988505</ref>, reaching A(1, 1059491543272883(~1e15)).<ref>https://discord.com/channels/960643023006490684/1259770474897080380/1390819028137803829</ref>

== dyuan01's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1224457633176486041

<pre>
A_1(a, b, c) = 0^inf 1 2^a <C (22)^b (20)^c 0^inf
A_2(a, b, c) = 0^inf 1 2^a <A2 (22)^b (20)^c 0^inf
B(a, b) = 0^inf 1 2^a <B0 (20)^b 0^inf
</pre>

{| class="wikitable"
! From !! To
|-
| A1(0, b, 2n) || A2(1, b+2n+1, 0)
|-
| A1(0, b, 2n+1) || A1(1, 0, b+2n+3)
|-
| A1(m+1, b, 0) || A1(m, 0, b+2)
|-
| A1(m+1, b, n+1) || A2(m, b+1, n)
|-
| A2(0, b, 2n) || A1(2b+3, 0, 2n+1)
|-
| A2(0, b, 2n+1) || A2(2b+3, 2n+1, 0)
|-
| A2(m+1, b, 0) || B(m, b+2)
|-
| A2(m+1, b, n+1) || A1(m, b+2, n)
|-
| B(0, b) || Halt
|-
| B(m+1, 2n) || A2(m, 2n+1, 0)
|-
| B(m+1, 2n+1) || A1(m, 0, 2n+3)
|}
Starting from A1(0, 0, 1) (at step 2).

== A(a, c) Rules and Timings ==

Let A(a, c) = A1(a, 0, c) = <code>0^∞ 1 2^a <C (20)^c 0^∞</code>, where A1(a, b, c) comes from dyuan01's rules. Then the TM satisfies the following rules once it reaches A(0, 1) after 2 steps. Note that rules (a) and (g) aren't actually reachable from the initial condition.

{| class="wikitable" style="text-align:left"
|+ Rules and associated step counts ([https://discord.com/channels/960643023006490684/1259770474897080380/1324065684677988505 source])
! !! style="text-align:left" | A(a, c) → !! Conditions !! Step count
|-
! style="text-align:right" | (a)
| A(a−c−1, 3c/2+2) || c ≤ a−1, c ≡ 0 (mod 2) || 3c2+8c+5
|-
! style="text-align:right" | (b)
| A(a−c−2, 3(c−1)/2+5) || c ≤ a−2, c ≡ 1 (mod 4) || (6c2+31c+37)/2
|-
! style="text-align:right" | (c)
| A(a−c−4, 3(c−1)/2+8) || c ≤ a−4, c ≡ 3 (mod 4) || 3c2+29c+65
|-
! style="text-align:right" | (d)
| Halt(3(c−1)/2+7) || c = a−3, c ≡ 3 (mod 4) || (6c2+43c+75)/2
|-
! style="text-align:right" | (e)
| A(3c+8, 1) || c = a−2, c ≡ 3 (mod 4) || (6c2+37c+63)/2
|-
! style="text-align:right" | (f)
| Halt(3(c−1)/2+4) || c = a−1, c ≡ 1 (mod 2) || 3c2+8c+6
|-
! style="text-align:right" | (g)
| Halt(a/2+c+4) || c ≥ a, a ≡ 0, c ≡ 0 (mod 2) || 3a2+5a+9c+24
|-
! style="text-align:right" | (h)
| A(1, a/2+c+2) || c ≥ a, a ≡ 0, c ≡ 1 (mod 2) || 3a2+3a+5c+11
|-
! style="text-align:right" | (i)
| A(3a, c−a+4) || c ≥ a, a ≡ 1, c ≡ 0 (mod 2) || 3a2−9a+14c+30
|-
! style="text-align:right" | (j)
| A(3a+2, c−a+1) || c ≥ a, a ≡ 1, c ≡ 1 (mod 2) || 3a2+5c+6
|}

== Large-scale behavior ==

Consider the behavior of this machine starting at A(0, 1). If we start a new line every time rule (h) is applied, we find that it follows ''chains'' of steps, each starting from a config of form A(1, ''c''):

A(0,1)
-h> '''A(1,3)''' -j> A(5,3) -e> A(17,1) -b> A(14,5)
-b> A(7,11) -j> A(23,5) -b> A(16,11) -c> A(1,23)
-j> A(5,23) -j> A(17,19) -j> A(53,3) -c> A(46,11)
-c> A(31,23) -c> A(4,41)
-h> '''A(1,45)''' -j> A(5,45) -j> A(17,41) -j> A(53,25)
-b> A(26,41)
-h> '''A(1,56)''' -i> A(3,59) -j> A(11,57) -j> A(35,47)
-j> A(107,13) -b> A(92,23) -c> A(65,41) -b> A(22,65)
-h> '''A(1,78)''' -i> A(3,81) -j> A(11,79) -j> A(35,69)
-j> A(107,35) -c> A(68,59) -c> A(5,95) -j> A(17,91)
-j> A(53,75) -j> A(161,23) -c> A(134,41) -b> A(91,65)
-b> A(24,101)
-h> '''A(1,115)''' -j> A(5,115) -j> A(17,111) -j> A(53,95)
-j> A(161,43) -c> A(114,71) -c> A(39,113) -j> A(119,75)
-c> A(40,119)
-h> '''A(1,141)''' -j> A(5,141) -j> A(17,137) -j> A(53,121)
-j> A(161,69) -b> A(90,107)
-h> '''A(1,154)''' -i> ...

If we look at the sequence of applied rule labels, we can see the overall structure of these chains:

A(0,1) h
A(1,3) jebbjbcjjjccch
A(1,45) jjjbh
A(1,56) ijjjbcbh
A(1,78) ijjjccjjjcbbh
A(1,115) jjjjccjch
A(1,141) jjjjbh
A(1,154) ijjjjbccbbbjch
A(1,194) ijjjjbcbh
A(1,218) ijjjjbcjccbcjbcbbjjjcbjcbch
A(1,298) ijjjjbh
A(1,315) jjjjjccch
A(1,341) jjjjjbcjcbbbjch
A(1,381) jjjjjbcjbh
A(1,405) jjjjjbcjjbh
A(1,431) jjjjjch
A(1,448) ijjjjch
A(1,467) jjjjjch
A(1,484) ijjjjjbcbbbcch
A(1,524) ijjjjjbcccch
A(1,561) jjjjjbh
A(1,576) ijjjjjbbbcjjcbjjbcjbbjch
A(1,640) ijjjjjbbbh
A(1,664) ijjjjjbbch
A(1,690) ijjjjjccjbccbjccch

Following a possible (i) and an initial run of (j), the chain alternates between runs of (b)/(c) and runs of (j). Each run of (b)/(c) is of even length, except for the final run which is of odd length. Starting from A(1, ''c''), the length of the initial run of (j) approaches (log3 ''c'' − 1). Rules (d), (f), and (h) can only occur after an odd-length run of (b)/(c), while rule (e) can only occur after an even-length run.

[[File:758 chain lengths.png|thumb|400px|right|alt=A 2D plot of blue and orange points. The values are organized into branching trees of intervals that become progressively smaller until they turn into scattered clouds of points.|Chain lengths starting at A(1, ''c'') configs. Blue points correspond to ''c'' odd, orange points to ''c'' even. The log scale for ''c'' illustrates the recursive structure.]]

Notice how in the sequence of A(1, ''c'') configs, the next ''c'' value is always greater than the previous ''c'' value, but not extraordinarily greater. In fact, the difference Δ''c'' over the course of a chain is roughly proportional to the length of the chain. We can see this if we reparameterize the rules in terms of ''t'' = ''a''+2''c'' and ''d'' = (''c''−1)/2, with the invariant that 0 ≤ ''d'' ≤ (''t''−2)/4 at all times (<code>T(t,d) = A(t-4d-2, 2d+1))</code>:

{| class="wikitable" style="text-align:left"
|+ Rules for T(t, d)
! !! style="text-align:left" | T(t, d) → !! Conditions
|-
! style="text-align:right" | (b)
| T(t+5, 3d/2+2) || 6d ≤ t−5, d ≡ 0 (mod 2)
|-
! style="text-align:right" | (c)
| T(t+9, 3(d−1)/2+5) || 6d ≤ t−7, d ≡ 1 (mod 2)
|-
! style="text-align:right" | (d)
| Halt(3d+7) || 6d = t−6, d ≡ 1 (mod 2)
|-
! style="text-align:right" | (e)
| T(t+8, 0) || 6d = t−5, d ≡ 1 (mod 2)
|-
! style="text-align:right" | (f)
| Halt(3d+4) || 6d = t−4
|-
! style="text-align:right" | (h)
| T(t+5, (t−2)/4+1) || 6d ≥ t−2, t ≡ 2 (mod 4)
|-
! style="text-align:right" | (hi)
| T(t+13, t/4+2) || 6d ≥ t−2, t ≡ 0 (mod 4)
|-
! style="text-align:right" | (j)
| T(t+4, 3d−(t−1)/2+1) || 6d ≥ t−3, t ≡ 1 (mod 2)
|}

In this form, each step increases ''t'' by a small positive value, so this explains why Δ''c'' between A(1, ''c'') configs depends on the number of steps in the chain.

What determines the number of steps in the chain? As the plot shows, the chain lengths follow a sort of fractal pattern depending on the magnitude of ''c''. To derive this pattern, we first start with our T(''t'', ''d'') parameterization, combine steps so that ''t'' is always odd, and let ''u'' = (''t''−1)/2, so that 0 ≤ ''d'' ≤ (''u''−1)/2. Looking at rules (b), (c), and (j), we find (<code>U(u,d) = T(2u+1, d))</code>:

{| class="wikitable" style="text-align:left"
|+ Rules for U(u, d)
! !! style="text-align:left" | U(u, d) → !! Conditions
|-
! style="text-align:right" | (bb)
| U(u+5, (9d+20)/4) || 0 ≤ d ≤ (2u−12)/9, d ≡ 0 (mod 4)
|-
! style="text-align:right" | (cc)
| U(u+9, (9d+35)/4) || 0 ≤ d ≤ (2u−19)/9, d ≡ 1 (mod 4)
|-
! style="text-align:right" | (bc)
| U(u+7, (9d+26)/4) || 0 ≤ d ≤ (2u−12)/9, d ≡ 2 (mod 4)
|-
! style="text-align:right" | (cb)
| U(u+7, (9d+29)/4) || 0 ≤ d ≤ (2u−17)/9, d ≡ 3 (mod 4)
|-
! style="text-align:right" | (j)
| U(u+2, 3d−u+1) || (u−1)/3 ≤ d ≤ (u−1)/2
|}

[[File:758 fractal.png|thumb|400px|right|alt=A fractal pattern similar to the ternary Cantor set. A single line appears at the top, followed by 2 shorter lines below it, followed by 4 even shorter lines below those, and so on recursively.|The fractal pattern followed by rules (b), (c), (j). The depth of a given point corresponds to the number of steps before hitting rule (h).]]

Broadly, it maps ''d'' → 9''d''/4 when 0 < ''d'' < 2''u''/9; hits rule (h) and resets when 2''u''/9 < ''d'' < ''u''/3; and maps ''d'' → 3''d''−''u'' when ''u''/3 < ''d'' < ''u''/2. These three subcases form an [[wikipedia:iterated function system|iterated function system]] describing a fractal pattern analogous to the ternary Cantor set. The machine checks which interval the ratio 2''d''/''u'' lies in: if it lies in the middle interval, rule (h) applies, but if it lies in the left or right interval, rules (b), (c), (j) expand its position within that interval, then recursively repeat the check. Similarly to the Cantor set, the fractal has Lebesgue measure 0, so almost all initial points should eventually hit rule (h). As a corollary, the number of steps after the initial (j) run should follow a geometric distribution, so the expected chain length should approach log3 ''c'' plus a constant.

The machine halts if the chain ends at rules (d) or (f), which reside at the right edge of the left intervals within the fractal. Certain configs A(1, ''c'') hit one of these rules before hitting rule (h), and these values of ''c'' are called ''halting values''. The first few halting values are:

A(1,12) -> Halt(40) via ijjccjcd
A(1,14) -> Halt(40) via ijjbcjcd
A(1,71) -> Halt(100) via jjjebbccbf
A(1,73) -> Halt(100) via jjjjbbccbf
A(1,131) -> Halt(148) via jjjjcd
A(1,133) -> Halt(148) via jjjjbd
A(1,2331) -> Halt(2377) via jjjjjjjcbccccjbf
A(1,2333) -> Halt(2377) via jjjjjjjbbccccjbf
A(1,2583) -> Halt(2620) via jjjjjjjccbcjbf
A(1,2585) -> Halt(2620) via jjjjjjjbcbcjbf

As a rule, halting values always come in pairs with a difference of 2, except in the unlikely case that a chain hits rule (e) before halting. They are common for small values of ''c'', but soon become exponentially rare. In fact, there only exist 64 total halting values up to ''c'' = 3.4×1015, and the first 58 are known not to be reached by the forward iteration.

<div class="toccolours mw-collapsible mw-collapsed">'''First 64 halting values'''<div class="mw-collapsible-content"><pre style="overflow:scroll;white-space:pre">
1. A(1,12) -> Halt(40) via ijjccjcd
2. A(1,14) -> Halt(40) via ijjbcjcd
3. A(1,71) -> Halt(100) via jjjebbccbf
4. A(1,73) -> Halt(100) via jjjjbbccbf
5. A(1,131) -> Halt(148) via jjjjcd
6. A(1,133) -> Halt(148) via jjjjbd
7. A(1,2331) -> Halt(2377) via jjjjjjjcbccccjbf
8. A(1,2333) -> Halt(2377) via jjjjjjjbbccccjbf
9. A(1,2583) -> Halt(2620) via jjjjjjjccbcjbf
10. A(1,2585) -> Halt(2620) via jjjjjjjbcbcjbf
11. A(1,3195) -> Halt(3241) via jjjjjjjcbjbbccjcf
12. A(1,3197) -> Halt(3241) via jjjjjjjbbjbbccjcf
13. A(1,6306) -> Halt(6358) via ijjjjjjjcbjcccbcd
14. A(1,6308) -> Halt(6358) via ijjjjjjjbbjcccbcd
15. A(1,7167) -> Halt(7204) via jjjjjjjjcbcbbd
16. A(1,7169) -> Halt(7204) via jjjjjjjjbbcbbd
17. A(1,11787) -> Halt(11812) via jjjjjjjjcd
18. A(1,11789) -> Halt(11812) via jjjjjjjjbd
19. A(1,13624) -> Halt(13672) via ijjjjjjjjccbbbccf
20. A(1,13626) -> Halt(13672) via ijjjjjjjjbcbbbccf
21. A(1,43122) -> Halt(43165) via ijjjjjjjjjcccbbf
22. A(1,43124) -> Halt(43165) via ijjjjjjjjjbccbbf
23. A(1,905235) -> Halt(905284) via jjjjjjjjjjjjccjjbbjbf
24. A(1,905237) -> Halt(905284) via jjjjjjjjjjjjbcjjbbjbf
25. A(1,956563) -> Halt(956596) via jjjjjjjjjjjjcd
26. A(1,956565) -> Halt(956596) via jjjjjjjjjjjjbd
27. A(1,1712679) -> Halt(1712746) via jjjjjjjjjjjjjcbcbbcjccjcf
28. A(1,1712681) -> Halt(1712746) via jjjjjjjjjjjjjbbcbbcjccjcf
29. A(1,49818027) -> Halt(49818118) via jjjjjjjjjjjjjjjjccbbjbcccccjcbcd
30. A(1,49818029) -> Halt(49818118) via jjjjjjjjjjjjjjjjbcbbjbcccccjcbcd
31. A(1,77484059) -> Halt(77484100) via jjjjjjjjjjjjjjjjcd
32. A(1,77484061) -> Halt(77484100) via jjjjjjjjjjjjjjjjbd
33. A(1,106744976) -> Halt(106745041) via ijjjjjjjjjjjjjjjjccccjjjbf
34. A(1,106744978) -> Halt(106745041) via ijjjjjjjjjjjjjjjjbcccjjjbf
35. A(1,659939159) -> Halt(659939224) via jjjjjjjjjjjjjjjjjjccjjcbjbd
36. A(1,659939161) -> Halt(659939224) via jjjjjjjjjjjjjjjjjjbcjjcbjbd
37. A(1,3822354579) -> Halt(3822354640) via jjjjjjjjjjjjjjjjjjjjccbbcf
38. A(1,3822354581) -> Halt(3822354640) via jjjjjjjjjjjjjjjjjjjjbcbbcf
39. A(1,6276211875) -> Halt(6276211924) via jjjjjjjjjjjjjjjjjjjjcd
40. A(1,6276211877) -> Halt(6276211924) via jjjjjjjjjjjjjjjjjjjjbd
41. A(1,16380092275) -> Halt(16380092362) via jjjjjjjjjjjjjjjjjjjjjccjcbjjjjbbbbcd
42. A(1,16380092277) -> Halt(16380092362) via jjjjjjjjjjjjjjjjjjjjjbcjcbjjjjbbbbcd
43. A(1,404671372119) -> Halt(404671372210) via jjjjjjjjjjjjjjjjjjjjjjjjcbjcccccccf
44. A(1,404671372121) -> Halt(404671372210) via jjjjjjjjjjjjjjjjjjjjjjjjbbjcccccccf
45. A(1,508373165611) -> Halt(508373165668) via jjjjjjjjjjjjjjjjjjjjjjjjcd
46. A(1,508373165613) -> Halt(508373165668) via jjjjjjjjjjjjjjjjjjjjjjjjbd
47. A(1,3957690125931) -> Halt(3957690126046) via jjjjjjjjjjjjjjjjjjjjjjjjjjcbjcbjjccjjcbbbbcjcd
48. A(1,3957690125933) -> Halt(3957690126046) via jjjjjjjjjjjjjjjjjjjjjjjjjjbbjcbjjccjjcbbbbcjcd
49. A(1,4444131579443) -> Halt(4444131579553) via jjjjjjjjjjjjjjjjjjjjjjjjjjcbjjjbbbcbbbbccbccf
50. A(1,4444131579445) -> Halt(4444131579553) via jjjjjjjjjjjjjjjjjjjjjjjjjjbbjjjbbbcbbbbccbccf
51. A(1,8359489573703) -> Halt(8359489573780) via jjjjjjjjjjjjjjjjjjjjjjjjjjjcccbbd
52. A(1,8359489573705) -> Halt(8359489573780) via jjjjjjjjjjjjjjjjjjjjjjjjjjjbccbbd
53. A(1,26358811020231) -> Halt(26358811020352) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjcbcbjcbcbbccbbcbcjbf
54. A(1,26358811020233) -> Halt(26358811020352) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjbbcbjcbcbbccbbcbcjbf
55. A(1,41178226418867) -> Halt(41178226418932) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjcd
56. A(1,41178226418869) -> Halt(41178226418932) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjbd
57. A(1,81795441578679) -> Halt(81795441578764) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjjcbccjcd
58. A(1,81795441578681) -> Halt(81795441578764) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjjbbccjcd
59. A(1,1326438094216110) -> Halt(1326438094216285) via ijjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjccbcbbjccjcbjcbjccbbcccccccccf
60. A(1,1326438094216112) -> Halt(1326438094216285) via ijjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjbcbcbbjccjcbjcbjccbbcccccccccf
61. A(1,2031355966425479) -> Halt(2031355966425562) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjcbbcbf
62. A(1,2031355966425481) -> Halt(2031355966425562) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjbbbcbf
63. A(1,3335436339933243) -> Halt(3335436339933316) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjcd
64. A(1,3335436339933245) -> Halt(3335436339933316) via jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjbd
</pre></div></div>

To determine which halting ''c'' values should get reached by the forward iteration, we can employ a form of backward reasoning. By the nature of this machine, Δ''c'' depends on both the initial (j) run length and the chain length following the run. For longer chains, the length is effectively pseudorandom, so any two sequences of A(1, ''c'') values should eventually hit each other, after which they will have the same values.

If we can find a sufficiently long stretch of consecutive A(1, ''c'') configs that all reach the same halting value, we know that any sequence that reaches that stretch will halt. Conversely, if we find a sufficiently long stretch of A(1, ''c'') configs that skip past a halting value, we know that any sequence that reaches that stretch will skip past the halting value. In the first case, we say that the halting value ''explodes'' in terms of how many A(1, ''c'') configs can reach it; in the second case, we say that the halting value ''dies out''.

The first and currently only known halting value that does not die out is ''H'' = (3307−8282708212)/13959275. It it reachable from a very long stretch of consecutive A(1, ''c'') configs up to ''c'' ≤ ''H''−3,403,055. The lower bound of this stretch is not known, but it goes at least to H-8,000,000 ≤ c thus this stretch is well over 4 million long. Thus, assuming the forward iteration reaches this very long stretch, it will halt at A(1, ''H''), unless it has already reached some earlier halting value.

However, we cannot prove that the forward iteration reaches this long stretch instead of skipping past it. Statistically, the expectation is that Δ''c'' = log3 ''c'' + O(1), but we cannot place any easy bound on how long the chain can become: in principle, there could be an undiscovered A(1, ''c'') config that goes on for 101000 steps or more. So if we want to fully prove that this machine halts at or before A(1, ''H''), we must place an upper bound on Δ''c'' for every step leading up to it. But given the size of ''H'', there is no known practical method to compute such an upper bound.

== Equivalence to 1RB0LB0RC_2LC2LA1RA_1RA1LC--- ==
{{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}, #153, eventually becomes equivalent to this machine. As found by [https://discord.com/channels/960643023006490684/1259770474897080380/1260244842999709726 @Legion], after running the #153 machine for 1,790,901 steps, if one permutes the states A,C, and B and exchanges 1 for 2 and L for R, it has the same configuration as TM #758 after it has run 1,841,608 steps.

== History ==
LegionMammal's rough timeline of this TM on 30 Apr 2025 ([https://discord.com/channels/960643023006490684/1259770474897080380/1367340727859679322 Discord link]):

# The machine (and its sibling) passed straight through various rounds of cleverly-written deciders
# dyuan posted his set of rules and looked into it a bit, Justin noted that he'd briefly looked at it some time back
# Shawn and savask wrote up some acceleration schemes, found empirical evidence that it repeatedly comes close to halting, and speculated that it might actually halt after some period of time
# I took a crack at it myself, this time in terms of chains starting from <code>A(1,c)</code> configs, found some <code>c</code> values leading to a halt (showing that there's no obvious structural barrier), and conjectured some heuristics for how long it should take to reach such a halting <code>c</code> value
# dyuan and I nailed down the ideas of 'halter families' (collections of infinitely many halting <code>c</code> values so we don't have to brute-force them) and 'reachability analysis' (obtaining a strong probvious guess of whether a <code>c</code> value will or won't occur in the machine's actual forward behavior, assuming it hasn't halted beforehand)
# dyuan and I raced to find a halting <code>c</code> value that 'explodes' (passes the reachability analysis), first within the 'trivial' halter family to no avail, then within all halter families (writing a program to enumerate halter families is extremely fiddly, at this point I treat some of my own code as a black box not to be touched)
# By dint of a somewhat more performant program, I found (and dyuan confirmed) the <math>c = \frac{3^{307}-8\,282\,708\,212}{13\,959\,275}</math> we all know and love, probviously sealing the machine's fate

== savask's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254085725138190336

Let <code>(m, b, n) = A2(m, b, n) = 0^inf 1 2^m <A2 (22)^b (20)^n 0^inf</code>

<pre>
(0, b, n) -> (2b+2, 1, n) if n is even
-> (2b, 1, n+3) if n is odd

(1, b, 0) -> Halt

(2, b, 0) -> (0, b+3, 0) if b is even
-> (0, 1, b+5) if b is odd

(m, b, 0) -> (m-2, b+3, 0) if b is even
-> (m-3, 1, b+3) if b is odd

(1, b, n) -> (0, 1, n+b+2) if n is even
-> Halt if n is odd

(2, b, 1) -> Halt if b is even
-> (0, 1, b+5) if b is odd

(m, b, 1) -> (m-3, 1, b+3)

(m, b, n) -> (m-2, b+3, n-2)
</pre>

https://discord.com/channels/960643023006490684/1084047886494470185/1254306301786198116

<pre>
step (A2 0 b n) | even n = A2 (2*b+2) 1 n
| otherwise = A2 (2*b) 1 (n+3)
-- From now on m > 0
step (A2 1 b 0) = error $ "Halt A2 1 " ++ show b ++ " 0"
step (A2 2 b 0) | even b = A2 0 (b+3) 0
| otherwise = A2 0 1 (b+5)
step (A2 m b 0) | even b = A2 (m-2) (b+3) 0
| otherwise = A2 (m-3) 1 (b+3)
-- From now on n > 0
step (A2 1 b n) | even n = A2 0 1 (n+b+2)
| otherwise = error $ "Halt A2 1 " ++ show b ++ " " ++ show n
step (A2 2 b 1) | even b = error $ "Halt A2 2 " ++ show b ++ " 1"
| otherwise = A2 0 1 (b+5)
step (A2 m b 1) = A2 (m-3) 1 (b+3)
-- Here m > 1, n > 1
step (A2 m b n) = let d2 = (min m n) `div` 2 in A2 (m - 2*d2) (b + 3*d2) (n - 2*d2) -- Accelerated
</pre>

== Shawn's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254307091863048264

We can reduce the set of rules from savask's list a bit by noticing that we can evaluate so that all rules end with c even:

<pre>
(0, b, 2c) -> (2b+2, 1, 2c)

(1, b, 0) -> Halt
(1, 2b, 2c) -> (0, 1, 2(b+c+1))
(1, 2b+1, 2c) -> (2, 1, 2(b+c+3))

(a, 2b, 0) -> (a-2, 2b+3, 0)
(2, 2b+1, 0) -> (0, 1, 2b+6)
(a, 2b+1, 0) -> (a-3, 1, 2b+4)

(a, b, c) -> (a-2, b+3, c-2)
</pre>

=== Phases ===
We can think of this going through two different phases. "Even Phase" (where <code>a</code> is even) and "Odd Phase" (where <code>a</code> is odd).

<pre>
Even Phase: a,c even:
(0, b, 2c) -> (2b+2, 1, 2c)
(2a+2, 2b, 0) -> (2a, 2b+3, 0)
(2, 2b+1, 0) -> (0, 1, 2(b+3))

To Odd Phase:
(2a+4, 2b+1, 0) -> (2a+1, 1, 2b+4)

Odd Phase: a odd, c even
To Halt:
(1, b, 0) -> Halt
(3, 2b, 0) -> (1, 2b+3, 0) -> Halt

To Even Phase:
(1, 2b, 2c+2) -> (0, 1, 2(b+c+2))
(1, 2b+1, 2c+2) -> (0, 1, 2b+2c+5) -> (2, 1, 2(b+c+4))

(2a+5, 2b, 0) -> (2a+3, 2b+3, 0) -> (2a, 1, 2b+6)
(2a+3, 2b+1, 0) -> (2a, 1, 2b+4)
</pre>

So the only way for this to halt is if it is in "Even Phase" and hits (2k+8, 2k+1, 0) or (4k+12, 4k+3, 0) (which will lead to (1, b, 0) or (3, 2b, 0) eventually).
If <code>a</code> is bigger or smaller, then "Odd Phase" will end going back to "Even Phase" again.

=== Repeated (0, b, 2c) ===

Let <math>f(n) = 3n+4</math>, then<math display="block">(0, b, 2c) \to (0, f(b), 2(c - b - 1))</math> Let<math display="block">h(n) = f^n(1) + 1 = 3^{n+1} - 1</math><math display="block">g(n) = \sum_{k=0}^{n-1} h(k) = \frac{3}{2} (3^n - 1) - n</math>

Then if <math>c > g(n)</math>:<math display="block">(0, 1, 2c) \to (0, f^n(1), 2 (c-g(n))) \to (2 h(n), 1, 2 (c-g(n)))</math>

=== Repeated (0, 1, 2c) ===
https://discord.com/channels/960643023006490684/1084047886494470185/1254635277020954705

Let <math>C(n) = (0, 1, 2n)</math> = <code>0^inf 1 <A2 22 (20)^2n 0^inf</code>

<math display="block">C(g(n) + 8k+1) \to C(g(n) + 8k+1 + n+9)</math><math display="block">\forall k: \frac{h(n) - 45}{65} < k < \frac{h(n) - 22}{38}</math>

Notably, when 8 divides (n+1) then this rule can potentially be applied repeatedly.

Ex: if n = 7, then we get:<math display="block">\forall k \in [101, 172]: C(3273 + 8k) \to C(3273 + 8(k+2))</math>

And we see this starting with <math>C(4137) = C(3273 + 8 \cdot 108)</math> which repeats this rule until we get to <math>C(4665) = C(3273 + 8 \cdot 174)</math>.

And as n gets way bigger, these ranges of repeat will increase exponentially.

== References ==

[[Category:BB(3,3)]][[Category:Potential Cryptids]]

User:Hipparcos/Longitudinal analysis

2026-10-19T04:09:53Z

Hipparcos: revise intro

'''Longitudinal analysis''' refers to ways of analyzing Turing machines in which the effect of the head on the tape is computed not necessarily in chronological order, but rather in "spatial" order, over successive sections of the tape. Unlike in the normal forward simulation of a Turing machine, in longitudinal analysis, there are multiple heads present at once. Sometimes, in analyzing TMs we talk about the effects of the head visiting a certain portion of the tape a certain number of times; longitudinal analysis provides a way of thinking about such situations. A major limitation of longitudinal analysis is that you must predict the state when the head returns to a given point on the tape; this limits the types of TMs that this method is applicable to. Different practitioners of longitudinal analysis have different notations and practices; in this article, I mostly follow dyuan's example, using the notation of ''inverse heads'' and discussing block analysis''.

== What is an inverse head?! ==
Recall that according to [[directed head notation]], we can write the configuration of a Turing machine as something like <code>100 A> 1101</code>. We think of the head as being "in between" tape symbols. In this example, the head has written a 0 on its left, and is traveling to the right. Soon it will read the 1 to its right, but not yet. (An alternative interpretation is that the head has already reached the next tape symbol. The arrow points at the symbol that the read/write head is currently located and about to read, and also points in the direction that the head has traveled from the previous step to the current step.) Inverse heads are a kind of extension to directed head notation. Starting from any given configuration, we can create a pair of a regular head and its inverse head. For example:<syntaxhighlight line="1" lang="text">
100 A> 1101
100 1101
</syntaxhighlight>This inverse head <code><B^-1</code> is a prediction. Specifically, we are predicting that after the head <code>A></code> continues to travel to the right, ''if and when'' it returns back to this spot, it will return as a <code><B</code>. At that point, it can cancel out with the inverse head <code><B^-1</code>. (Technically, we are also allowed to move the <code><B</code> that we have created, but I choose to only move the <code>A></code> for now.) We hope to see something like this: <syntaxhighlight line="2" lang="text">
100 1101 (other symbols)
100 (other symbols)
...a bunch of steps later...
100 
(The symbols and states are just for illustrative purposes and are arbitrary.)

However, if the head comes back as some different state, then our analysis is invalid!
<syntaxhighlight line="2" lang="text">
100 1101 (other symbols)
...a bunch of steps later...
100 
We should have predicted the correct head. Fortunately for us, for some TMs, this is easy to do.

Another thing about inverse heads: when I do longitudinal analysis, I never move an inverse head by itself. This would amount to making another prediction about the forward simulation of the TM, which is difficult to reason about. I only create and destroy matching pairs of head and inverse head, and I move normal heads.

== Longitudinal heads ==
Now consider what we can achieve if we pair a normal head traveling in one direction with an inverse head traveling in the opposite direction. Such a construction is so common that in the context of longitudinal analysis, we often refer to it as just "head". For a simple example, consider the binary counter <code>1RB---_1LC1RB_0RB0LC</code>. If you look at the simulation of this TM, you'll see that the head going right is always <code>B></code>, and the head going left is always <code><C</code>.

The following four rules are commonly applied:
<syntaxhighlight line="1" lang="text">
B> 0 -> <C 1
B> 1 -> 1 B>
0 <C -> 0 B>
1 <C -> <C 0
</syntaxhighlight>

Consider the longitudinal head <code>h = <C^-1 B></code>.

We must work out how this new head interacts with the tape symbols. To do this, we will still have to break it up into its component heads and simulate it with our rules for normal heads. But things are slightly different, since we can create and destroy pairs of matching heads.
<syntaxhighlight line="1" lang="text">
h 0
<C^-1 B> 0
<C^-1 <C 1
1
</syntaxhighlight>
Therefore, <code>h 0 -> 1</code>.

<syntaxhighlight line="1" lang="text">
h 1
<C^-1 B> 1
<C^-1 1 B>
<C^-1 1 <C <C^-1 B>
<C^-1 1 <C h
<C^-1 <C 0 h
0 h
</syntaxhighlight>
Therefore, <code>h 1 -> 0 h</code>.

Behold these new rules. Unlike in normal forward simulation, when a longitudinal head interacts with tape symbols, the head can change in number - one head can be used up and disappear; also, in some TMs (not this one), we see one head pass through a symbol and become two heads. Of course, one head might also appear to just pass through a symbol and remain the same head. Also, consider the tape symbol in the rule <code>h 1 -> 0 h</code>. It has changed from <code>1</code> to <code>0</code>. Even though there is a head to the right of the <code>0</code>, we are actually looking at this tape symbol as if right now it is to the right of the head in normal forward simulation, since we have already computed what happens when <code><C</code> passes through it on the way back to the left.

Let's see how we can use this to analyze the binary counter I mentioned. At step 4, the simulation is <code>$ B> 01 $</code> (<code>$</code> is just shorthand for the endless string of zeros at either end of the tape). It looks like when the head reaches the left end of the tape, rule 3 from above always gets applied, so the head will always be <code>B></code>. So, we might as well assume for the sake of our analysis that this will happen infinitely many times. We replace the simulation with <code>h^inf 01 $</code>.

==Infinite head cycles==
<code>h^inf</code> means there is a sequence of infinitely many <code>h</code> heads.

When I started working with infinite longitudinal heads, I kept making a certain mistake. Just because <code>h 1 -> 0 h</code> is true doesn't mean that we can do this: <code>h^inf 1 -> 0 h^inf</code> (BAD). Do you see what went wrong? If we write out the longitudinal simulation more explicitly, we have
<syntaxhighlight line="1" lang="text">
h^inf 1
...h h h 1
...h h 0 h
...h 1 h
</syntaxhighlight>
and so on. So we can't just repeatedly apply the rule for <code>h 1</code>. But the following analysis works:
<syntaxhighlight line="1" lang="text">
h^inf 1
(h h)^inf 1
(1^-1 h h 1)^inf
(1^-1 h 0 h)^inf
(1^-1 1 h)^inf
h^inf
</syntaxhighlight>
Therefore <code>h^inf 1 -> h^inf</code>, that is, an infinite sequence of <code>h</code> heads can pass through a <code>1</code> symbol and remain as an infinite sequence of <code>h</code> heads. In line 3 of the above analysis, we introduced the use of ''inverse symbols'', which work analogously to inverse heads. Line 2 is in fact equivalent to line 3 (to see this, write out multiple repeats of the cycle and see how the symbols and inverse symbols cancel out). A limitation of this notation is that we no longer keep track of a tape symbol after the infinite head cycle has passed through it (line 6).

We can similarly derive the rule <code>h^inf 0 -> h^inf</code>. Now, we are equipped to run a longitudinal simulation of the binary counter:
<syntaxhighlight line="1" lang="text">
h^inf 01 0^inf
h^inf 1 0^inf
h^inf 0^inf
</syntaxhighlight>
At this point, we reach an infinite loop of <code>h^inf 0^inf -> h^inf 0^inf</code>. For this machine, the head will travel arbitrarily far down the tape to the right and never halt.

===Advanced example of infinite head cycles===
More complicated solution by dyuan. <code>1RB1LC_0RC1LF_1LD0RE_0LA0LE_0LA0LB_0LC---</code>.

<ref>@dyuan01 on Discord: longitudinal rules and initial analysis [https://discord.com/channels/960643023006490684/1460495597386731643/1464154110436577343], revised analysis [https://discord.com/channels/960643023006490684/1460495597386731643/1467632779679371380]</ref>

...

Regarding <code>1RB---_1LC1RB_0RB0LC</code>, we can also derive rules for multiple heads, such as <code>h^2 0 -> 0 h</code>, <code>h^2 1 -> 1 h</code>.

(work in progress)

User:Hipparcos/Longitudinal analysis

2026-10-19T04:08:18Z

Hipparcos: revise intro to reduce the priority of "inverse heads"

'''Longitudinal analysis''' refers to ways of analyzing Turing machines in which the effect of the head on the tape is computed not necessarily in chronological order, but rather in "spatial" order, over successive sections of the tape. Unlike in the normal forward simulation of a Turing machine, in longitudinal analysis, there are multiple heads present at once. Sometimes, in analyzing TMs we talk about the effects of the head visiting a certain portion of the tape a certain number of times; longitudinal analysis provides a way of thinking about such situations. A major limitation of longitudinal analysis is that you must predict the state when the head returns to a given point on the tape; this limits the types of TMs that this method is applicable to. Different practitioners of longitudinal analysis have different notations and practices; in this article, I mostly follow dyuan's example and use ``inverse heads''.

== What is an inverse head?! ==
Recall that according to [[directed head notation]], we can write the configuration of a Turing machine as something like <code>100 A> 1101</code>. We think of the head as being "in between" tape symbols. In this example, the head has written a 0 on its left, and is traveling to the right. Soon it will read the 1 to its right, but not yet. (An alternative interpretation is that the head has already reached the next tape symbol. The arrow points at the symbol that the read/write head is currently located and about to read, and also points in the direction that the head has traveled from the previous step to the current step.) Inverse heads are a kind of extension to directed head notation. Starting from any given configuration, we can create a pair of a regular head and its inverse head. For example:<syntaxhighlight line="1" lang="text">
100 A> 1101
100 1101
</syntaxhighlight>This inverse head <code><B^-1</code> is a prediction. Specifically, we are predicting that after the head <code>A></code> continues to travel to the right, ''if and when'' it returns back to this spot, it will return as a <code><B</code>. At that point, it can cancel out with the inverse head <code><B^-1</code>. (Technically, we are also allowed to move the <code><B</code> that we have created, but I choose to only move the <code>A></code> for now.) We hope to see something like this: <syntaxhighlight line="2" lang="text">
100 1101 (other symbols)
100 (other symbols)
...a bunch of steps later...
100 
(The symbols and states are just for illustrative purposes and are arbitrary.)

However, if the head comes back as some different state, then our analysis is invalid!
<syntaxhighlight line="2" lang="text">
100 1101 (other symbols)
...a bunch of steps later...
100 
We should have predicted the correct head. Fortunately for us, for some TMs, this is easy to do.

Another thing about inverse heads: when I do longitudinal analysis, I never move an inverse head by itself. This would amount to making another prediction about the forward simulation of the TM, which is difficult to reason about. I only create and destroy matching pairs of head and inverse head, and I move normal heads.

== Longitudinal heads ==
Now consider what we can achieve if we pair a normal head traveling in one direction with an inverse head traveling in the opposite direction. Such a construction is so common that in the context of longitudinal analysis, we often refer to it as just "head". For a simple example, consider the binary counter <code>1RB---_1LC1RB_0RB0LC</code>. If you look at the simulation of this TM, you'll see that the head going right is always <code>B></code>, and the head going left is always <code><C</code>.

The following four rules are commonly applied:
<syntaxhighlight line="1" lang="text">
B> 0 -> <C 1
B> 1 -> 1 B>
0 <C -> 0 B>
1 <C -> <C 0
</syntaxhighlight>

Consider the longitudinal head <code>h = <C^-1 B></code>.

We must work out how this new head interacts with the tape symbols. To do this, we will still have to break it up into its component heads and simulate it with our rules for normal heads. But things are slightly different, since we can create and destroy pairs of matching heads.
<syntaxhighlight line="1" lang="text">
h 0
<C^-1 B> 0
<C^-1 <C 1
1
</syntaxhighlight>
Therefore, <code>h 0 -> 1</code>.

<syntaxhighlight line="1" lang="text">
h 1
<C^-1 B> 1
<C^-1 1 B>
<C^-1 1 <C <C^-1 B>
<C^-1 1 <C h
<C^-1 <C 0 h
0 h
</syntaxhighlight>
Therefore, <code>h 1 -> 0 h</code>.

Behold these new rules. Unlike in normal forward simulation, when a longitudinal head interacts with tape symbols, the head can change in number - one head can be used up and disappear; also, in some TMs (not this one), we see one head pass through a symbol and become two heads. Of course, one head might also appear to just pass through a symbol and remain the same head. Also, consider the tape symbol in the rule <code>h 1 -> 0 h</code>. It has changed from <code>1</code> to <code>0</code>. Even though there is a head to the right of the <code>0</code>, we are actually looking at this tape symbol as if right now it is to the right of the head in normal forward simulation, since we have already computed what happens when <code><C</code> passes through it on the way back to the left.

Let's see how we can use this to analyze the binary counter I mentioned. At step 4, the simulation is <code>$ B> 01 $</code> (<code>$</code> is just shorthand for the endless string of zeros at either end of the tape). It looks like when the head reaches the left end of the tape, rule 3 from above always gets applied, so the head will always be <code>B></code>. So, we might as well assume for the sake of our analysis that this will happen infinitely many times. We replace the simulation with <code>h^inf 01 $</code>.

==Infinite head cycles==
<code>h^inf</code> means there is a sequence of infinitely many <code>h</code> heads.

When I started working with infinite longitudinal heads, I kept making a certain mistake. Just because <code>h 1 -> 0 h</code> is true doesn't mean that we can do this: <code>h^inf 1 -> 0 h^inf</code> (BAD). Do you see what went wrong? If we write out the longitudinal simulation more explicitly, we have
<syntaxhighlight line="1" lang="text">
h^inf 1
...h h h 1
...h h 0 h
...h 1 h
</syntaxhighlight>
and so on. So we can't just repeatedly apply the rule for <code>h 1</code>. But the following analysis works:
<syntaxhighlight line="1" lang="text">
h^inf 1
(h h)^inf 1
(1^-1 h h 1)^inf
(1^-1 h 0 h)^inf
(1^-1 1 h)^inf
h^inf
</syntaxhighlight>
Therefore <code>h^inf 1 -> h^inf</code>, that is, an infinite sequence of <code>h</code> heads can pass through a <code>1</code> symbol and remain as an infinite sequence of <code>h</code> heads. In line 3 of the above analysis, we introduced the use of ''inverse symbols'', which work analogously to inverse heads. Line 2 is in fact equivalent to line 3 (to see this, write out multiple repeats of the cycle and see how the symbols and inverse symbols cancel out). A limitation of this notation is that we no longer keep track of a tape symbol after the infinite head cycle has passed through it (line 6).

We can similarly derive the rule <code>h^inf 0 -> h^inf</code>. Now, we are equipped to run a longitudinal simulation of the binary counter:
<syntaxhighlight line="1" lang="text">
h^inf 01 0^inf
h^inf 1 0^inf
h^inf 0^inf
</syntaxhighlight>
At this point, we reach an infinite loop of <code>h^inf 0^inf -> h^inf 0^inf</code>. For this machine, the head will travel arbitrarily far down the tape to the right and never halt.

===Advanced example of infinite head cycles===
More complicated solution by dyuan. <code>1RB1LC_0RC1LF_1LD0RE_0LA0LE_0LA0LB_0LC---</code>.

<ref>@dyuan01 on Discord: longitudinal rules and initial analysis [https://discord.com/channels/960643023006490684/1460495597386731643/1464154110436577343], revised analysis [https://discord.com/channels/960643023006490684/1460495597386731643/1467632779679371380]</ref>

...

Regarding <code>1RB---_1LC1RB_0RB0LC</code>, we can also derive rules for multiple heads, such as <code>h^2 0 -> 0 h</code>, <code>h^2 1 -> 1 h</code>.

(work in progress)

User:Hipparcos/Longitudinal analysis

2026-10-18T23:18:27Z

Hipparcos: finish simple example

'''Longitudinal analysis''' is a way of analyzing Turing machines involving the use of ''inverse heads''. Unlike in the normal forward simulation of a Turing machine, in longitudinal analysis, there can be multiple heads present at once, and the effect of the head on the tape is computed not necessarily in chronological order, but rather on sections of the tape that we are interested in. Sometimes, in analyzing TMs we talk about the effects of the head visiting a certain portion of the tape a certain number of times; longitudinal analysis provides a powerful notation for such situations. A major limitation of longitudinal analysis is that you must predict the state when the head returns to a given point on the tape; this limits the types of TMs that this method is applicable to.

== What is an inverse head?! ==
Recall that according to [[directed head notation]], we can write the configuration of a Turing machine as something like <code>100 A> 1101</code>. We think of the head as being "in between" tape symbols. In this example, the head has written a 0 on its left, and is traveling to the right. Soon it will read the 1 to its right, but not yet. (An alternative interpretation is that the head has already reached the next tape symbol. The arrow points at the symbol that the read/write head is currently located and about to read, and also points in the direction that the head has traveled from the previous step to the current step.) Inverse heads are a kind of extension to directed head notation. Starting from any given configuration, we can create a pair of a regular head and its inverse head. For example:<syntaxhighlight line="1" lang="text">
100 A> 1101
100 1101
</syntaxhighlight>This inverse head <code><B^-1</code> is a prediction. Specifically, we are predicting that after the head <code>A></code> continues to travel to the right, ''if and when'' it returns back to this spot, it will return as a <code><B</code>. At that point, it can cancel out with the inverse head <code><B^-1</code>. (Technically, we are also allowed to move the <code><B</code> that we have created, but I choose to only move the <code>A></code> for now.) We hope to see something like this: <syntaxhighlight line="2" lang="text">
100 1101 (other symbols)
100 (other symbols)
...a bunch of steps later...
100 
(The symbols and states are just for illustrative purposes and are arbitrary.)

However, if the head comes back as some different state, then our analysis is invalid!
<syntaxhighlight line="2" lang="text">
100 1101 (other symbols)
...a bunch of steps later...
100 
We should have predicted the correct head. Fortunately for us, for some TMs, this is easy to do.

Another thing about inverse heads: when I do longitudinal analysis, I never move an inverse head by itself. This would amount to making another prediction about the forward simulation of the TM, which is difficult to reason about. I only create and destroy matching pairs of head and inverse head, and I move normal heads.

== Longitudinal heads ==
Now consider what we can achieve if we pair a normal head traveling in one direction with an inverse head traveling in the opposite direction. Such a construction is so common that in the context of longitudinal analysis, we often refer to it as just "head". For a simple example, consider the binary counter <code>1RB---_1LC1RB_0RB0LC</code>. If you look at the simulation of this TM, you'll see that the head going right is always <code>B></code>, and the head going left is always <code><C</code>.

The following four rules are commonly applied:
<syntaxhighlight line="1" lang="text">
B> 0 -> <C 1
B> 1 -> 1 B>
0 <C -> 0 B>
1 <C -> <C 0
</syntaxhighlight>

Consider the longitudinal head <code>h = <C^-1 B></code>.

We must work out how this new head interacts with the tape symbols. To do this, we will still have to break it up into its component heads and simulate it with our rules for normal heads. But things are slightly different, since we can create and destroy pairs of matching heads.
<syntaxhighlight line="1" lang="text">
h 0
<C^-1 B> 0
<C^-1 <C 1
1
</syntaxhighlight>
Therefore, <code>h 0 -> 1</code>.

<syntaxhighlight line="1" lang="text">
h 1
<C^-1 B> 1
<C^-1 1 B>
<C^-1 1 <C <C^-1 B>
<C^-1 1 <C h
<C^-1 <C 0 h
0 h
</syntaxhighlight>
Therefore, <code>h 1 -> 0 h</code>.

Behold these new rules. Unlike in normal forward simulation, when a longitudinal head interacts with tape symbols, the head can change in number - one head can be used up and disappear; also, in some TMs (not this one), we see one head pass through a symbol and become two heads. Of course, one head might also appear to just pass through a symbol and remain the same head. Also, consider the tape symbol in the rule <code>h 1 -> 0 h</code>. It has changed from <code>1</code> to <code>0</code>. Even though there is a head to the right of the <code>0</code>, we are actually looking at this tape symbol as if right now it is to the right of the head in normal forward simulation, since we have already computed what happens when <code><C</code> passes through it on the way back to the left.

Let's see how we can use this to analyze the binary counter I mentioned. At step 4, the simulation is <code>$ B> 01 $</code> (<code>$</code> is just shorthand for the endless string of zeros at either end of the tape). It looks like when the head reaches the left end of the tape, rule 3 from above always gets applied, so the head will always be <code>B></code>. So, we might as well assume for the sake of our analysis that this will happen infinitely many times. We replace the simulation with <code>h^inf 01 $</code>.

==Infinite head cycles==
<code>h^inf</code> means there is a sequence of infinitely many <code>h</code> heads.

When I started working with infinite longitudinal heads, I kept making a certain mistake. Just because <code>h 1 -> 0 h</code> is true doesn't mean that we can do this: <code>h^inf 1 -> 0 h^inf</code> (BAD). Do you see what went wrong? If we write out the longitudinal simulation more explicitly, we have
<syntaxhighlight line="1" lang="text">
h^inf 1
...h h h 1
...h h 0 h
...h 1 h
</syntaxhighlight>
and so on. So we can't just repeatedly apply the rule for <code>h 1</code>. But the following analysis works:
<syntaxhighlight line="1" lang="text">
h^inf 1
(h h)^inf 1
(1^-1 h h 1)^inf
(1^-1 h 0 h)^inf
(1^-1 1 h)^inf
h^inf
</syntaxhighlight>
Therefore <code>h^inf 1 -> h^inf</code>, that is, an infinite sequence of <code>h</code> heads can pass through a <code>1</code> symbol and remain as an infinite sequence of <code>h</code> heads. In line 3 of the above analysis, we introduced the use of ''inverse symbols'', which work analogously to inverse heads. Line 2 is in fact equivalent to line 3 (to see this, write out multiple repeats of the cycle and see how the symbols and inverse symbols cancel out). A limitation of this notation is that we no longer keep track of a tape symbol after the infinite head cycle has passed through it (line 6).

We can similarly derive the rule <code>h^inf 0 -> h^inf</code>. Now, we are equipped to run a longitudinal simulation of the binary counter:
<syntaxhighlight line="1" lang="text">
h^inf 01 0^inf
h^inf 1 0^inf
h^inf 0^inf
</syntaxhighlight>
At this point, we reach an infinite loop of <code>h^inf 0^inf -> h^inf 0^inf</code>. For this machine, the head will travel arbitrarily far down the tape to the right and never halt.

===Advanced example of infinite head cycles===
More complicated solution by dyuan. <code>1RB1LC_0RC1LF_1LD0RE_0LA0LE_0LA0LB_0LC---</code>.

<ref>@dyuan01 on Discord: longitudinal rules and initial analysis [https://discord.com/channels/960643023006490684/1460495597386731643/1464154110436577343], revised analysis [https://discord.com/channels/960643023006490684/1460495597386731643/1467632779679371380]</ref>

...

Regarding <code>1RB---_1LC1RB_0RB0LC</code>, we can also derive rules for multiple heads, such as <code>h^2 0 -> 0 h</code>, <code>h^2 1 -> 1 h</code>.

(work in progress)

User:Hipparcos/Longitudinal analysis

2026-10-16T22:21:13Z

Hipparcos: /* Longitudinal heads */ add clarification

'''Longitudinal analysis''' is a way of analyzing Turing machines involving the use of ''inverse heads''. Unlike in the normal forward simulation of a Turing machine, in longitudinal analysis, there can be multiple heads present at once, and the effect of the head on the tape is computed not necessarily in chronological order, but rather on sections of the tape that we are interested in. Sometimes, in analyzing TMs we talk about the effects of the head visiting a certain portion of the tape a certain number of times; longitudinal analysis provides a powerful notation for such situations. A major limitation of longitudinal analysis is that you must predict the state when the head returns to a given point on the tape; this limits the types of TMs that this method is applicable to.

== What is an inverse head?! ==
Recall that according to [[directed head notation]], we can write the configuration of a Turing machine as something like <code>100 A> 1101</code>. We think of the head as being "in between" tape symbols. In this example, the head has written a 0 on its left, and is traveling to the right. Soon it will read the 1 to its right, but not yet. (An alternative interpretation is that the head has already reached the next tape symbol. The arrow points at the symbol that the read/write head is currently located and about to read, and also points in the direction that the head has traveled from the previous step to the current step.) Inverse heads are a kind of extension to directed head notation. Starting from any given configuration, we can create a pair of a regular head and its inverse head. For example:<syntaxhighlight line="1" lang="text">
100 A> 1101
100 1101
</syntaxhighlight>This inverse head <code><B^-1</code> is a prediction. Specifically, we are predicting that after the head <code>A></code> continues to travel to the right, ''if and when'' it returns back to this spot, it will return as a <code><B</code>. At that point, it can cancel out with the inverse head <code><B^-1</code>. (Technically, we are also allowed to move the <code><B</code> that we have created, but I choose to only move the <code>A></code> for now.) We hope to see something like this: <syntaxhighlight line="2" lang="text">
100 1101 (other symbols)
100 (other symbols)
...a bunch of steps later...
100 
(The symbols and states are just for illustrative purposes and are arbitrary.)

However, if the head comes back as some different state, then our analysis is invalid!
<syntaxhighlight line="2" lang="text">
100 1101 (other symbols)
...a bunch of steps later...
100 
We should have predicted the correct head. Fortunately for us, for some TMs, this is easy to do.

Another thing about inverse heads: when I do longitudinal analysis, I never move an inverse head by itself. This would amount to making another prediction about the forward simulation of the TM, which is difficult to reason about. I only create and destroy matching pairs of head and inverse head, and I move normal heads.

== Longitudinal heads ==
Now consider what we can achieve if we pair a normal head traveling in one direction with an inverse head traveling in the opposite direction. Such a construction is so common that in the context of longitudinal analysis, we often refer to it as just "head". For a simple example, consider the binary counter <code>1RB---_1LC1RB_0RB0LC</code>. If you look at the simulation of this TM, you'll see that the head going right is always <code>B></code>, and the head going left is always <code><C</code>.

The following four rules are commonly applied:
<syntaxhighlight line="1" lang="text">
B> 0 -> <C 1
B> 1 -> 1 B>
0 <C -> 0 B>
1 <C -> <C 0
</syntaxhighlight>

Consider the longitudinal head <code>h = <C^-1 B></code>.

We must work out how this new head interacts with the tape symbols. To do this, we will still have to break it up into its component heads and simulate it with our rules for normal heads. But things are slightly different, since we can create and destroy pairs of matching heads.
<syntaxhighlight line="1" lang="text">
h 0
<C^-1 B> 0
<C^-1 <C 1
1
</syntaxhighlight>
Therefore, <code>h 0 -> 1</code>.

<syntaxhighlight line="1" lang="text">
h 1
<C^-1 B> 1
<C^-1 1 B>
<C^-1 1 <C <C^-1 B>
<C^-1 1 <C h
<C^-1 <C 0 h
0 h
</syntaxhighlight>
Therefore, <code>h 1 -> 0 h</code>.

Behold these new rules. Unlike in normal forward simulation, when a longitudinal head interacts with tape symbols, the head can change in number - one head can be used up and disappear; also, in some TMs (not this one), we see one head pass through a symbol and become two heads. Of course, one head might also appear to just pass through a symbol and remain the same head. Also, consider the tape symbol in the rule <code>h 1 -> 0 h</code>. It has changed from <code>1</code> to <code>0</code>. Even though there is a head to the right of the <code>0</code>, we are actually looking at this tape symbol as if right now it is to the right of the head in normal forward simulation, since we have already computed what happens when <code><C</code> passes through it on the way back to the left.

Let's see how we can use this to analyze the binary counter I mentioned. At step 4, the simulation is <code>$ B> 01 $</code> (<code>$</code> is just shorthand for the endless string of zeros at either end of the tape). It looks like when the head reaches the left end of the tape, rule 3 from above always gets applied, so the head will always be <code>B></code>. So, we might as well assume for the sake of our analysis that this will happen infinitely many times. We replace the simulation with <code>h^inf 01 $</code>.

==Infinite head cycles==
When I started working with infinite longitudinal heads, I kept making a certain mistake. Just because <code>h 1 -> 0 h</code> is true doesn't mean that we can do this: <code>h^inf 1 -> 0 h^inf</code> (BAD). Do you see what went wrong?

...

We can also apply these rules we just derived to figure out rules for multiple heads, such as <code>h^2 0 -> 0 h</code>, <code>h^2 1 -> 1 h</code>.

(work in progress)

User:Hipparcos/Longitudinal analysis

2026-10-16T22:03:47Z

Hipparcos: explained longitudinal head; start talking about infinite heads

User:Hipparcos/Longitudinal analysis

2026-10-15T22:35:14Z

Hipparcos: /* What is an inverse head?! */ finish section

User:Hipparcos/Longitudinal analysis

2026-10-15T22:22:07Z

Hipparcos: /* What is an inverse head?! */ clarify

User:Hipparcos/Longitudinal analysis

2026-10-15T22:21:29Z

Hipparcos: more on inverse heads

User:Hipparcos/Longitudinal analysis

2026-10-15T22:14:35Z

Hipparcos: more on inverse heads

User:Hipparcos/Longitudinal analysis

2026-10-15T22:07:53Z

Hipparcos: write about inverse heads

User:Hipparcos/Longitudinal analysis

2026-10-15T21:43:17Z

Hipparcos: start page

Skelet 1

2026-10-14T17:22:55Z

Hipparcos: add section on behavior

{{machine|1LC1LE_---1LD_1RD0LD_1LA1RE_0LB0RC}}{{unsolved|What is the exact cycle preperiod of Skelet 1?}}{{Stub}}
[[File:Skeleton warrior.png|thumb|A skeleton warrior holding a sword. The runic inscription on its blade is a string that is particularly often encountered on a tape during Skelet 1 simulation.]]
{{TM|1RB1RD_1LC0RC_1RA1LD_0RE0LB_---1RC}}, called '''Skelet #1''', was one of [[Skelet's 43 holdouts]] and one of the last holdouts in [[BB(5)]]. It was eventually proven to be a [[Translated Cycler]] by Pavel Kropitz and Shawn Ligocki. It is one of the few TMs to have required an individual proof of non-halting in [[Coq-BB5]].<ref name="bbchallenge 2025">https://arxiv.org/pdf/2509.12337 Determination of the fifth Busy Beaver value</ref>

The translated cycle has a period 8,468,569,863 and start step about <math>5.42 \times 10^{51}</math>.<ref>[https://www.sligocki.com/2023/03/13/skelet-1-infinite.html#stats Skelet #1 is infinite] Statistics.</ref> Both of these values are gigantic in comparison to the runtime of the [[5-state busy beaver winner]] which runs for a "mere" 47 million steps.

== Behavior ==
The machine can be analyzed in terms of a number of blocks, one leftward head, and one rightward hard.<ref>[https://www.sligocki.com/2023/03/13/skelet-1-infinite.html#tape-representation Skelet #1 is infinite] Tape representation.</ref> The blocks include base-4 digits and filler. As the simulation proceeds, digits occasionally collide and create "debris" that is later cleaned up. The head remains close to the right end of the tape, leaving behind patterns on the left end of the tape that are never visited again. In order to simulate this machine to translated cycling in a reasonable amount of time, two accelerations are needed: 1) counter acceleration, which involves the base-4 digits and filler, and 2) uni-cycle acceleration. Also, some common blocks of symbols can be repeated as many as 1019 times and must be run-length encoded. Such an accelerated simulator can reach the translated cycle in several 107 simulator steps.

== Preperiod ==
The exact preperiod (minimum cycle start start step) for Skelet 1 is not known, but @hipparcos computed it to be approximately 5418883027667422764169643414989497193809945789706483. This is an upper bound (by this point the TM is cycling). This value is probably accurate to within about one period.<ref>[https://discord.com/channels/960643023006490684/1075378436404678707/1328263736686936066 @hipparcos 13 Jan 2025 Discord]</ref>

== See also ==
* [[Skelet 10]]
* [[Skelet 17]]

== References ==
<references />

== See Also ==
* [https://www.sligocki.com/2023/02/25/skelet-1-wip.html Skelet #1: What I Know]. 25 Feb 2023. Shawn Ligocki
* [https://www.sligocki.com/2023/02/27/skelet-1-halting-config.html Skelet #1: A Halting Counter Config]. 27 Feb 2023. Shawn Ligocki
* [https://www.sligocki.com/2023/03/13/skelet-1-infinite.html Skelet #1 is infinite ... we think]. 13 Mar 2023. Shawn Ligocki
* Simulation code by Pavel & Shawn: https://github.com/univerz/bbc/tree/no1
[[Category:BB(5)]]

User:Hipparcos

2025-10-08T06:58:52Z

Hipparcos: test

I am @hipparcos on Discord.

Some of my Turing machine code: [https://github.com/jhuang97/turing%20machine https://github.com/jhuang97/turing_machine].

testing math rendering...

<math>a+b \mathrel{\textrm{A}} c</math>

Hydra

2025-10-07T16:46:03Z

Hipparcos: fix some directed heads

{{machine|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}{{unsolved|Does Hydra run forever?}}
{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA|undecided}}, called '''Hydra''', is a [[BB(2,5)]] [[Cryptid]]. Its high-level rules were first reported [https://discord.com/channels/960643023006490684/1084047886494470185/1231110668288135208 on Discord] by Daniel Yuan on 20 April 2024, who also gave Hydra said name. Later on, a 6-state, 2-symbol [[Turing machine]] was discovered and named [[Antihydra]] for having similar behaviour to Hydra, making the study of this machine important to the study of that one.

Hydra is known to not generate Sturmian words<ref>Dubickas A. On Integer Sequences Generated by Linear Maps. ''Glasgow Mathematical Journal''. 2009; 51(2): 243-252. doi:[https://doi.org/10.1017/S0017089508004655 10.1017/S0017089508004655]</ref> (Corollary 4).
<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">
{|class="wikitable" style="margin-left: auto; margin-right: auto;"
! !!0!!1!!2!!3!!4
|-
!A
|1RB
|3RB
| ---
|3LA
|1RA
|-
!B
|2LA
|3RA
|4LB
|0LB
|0LA
|}
The transition table of Hydra.</div>
== Analysis ==
Let <math>C(a,b):=0^\infty <\!\!\text{A}\;2\;0^a\;3^b\;2\;0^\infty</math>. Then,<ref>S. Ligocki, "[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)] (2024). Accessed 22 July 2024.</ref>
<math display="block">\begin{array}{|lll|}\hline
C(2a,0)&\xrightarrow{6a^2+20a+4}&0^\infty\;3^{3a+1}\;1\;\text{A}\!\!> 2\;0^\infty,\\
C(2a,b+1)&\xrightarrow{6a^2+23a+10}&C(3a+3,b),\\
C(2a+1,b)&\xrightarrow{4b+6a^2+23a+26}&C(3a+3,b+2).\\\hline
\end{array}</math>
<div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content">
Consider the partial configuration <math>P(m,n):=0^\infty\;3^m\;\text{A}\!\!>02\;0^n</math>. After 14 steps this configuration becomes
<math>0^\infty\;3^{m+3}<\!\!\text{A}\;2\;0^{n-2}</math>. We note the following shift rule:
<math display="block">\begin{array}{|c|}\hline3^s<\!\!\text{A}\xrightarrow{s}\;<\!\!\text{A}\;3^s\\\hline\end{array}</math>
Using this shift rule, we get <math>0^\infty<\!\!\text{A}\;3^{m+3}\;2\;0^{n-2}</math> in <math>m+3</math> steps. From here, we can observe that <math>\text{A}\!\!>0\;3^s</math> turns into <math>3\;\text{A}\!\!>0\;3^{s-1}</math> in three steps if <math>s\ge 1</math>. By repeating this process, we acquire this transition rule:
<math display="block">\begin{array}{|c|}\hline\text{A}\!\!>0\;3^s\xrightarrow{3s}3^s\;\text{A}\!\!>0\\\hline\end{array}</math>
With this rule, it takes <math>3m+9</math> steps to reach the configuration <math>0^\infty\;3^{m+3}\;\text{A}\!\!>02\;0^{n-2}</math>, which is the same configuration as <math>P(m+3,n-2)</math>. To summarize:
<math display="block">\begin{array}{|c|}\hline P(m,n)\xrightarrow{4m+26}P(m+3,n-2)\text{ if }n\ge 2.\\\hline\end{array}</math>
With <math>C(a,b)</math> we have <math>P(0,a)</math>. As a result, we can apply this rule <math display="inline">\big\lfloor\frac{1}{2}a\big\rfloor</math> times, which creates two possible scenarios:
#If <math>a\equiv0\ (\operatorname{mod}2)</math>, then in <math>\sum_{i=0}^{(a/2)-1}(4\times 3i+26)=\textstyle\frac{3}{2}a^2+10a</math> steps we arrive at <math display="inline">P\Big(\frac{3}{2}a,0\Big)</math>. The matching complete configuration is <math>0^\infty\;3^{(3/2)a}\;\text{A}\!\!>02\;3^b\;2\;0^\infty</math>, which in four steps becomes <math>0^\infty\;3^{(3/2)a+1}\;1\;\text{A}\!\!>3^b\;2\;0^\infty.</math> If <math>b=0</math> then we have reached the undefined <code>A2</code> transition in <math display="inline">\frac{3}{2}a^2+10a+4</math> steps total. Otherwise, continuing for three steps gives us <math>0^\infty\;3^{(3/2)+2}<\!\!\text{B}\;0\;3^{b-1}\;2\;0^\infty</math>. Another shift rule is required here:<math display="block">\begin{array}{|c|}\hline3^s<\!\!\text{B}\xrightarrow{s}\;<\!\!\text{B}\;0^s\\\hline\end{array}</math>This means the configuration becomes <math>0^\infty<\!\!\text{B}\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^\infty</math> in <math display="inline">\frac{3}{2}a+2</math> steps, and <math>0^\infty<\!\!\text{A}\;2\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^\infty</math>, equal to <math display="inline">C\Big(\frac{3}{2}a+3,b-1\Big)</math>, one step later. This gives a total of <math display="inline">\frac{3}{2}a^2+\frac{23}{2}a+10</math> steps.
#If <math>a\equiv1\ (\operatorname{mod}2)</math>, then in <math display="inline">\frac{3}{2}a^2+7a-\frac{17}{2}</math> steps we arrive at <math display="inline">P\Big(\frac{3a-3}{2},1\Big)</math>. The matching complete configuration is <math>0^\infty\;3^{(3a-3)/2}\;\text{A}\!\!>020\;3^b\;2\;0^\infty</math>, which in four steps becomes <math>0^\infty\;3^{(3a-1)/2}\;1\;\text{A}\!\!>0\;3^b\;2\;0^\infty</math>, and then <math>0^\infty\;3^{(3a-1)/2}\;1\;3^b\;\text{A}\!\!>02\;0^\infty</math> in <math>3b</math> steps. After 14 steps, we see the configuration <math>0^\infty\;3^{(3a-1)/2}\;1\;3^{b+3}<\!\!\text{A}\;2\;0^\infty</math>, which turns into <math>0^\infty\;3^{(3a-1)/2}\;1<\!\!\text{A}\;3^{b+3}\;2\;0^\infty</math> in <math>b+3</math> steps. In two steps we get <math>0^\infty\;3^{(3a+1)/2}<\!\!\text{B}\;0\;3^{b+2}\;2\;0^\infty</math>, followed by <math>0^\infty<\!\!\text{B}\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^\infty</math> after <math display="inline">\frac{3a+1}{2}</math> more steps. We conclude with <math>0^\infty<\!\!\text{A}\;2\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^\infty</math>, equal to <math display="inline">C\Big(\frac{3a+3}{2},b+2\Big)</math>, one step later. This gives a total of <math display="inline">4b+\frac{3}{2}a^2+\frac{17}{2}a+16</math> steps.
The information above can be summarized as
<math display="block">C(a,b)\rightarrow\begin{cases}0^\infty\;3^{(3/2)a+1}\;1\;\text{A}\!\!>2\;0^\infty&\text{if }a\equiv0\pmod{2}\text{ and }b=0,\\C\Big(\frac{3}{2}a+3,b-1\Big)&\text{if }a\equiv0\pmod{2}\text{ and }b>0,\\C\Big(\frac{3a+3}{2},b+2\Big)&\text{if }a\equiv1\pmod2.\end{cases}</math>
Substituting <math>a\leftarrow 2a</math> for the first two cases and <math>a\leftarrow 2a+1</math> for the third yields the final result.
</div></div>
In effect, the halting problem for Hydra is about whether repeatedly applying the function <math display="inline">f(n)=3\big\lfloor\frac{n}{2}\big\rfloor+3</math> will at some point produce more even values of <math>n</math> than twice the number of odd values.

An alternative version of these rules exists that makes the connection to Antihydra more apparent by using the function <math display="inline">H(n)=\Big\lfloor\frac{3}{2}n\Big\rfloor</math>, or the [[Hydra function]].<ref>S. Ligocki, "[https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html BB(6) is Hard (Antihydra)]" (2024). Accessed 22 July 2024.</ref>

== Trajectory ==
It takes 20 steps to reach the configuration <math>C(3,0)</math>, and from there, the [[Collatz-like]] rules are repeatedly applied. Simulating Hydra has shown that after 4000000 rule steps, we have <math>b=2005373</math>. Here are the first few:
<math display="block">\begin{array}{|c|}\hline C(3,0)\xrightarrow{55}C(6,2)\xrightarrow{133}C(12,1)\xrightarrow{364}C(21,0)\xrightarrow{856}C(33,2)\xrightarrow{1938}C(51,4)\xrightarrow{4367}C(78,6)\rightarrow\cdots\\\hline\end{array}</math>
The heuristic argument that suggests Antihydra is a [[probviously]] non-halting machine can be applied here. This means that if <math>b</math> is to be thought of as moving randomly, then the probability of Hydra halting is <math display="inline">{\Big(\frac{\sqrt{5}-1}{2}\Big)}^{2005374}\approx 4.168\times 10^{-419099}</math>.

== Code ==

Fast Hydra/[[Antihydra]] simulation code by Greg Kuperberg (who said it could be made faster using FLINT):<syntaxhighlight lang="python2" line="1">
# Python script to demonstrate almost linear time hydra simulation
# using fast multiplication.
# by Greg Kuperberg

import time
from gmpy2 import mpz,bit_mask

# Straight computation of t steps of hydra
def simple(n,t):
for s in range(t): n += n>>1
return n

# Accelerated computation of 2**e steps of hydra
def hydra(n,e):
if e < 9: return simple(n,1<<e)
t = 1<<(e-1)
(p3t,m) = (mpz(3)**t,bit_mask(t))
n = p3t*(n>>t) + hydra(n&m,e-1)
return p3t*(n>>t) + hydra(n&m,e-1)

def elapsed():
(last,elapsed.mark) = (elapsed.mark,time.process_time())
return elapsed.mark-last
elapsed.mark = 0

(n,e) = (mpz(3),25)

elapsed()
print('hydra: steps=%d hash=%016x time=%.6fs'
% (1<<e,hash(hydra(n,e)),elapsed()))

# Quadratic time algorithm for comparison
# print('simple: steps=%d hash=%016x time=%.6fs'
# % (1<<e,hash(simple(n,1<<e)),elapsed()))
</syntaxhighlight>

==References==
[[Category:BB(2,5)]][[Category:Cryptids]]

1RB0RA 1LC1LF 1RD0LB 1RA1LE 1RZ0LC 1RG1LD 0RG0RF

2025-10-07T16:22:24Z

Hipparcos: try to fix math rendering issues with directed heads and \textrm -> \text

{{machine|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF|halt}} is the current [[BB(7)]] [[champion]], running for over <math>2 \uparrow^{11} 2 \uparrow^{11} 3</math> steps before it halts. It was discovered by Pavel Kropitz on 10 May 2025 ([https://discord.com/channels/960643023006490684/1369339127652159509/1370678203395604562 Discord link]) and analyzed by Shawn Ligocki (here) on 13 May 2025.

== Analysis by Shawn Ligocki ==
Consider general configurations matching the regex:

<math display="block">0^\infty \; 11 \; (1 \; (01)^*)^* \; 0011100 \; \text{A}\!\! > 0^\infty</math>

=== Low level rules ===
<pre>
01 1 01^n 0011100 A> 00 --> 1 01^n+2 0011100 A>
01^3 11 01^n 0011100 A> 0^6 --> 1 01^n+5 1 01 0011100 A>
01^3 (1 01)^k+1 11 01^n 0011100 A> 0^6 --> 1 01^n+6 (1 01)^k 11 01 0011100 A>
011 (1 01)^k 11 01^n 0011100 A> 0^2 --> 1 Z> 111 01^n+1 00 101^k+2
</pre>

=== Mid level rules ===
Let

<math display="block">
B(a; b, c, ..., z) = 0^\infty \; 111 \; (01)^{3z+1} \; 1 \; \cdots \; 1 (01)^{3c+1} \; 1 \; (01)^{3b+1} \; 1 \; (01)^0 \; 1 \; (01)^{3a+1} \; 0011100 \; \text{A}\!\! > 0^\infty
</math>

and let <code>B(a; [x]*k, y, ...)</code> = <math>B(a; \underbrace{x, \cdots, x}_k, y, ...)</math> (In other words, <code>[x]*k</code> represents k repeats of the value x in a config).

then

<pre>
B(a; b+1, ...) -> B(2a+4; b, ...)
B(a; [0]*k, 0, n+1, ...) -> B(0; [0]*k, a+2, n, ...)
B(a; [0]*k) -> Halt(3a + 2k + 9)

Start at step 8178: B(2, [1]*12)
</pre>

=== High level rule ===
Let

<math display="block">\begin{array}{l}
g_0(x) & = & 2x + 4 \\
g_{k+1}(x) & = & g_k^{x+2}(0) \\
\end{array}</math>

then

<math display="block">
B(a; \underbrace{0, \cdots, 0}_k, n, ...) \to B(g_k^n(a); \underbrace{0, \cdots, 0}_k, 0, ...)
</math>

=== Bound ===
Let

<math display="block">\begin{array}{l}
a_0 & = & 2 \\
a_{k+1} & = & g_k(a_k) \\
\end{array}
</math>

then

<math display="block">
B(a_0; \underbrace{1, \cdots, 1}_k)
\to B(a_k, \underbrace{0, \cdots, 0}_k)
\to \text{Halt}(3 a_k + 2 k + 9)
</math>and

<math display="block">
\text{Start} \to B(a_0; \underbrace{1, \cdots, 1}_{12})
</math>

and so this TM halts with a sigma score of <math> \sigma = 3 a_{12} + 33 </math>

Note that <math>g_k(x) = (2 \uparrow^k (x+4)) - 4</math> and so for <math>k \ge 2</math>,

<math display="block">
a_{k+1} + 4 > 2 \uparrow^k 2 \uparrow^k 3
</math>

and so this TM halts with sigma score <math>\sigma > 2 \uparrow^{11} 2 \uparrow^{11} 3</math>.

This bound is pretty tight: <math>\sigma < 2 \uparrow^{11} 2 \uparrow^{11} 4 = 2 \uparrow^{12} 4</math>.
[[Category:BB(7)]]

User:Hipparcos/Status by BB domain

2025-07-15T15:14:06Z

Hipparcos: add cryptids

I am seeing if it makes sense to summarize Busy Beaver progress in a table:

{| class="wikitable"
|+ Experimental BB Status Panel
|-
! scope="row"| Domain
! scope="col"| [[BB(2)]]
! scope="col"| [[BB(3,2)|BB(3)]]
! scope="col"| [[BB(2,3)]]
![[BB(4)]]
![[BB(2,4)]]
![[BB(5)]]
![[BB(3,3)]]
![[BB(2,5)]]
![[BB(6)]]
![[BB(7)]]
|-
! scope="row"| Maximum<ref>Shows max shift (S) and max score (Σ) values if known. In some cases, only max score is shown. See [[Busy Beaver Functions]].</ref>
| 6
4
|21
6
|38
9
|107
13
|3,932,964
2050
|47,176,870
4098
|<math>>10^{17}</math>
<math>>10^8</math>
|<math>>10 \uparrow \uparrow 4</math>
|<math>>2 \uparrow \uparrow \uparrow 5</math>
|<math>> 2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|-
! scope="row"| Cryptids
|
|
|
|
|
|
|Bigfoot
|Hydra
Bonus Cryptid
|~1000-2500,
incl. Antihydra,
Lucy's Moonlight
|
|-
! scope="row"| Holdouts
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #CFC;" |6 (manual)
19 (Rocq)
| style="background-color: #CFC;" |83
| style="background-color: #FE7;" |2891
| style="background-color: #FFC7C7;" |~108
|-
! scope="row"|Enumeration<ref># of TMs in [[TNF-1RB]]</ref>
| style="background-color: #9EFF9E;" | 41
| style="background-color: #9EFF9E;" |4057
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |620,621
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |126,891,605
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #FFC;" |~33,436,000,000
| style="background-color: #FE7;" |informal, ongoing
|-
!Sporadic<ref>Number of TMs requiring dedicated proofs.</ref>
|
|
|
|
|
|13
|
|
|
|
|-
! scope="row" |Deciders used
|Loop
|Loop
CPS
|Loop
CPS

RepWL
|Loop
CPS

RepWL
|Loop
CPS

RepWL
|Loop
CPS

RepWL

FAR

WFAR
|
|
|
|
|}

<references />

User:Hipparcos/Status by BB domain

2025-07-15T15:08:45Z

Hipparcos: add more info; reorder rows

I am seeing if it makes sense to summarize Busy Beaver progress in a table:

{| class="wikitable"
|+ Experimental BB Status Panel
|-
! scope="row"| Domain
! scope="col"| [[BB(2)]]
! scope="col"| [[BB(3,2)|BB(3)]]
! scope="col"| [[BB(2,3)]]
![[BB(4)]]
![[BB(2,4)]]
![[BB(5)]]
![[BB(3,3)]]
![[BB(2,5)]]
![[BB(6)]]
![[BB(7)]]
|-
! scope="row"| Maximum<ref>Shows max shift (S) and max score (Σ) values if known. In some cases, only max score is shown. See [[Busy Beaver Functions]].</ref>
| 6
4
|21
6
|38
9
|107
13
|3,932,964
2050
|47,176,870
4098
|<math>>10^{17}</math>
<math>>10^8</math>
|<math>>10 \uparrow \uparrow 4</math>
|<math>>2 \uparrow \uparrow \uparrow 5</math>
|<math>> 2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|-
! scope="row"| Cryptids
|
|
|
|
|
|
|Bigfoot
|Hydra
Bonus Cryptid
|1000-2500?
|
|-
! scope="row"| Holdouts
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #CFC;" |6 (manual)
19 (Rocq)
| style="background-color: #CFC;" |83
| style="background-color: #FE7;" |2891
| style="background-color: #FFC7C7;" |~108
|-
! scope="row"|Enumeration<ref># of TMs in [[TNF-1RB]]</ref>
| style="background-color: #9EFF9E;" | 41
| style="background-color: #9EFF9E;" |4057
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |620,621
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |126,891,605
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #FFC;" |~33,436,000,000
| style="background-color: #FE7;" |informal, ongoing
|-
!Sporadic<ref>Number of TMs requiring dedicated proofs.</ref>
|
|
|
|
|
|13
|
|
|
|
|-
! scope="row" |Deciders used
|Loop
|Loop
CPS
|Loop
CPS

RepWL
|Loop
CPS

RepWL
|Loop
CPS

RepWL
|Loop
CPS

RepWL

FAR

WFAR
|
|
|
|
|}

<references />

Busy Beaver Challenge

2025-07-15T14:56:05Z

Hipparcos: improve flow of sentence

The '''Busy Beaver Challenge''' (or '''bbchallenge''') is an online community founded in 2022 with the goal of solving [[BB(5)]]. This goal was accomplished in 2024. Since then the community has focussed on many different goals, including searching through unsolved domains (currently [[BB(6)]], [[BB(3,3)]], [[BB(2,5)]] and [[BB(7)]]) for new [[champions]] and [[cryptids]] and reducing [[holdout]] lists. Most of the interaction happens on our public Discord.

== See Also ==

* Main Website: https://bbchallenge.org/

User:Hipparcos/Status by BB domain

2025-07-15T14:48:53Z

Hipparcos: add more TNF tree sizes

I am seeing if it makes sense to summarize Busy Beaver progress in a table:

{| class="wikitable"
|+ Experimental BB Status Panel
|-
! scope="row"| Domain
! scope="col"| [[BB(2)]]
! scope="col"| [[BB(3,2)|BB(3)]]
! scope="col"| [[BB(2,3)]]
![[BB(4)]]
![[BB(2,4)]]
![[BB(5)]]
![[BB(3,3)]]
![[BB(2,5)]]
![[BB(6)]]
![[BB(7)]]
|-
! scope="row"| Cryptids
|
|
|
|
|
|
|Bigfoot
|Hydra
Bonus Cryptid
|1000-2500?
|
|-
! scope="row"| Holdouts
|
|
|
|
|
|
|6 (manual)
19 (Rocq)
|83
|2891
|
|-
! scope="row"| Maximum<ref>Shows max shift (S) and max score (Σ) values if known. In some cases, only max score is shown. See [[Busy Beaver Functions]].</ref>
| 6
4
|21
6
|38
9
|107
13
|3,932,964
2050
|47,176,870
4098
|<math>>10^{17}</math>
<math>>10^8</math>
|<math>>10 \uparrow \uparrow 4</math>
|
|
|-
! scope="row"|Enumeration<ref># of TMs in [[TNF-1RB]]</ref>
| style="background-color: #9EFF9E;" | 41
| style="background-color: #9EFF9E;" |4057
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |620,621
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |126,891,605
| style="background-color: #CFC;" |
| style="background-color: #CFC;" |
| style="background-color: #FFC;" |~33,436,000,000
| style="background-color: #FE7;" |
|-
!Sporadic<ref>Number of TMs requiring dedicated proofs.</ref>
|
|
|
|
|
|13
|
|
|
|
|-
! scope="row" |Deciders used
|Loop
|Loop
CPS
|Loop
CPS

RepWL
|Loop
CPS

RepWL
|Loop
CPS

RepWL
|Loop
CPS

RepWL

FAR

WFAR
|
|
|
|
|}

<references />

User:Hipparcos/Status by BB domain

2025-07-15T14:38:53Z

Hipparcos: add footnotes

I am seeing if it makes sense to summarize Busy Beaver progress in a table:

{| class="wikitable"
|+ Experimental BB Status Panel
|-
! scope="row"| Domain
! scope="col"| [[BB(2)]]
! scope="col"| [[BB(3,2)|BB(3)]]
! scope="col"| [[BB(2,3)]]
![[BB(4)]]
![[BB(2,4)]]
![[BB(5)]]
![[BB(3,3)]]
![[BB(2,5)]]
![[BB(6)]]
![[BB(7)]]
|-
! scope="row"| Cryptids
|
|
|
|
|
|
|Bigfoot
|Hydra
Bonus Cryptid
|1000-2500?
|
|-
! scope="row"| Holdouts
|
|
|
|
|
|
|6 (manual)
19 (Rocq)
|83
|2891
|
|-
! scope="row"| Maximum<ref>Shows max shift (S) and max score (Σ) values if known. In some cases, only max score is shown. See [[Busy Beaver Functions]].</ref>
| 6
4
|21
6
|38
9
|107
13
|3,932,964
2050
|47,176,870
4098
|<math>>10^{17}</math>
<math>>10^8</math>
|<math>>10 \uparrow \uparrow 4</math>
|
|
|-
! scope="row"|Enumeration<ref># of TMs in [[TNF-1RB]]</ref>
| style="background-color: #9EFF9E;" | 41
| style="background-color: #9EFF9E;" |4057
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |620,621
| style="background-color: #9EFF9E;" |
| style="background-color: #9EFF9E;" |
| style="background-color: #CFC;" |
| style="background-color: #CFC;" |
| style="background-color: #FFC;" |
| style="background-color: #FE7;" |
|-
!Sporadic<ref>Number of TMs requiring dedicated proofs.</ref>
|
|
|
|
|
|13
|
|
|
|
|-
! scope="row" |Deciders used
|Loop
|Loop
CPS
|Loop
CPS

RepWL
|Loop
CPS

RepWL
|Loop
CPS

RepWL
|Loop
CPS

RepWL

FAR

WFAR
|
|
|
|
|}

<references />

Module:Sandbox/Hipparcos

2025-07-15T14:11:17Z

Hipparcos: module test

local p = {}
p.main = function(frame)
local args = frame.args
local out = ''
-- some code here

return out
end
return p

Module:Sandbox/doc

2025-07-15T14:09:57Z

Hipparcos: adapt Module:Sandbox/doc from Wikipedia

This page is not itself a sandbox. If you want to test a module, see the instructions below; do not edit this page itself.

== Scribunto testing area ==

This is not an actual [https://en.wikipedia.org/wiki/Wikipedia:Lua Lua] module. It exists to provide a convenient pseudo-namespace for code testing, hopefully preventing the main Module: namespace from becoming littered with experiments, as Lua modules cannot exist as subpages in the User: namespace.

Please name your experimental modules in the following format to help keep things tidy:

Module:Sandbox/<var>Your User Name</var>
<inputbox>
type=create
preload=Module:Sandbox/new
editintro=Template:New module editintro
prefix=Module:Sandbox/
placeholder=Insert your username here
button label=Create new sandbox module
</inputbox>
If you need more Module sandboxes, create subpages of the sandbox thus created.

Module:Sandbox

2025-07-15T14:00:04Z

Hipparcos: copy over Wikipedia's Module:Sandbox

--[[
Please do not edit this page. This page serves as a root for the sandbox.

The following below is some starter code that you may use to get started with module writing and testing. Please feel free to take this to get started on your module.

Remember to remove this top notice when copying and pasting from here to your module sandbox.
]]--

local p = {}
p.main = function(frame)
local args = frame.args
local out = ''
-- some code here

return out
end
return p

User:Hipparcos/Status by BB domain

2025-07-15T13:53:28Z

Hipparcos: formatting; types of holdouts

User:Hipparcos/Status by BB domain

2025-07-15T13:50:02Z

Hipparcos: add a color background to indicate status of enumeration

User:Hipparcos/Status by BB domain

2025-07-15T03:08:49Z

Hipparcos: worked on BB status table some more

User:Hipparcos/Status by BB domain

2025-07-15T01:56:46Z

Hipparcos: trying a format for Busy Beaver status panel

I am seeing if it makes sense to summarize Busy Beaver progress in a table:

{| class="wikitable"
|+ Experimental BB Status Panel
|-
! scope="row"| Domain
! scope="col"| [[BB(2)]]
! scope="col"| [[BB(3,2)]]
! scope="col"| [[BB(2,3)]]
|-
! scope="row"| Cryptids
|
|
|
|-
! scope="row"| Holdouts
|
|
|
|-
! scope="row"| High score
| 6, 4
|
|
|-
! scope="row"|Enumeration
| style="background-color: #9EFF9E;" | 41
|
|
|-
! scope="row"|Deciders used
|Loops
|
|
|}

User:Hipparcos

2025-07-15T01:15:03Z

Hipparcos: create my user page

I am @hipparcos on Discord.

Some of my Turing machine code: [https://github.com/jhuang97/turing%20machine https://github.com/jhuang97/turing_machine].

BB(7)

2025-06-18T03:29:53Z

Hipparcos: /* Current Progress */ 71xxxx results

The 7-state, 2-symbol Busy Beaver problem '''BB(7)''' is a mostly unexplored domain with only preliminary information.

The current BB(7) champion is {{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}} discovered by Pavel Kropitz in 2025 proving the lower bound:<math display="block">S(7) > \Sigma(7) > 2 \uparrow^{11} 2 \uparrow^{11} 3</math>

== History ==
Before 2025, the only known BB(7) champions were produced by hand, not by search. Example, Milton Green designed a machine in 1964 that had [[sigma score]] 22,961 and Wythagoras modified a BB(6) champion in 2014 to produce a machine that had sigma score <math>> 10 \uparrow\uparrow 5</math>.

In May 2025, mxdys shared [https://github.com/ccz181078/TM C++ code] that breaks up the BB(7) enumeration into 1 million subtasks which each run for about 2 minutes and leave ~100 holdouts each. Various folks on Discord have been investigating different sections of this domain to search for champions.

Within three days of the code's release, the Ligockis found three champions after applying their deciders to enumerator output. Shawn Ligocki found the first two, {{TM|1RB0RF_1LC0RE_1RD1LB_1LA1LD_0RA0LE_1RG0LB_1RZ1RB}} and {{TM|1RB1RA_1RC0LC_0LD1LG_1LF0LE_1RZ1LF_0LA1LD_1RA1LC}}, with sigma scores of approximately 10 ↑↑ 22 and 10 ↑↑ 35. That evening, Terry Ligocki found {{TM|1RB0LG_1RC0RF_1LD1RZ_1LF0LE_1RA1LD_1LG1RE_0LB0LB}}, with sigma score ~10 ↑↑ 46. These were all outpaced by Pavel's champion.

== Top Halters ==
Based on limited search through a subset of the 1 million subtasks from mxdys's code, the top 20 scoring known machines are:
{| class="wikitable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|Pavel Kropitz
|-
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LF_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|Andrew Ducharme
|-
|{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ}}
|10 ↑↑ 286.17
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC0RA_1RD0RC_1LE1LD_1LA0LF_0LA0LG_1RZ0RD}}
|10 ↑↑ 246.32
|@Iijil
|-
|{{TM|1RB0LD_0LC1RZ_1RA0RD_1RE1LD_1LF0RC_0LG1LE_1RC0LD}}
|10 ↑↑ 192.67
|Andrew Ducharme
|-
|{{TM|1RB0LD_0LC1RZ_1RA0RD_1RE1LD_1LF0RC_0LG1LE_1RG0LD}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RD0LA_1RF0RA_0RG0LA_1RB1RZ}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RD0LA_1RF0RA_1RG0LA_0LE1RZ}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RA0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RG0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LG_1RF0RG_0RA0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB1RZ_1LC0RF_0LD1LB_1RD0LE_1RB1LE_1RG0RE_0RA0LE}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_1LG1RE_1LD0RF_0RA1RE_1RZ0RA}}
|10 ↑↑ 188.28
|@XnoobSpeakable, @Peacemaker II
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_0RF0LF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LF0RF_0RA1RE_1RZ0RE}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LF0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_1LG1RE_0RF0LF_0RA1RE_1RZ0LE}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_1LG1RE_0RF0LF_0RA1RE_1RZ0RA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_1LG1RE_1LF0RF_0RA1RE_1RZ0RA}}
|10 ↑↑ 188.28
|Terry Ligocki
|}

The top 20 known halters with unique scores are:

{| class="wikitable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|Pavel Kropitz
|-
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LF_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|Andrew Ducharme
|-
|{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ}}
|10 ↑↑ 286.17
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC0RA_1RD0RC_1LE1LD_1LA0LF_0LA0LG_1RZ0RD}}
|10 ↑↑ 246.32
|@Iijil
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RA0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC0LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LC}}
|10 ↑↑ 140.28
|@stokastic
|-
|{{TM|1RB0LG_0RC1RZ_1LD0LA_1RE1LE_1LC1RF_0RE0RA_0RF1LG}}
|10 ↑↑ 133.85
|@poppuncher
|-
|{{TM|1RB1RZ_1RC0RF_1LD1RB_1RG0LE_1LD0RA_1RE0LD_0RC1LF}}
|10 ↑↑ 129.24
|@Iijil
|-
|{{TM|1RB0LC_1RC0RG_1RD0LF_1RE0RF_1LA1RG_1LE1LF_1RZ1RD}}
|10 ↑↑ 126.20
|@stokastic
|-
|{{TM|1RB1LF_1RC1RA_1LD0LD_1LA1LE_0LA0LD_1LG0RF_0LE1RZ}}
|10 ↑↑ 116.98
|Terry Ligocki
|-
|{{TM|1RB0RD_1RC0LA_0LA0LE_1RE1RZ_1RF0RA_1LG0LE_1LC0LG}}
|10 ↑↑ 116.05
|
|-
|{{TM|1RB0RD_1RC0RA_0RD1LD_0LE1LF_1LA0LG_0LC1LB_1LC1RZ}}
|10 ↑↑ 115.52
|@prurq
|-
|{{TM|1RB0RF_1RC0RB_0RD0RF_1LE0LG_1LC0RD_1LA0LD_1LF1RZ}}
|10 ↑↑ 114.61
|Andrew Ducharme
|-
|{{TM|1RB0RE_1LC0LA_1LD0LC_0LE0LA_1RF0RG_1RD0LE_1RA1RZ}}
|10 ↑↑ 114.60
|Shawn Ligocki
|-
|{{TM|1RB0RE_0RC1LC_0LD1LF_1LE0LG_1RA0RC_0LB1LA_1LB1RZ}}
|10 ↑↑ 114.57
|Andrew Ducharme
|-
|{{TM|1RB0RG_1LC0LE_1LD0LB_1RB1RE_0RA1RF_0RD1RC_1RD1RZ}}
|10 ↑↑ 113.38
|Terry Ligocki
|-
|{{TM|1RB1RZ_1RC1RA_1RD0RB_1LE0RC_1LF0LD_1RG0LF_1RC0LG}}
|10 ↑↑ 108.77
|Terry Ligocki
|-
|{{TM|1RB0LA_1RC0RA_0RD0RB_1LE0RC_0LD1LF_0LA1LG_0LC1RZ}}
|10 ↑↑ 105.37
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC1RA_1RD0RG_1LA1RZ_1RA1LF_1LA0LE_0RF1RG}}
|10 ↑↑ 93.81
|Andrew Ducharme
|}

== Current Progress ==
This is a summary of the 1 million subtasks from mxdys's code that have been processed, including further processing by Shawn Ligocki's linear rule code ("TBD" = "To Be Determined", "TBE" = "To Be Entered"):
{| class="wikitable defaultleft"
!rowspan="2"|Task range
!rowspan="2"|Done by
!colspan="2"|Completed
!rowspan="2"|# holdouts
!rowspan="2"|Maximum Score TM
!rowspan="2"|~Sigma
!rowspan="2"|Source
|-
!enumeration
!linear rule
|-
|00xxxx
|rowspan="10"|@Iijil
|Yes
|Yes
|728,495
|{{TM|1RB0RF_1RC1LF_0RD0RD_1LE0LB_1RA1RZ_1LG1RA_1LD0RC}}
|10 ↑↑ 45.64
|rowspan="10"|[https://drive.google.com/drive/folders/1wniwrAuvsHfkvro8Tg65WAMNZEuIekzD Google Drive folder]
|-
|01xxxx
|Yes
|Yes
|817,178
|{{TM|1RB0LE_1RC0RA_1RD0RC_1LE1LD_1LA0LF_0LA0LG_1RZ0RD}}
|10 ↑↑ 246.32
|-
|02xxxx
|Yes
|No
|963,486
|TBD
|TBD
|-
|03xxxx
|Yes
|No
|1,052,504
|TBD
|TBD
|-
|04xxxx
|Yes
|No
|955,711
|TBD
|TBD
|-
|05xxxx
|Yes
|No
|1,056,745
|TBD
|TBD
|-
|06xxxx
|Yes
|No
|950,271
|TBD
|TBD
|-
|07xxxx
|Yes
|No
|1,053,750
|TBD
|TBD
|-
|08xxxx
|Yes
|No
|951,114
|TBD
|TBD
|-
|09xxxx
|Yes
|No
|1,052,362
|TBD
|TBD
|-
|13xxxx
|Shawn Ligocki
|Yes
|Yes
|1,192,442
|{{TM|1RB0RE_1LC0LA_1LD0LC_0LE0LA_1RF0RG_1RD0LE_1RA1RZ}}
|10 ↑↑ 114.60
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|
20xxxx - 
22xxxx
|@C7X
|Yes
|No
|2,972,747
|TBD
|TBD
|[https://drive.google.com/drive/folders/11iGTKsvu2Y7aFrwOcWS1LYvcN6i_7-JM?usp=sharing Google Drive folder]
|-
|243308
|@uni
|Yes
|No
|TBE
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|[https://discord.com/channels/960643023006490684/1369339127652159509/1373660959960469545 Discord post]
|-
|25xxxx
|rowspan="10"|@stokastic
|Yes
|Yes
|815,919
|{{TM|1RB1RZ_1LC0LE_0LD0LC_0RE1LB_1RF0RG_0LD1RB_1RD1RA}}
|10 ↑↑ 31.33
|rowspan="10"|[https://drive.google.com/drive/folders/16_qIdWWD-wolj6zURB5ZSbY-otI4zoUF?usp=sharing Google Drive folder]
|-
|26xxxx
|Yes
|Yes
|731,995
|{{TM|1RB1RZ_0LC1RB_0LE0LD_1LE1LD_0RF0LC_0RG1RF_1RD0RA}}
|10 ↑↑ 36.26
|-
|27xxxx
|Yes
|Yes
|811,486
|{{TM|1RB0RG_1LC1LB_0RE0LD_0LC1RF_0RA1RE_0LF0LB_1RF1RZ}}
|10 ↑↑ 63.56
|-
|28xxxx
|Yes
|Yes
|956,935
|{{TM|1RB1RZ_0LC1RC_0RE1RD_0RB1RG_1RF0RA_1LG0LC_1LB0LF}}
|10 ↑↑ 114.57
|-
|29xxxx
|Yes
|Yes
|1,052,415
|{{TM|1RB1LA_1RC1RD_0LA1LG_1RZ0LE_1RB1RF_1RE0LC_0RE1LF}}
|10 ↑↑ 31.67
|-
|30xxxx
|Yes
|Yes
|1,032,095
|{{TM|1RB0LC_1RC0RG_1RD0LF_1RE0RF_1LA1RG_1LE1LF_1RZ1RD}}
|10 ↑↑ 126.20
|-
|31xxxx
|Yes
|Yes
|1,436,970
|{{TM|1RB1LD_1LC0RF_0RA0LB_0LE1RZ_1LA0LE_1RG1LA_0RC0RF}}
|10 ↑↑ 50.27
|-
|32xxxx
|Yes
|Yes
|1,036,950
|{{TM|1RB1RD_1LC0RF_0LE0LD_1LE1LE_1RF0LB_1RB0RG_1RA1RZ}}
|10 ↑↑ 50.28
|-
|33xxxx
|Yes
|Yes
|1,432,081
|{{TM|1RB0LC_1LC0LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LC}}
|10 ↑↑ 140.28
|-
|34xxxx
|Yes
|Yes
|1,032,970
|{{TM|1RB0RA_1LC0LE_0LD0LB_1RE0RD_0RA0LF_1RD1RG_0RF1RZ}}
|10 ↑↑ 72.69
|-
|
35xxxx - 
39xxxx
|Terry Ligocki
|Yes
|Yes
|4,894,047
|{{TM|1RB1RZ_1LC0RF_0LD1LB_1RD0LE_1RB1LE_1RG0RE_0RA0LE}}
|10 ↑↑ 192.67
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|40xxxx
| rowspan="8" |Andrew Ducharme
|Yes
|Yes
|730,310
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LF_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
| rowspan="8" |[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|41xxxx
|Yes
|Yes
|814,075
|{{TM|1RB0LD_0LC1RZ_1RA0RD_1RE1LD_1LF0RC_0LG1LE_1RC0LD}}
|10 ↑↑ 192.67
|-
|42xxxx
|Yes
|Yes
|739,729
|{{TM|1RB1LD_0RC1RF_1LD0LE_0LE0LA_1LA1LE_1RG0LA_1RZ1RA}}
|10 ↑↑ 46.26
|-
|43xxxx
|Yes
|Yes
|817,332
|{{TM|1RB0LE_1RC1RA_1RD0RG_1LA1RZ_1RA1LF_1LA0LE_0RF1RG}}
|10 ↑↑ 93.81
|-
|44xxxx
|Yes
|Yes
|729,686
|{{TM|1RB1LC_1RC0RC_1RD1LA_0RE1RF_1LC0LG_1LA1LE_1RZ1LF}}
|10 ↑↑ 76.36
|-
|45xxxx
|Yes
|Yes
|812,973
|{{TM|1RB0RE_0RC1LC_0LD1LF_1LE0LG_1RA0RC_0LB1LA_1LB1RZ}}
|10 ↑↑ 114.57
|-
|46xxxx
|Yes
|Yes
|725,102
|{{TM|1RB1RA_0LC0RE_0LD1LC_1LA0LF_0RB0RA_1LG1RZ_0RE1LG}}
|10 ↑↑ 36.26
|-
|47xxxx
|No
|No
|TBD
|TBD
|TBD
|-
|48xxxx
| rowspan="2" |Tobiáš Brichta
|No
|No
|TBD
|TBD
|TBD
| rowspan="2" |[https://drive.google.com/drive/folders/1-csgJ5uSIX3SKlqTkSnhkUuEYLKgCw81 Google Drive folder]
|-
|49xxxx
|No
|No
|TBD
|TBD
|TBD
|-
|500xxx
|rowspan="2"|@prurq
|Yes
|Yes
|120,520
|{{TM|1RB0RD_1RC0RA_0RD1LD_0LE1LF_1LA0LG_0LC1LB_1LC1RZ}}
|10 ↑↑ 115.52
|rowspan="2"|[https://drive.google.com/drive/folders/145H4sT4F9KJYGSrlIETZdBOIMR7krLQm Google Drive folder]
|-
|501xxx
|Yes
|No
|96,102
|TBD
|TBD
|-
|60xxxx
| rowspan="5" |@gerbil5709
|Yes
|No
|957,769
|TBD
|TBD
| rowspan="5" |[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing Google Drive folder]
|-
|61xxxx
|Yes
|No
|1,052,047
|TBD
|TBD
|-
|62xxxx
|Yes
|No
|959,753
|TBD
|TBD
|-
|63xxxx
|Yes
|No
|1,051,882
|TBD
|TBD
|-
|64xxxx
|No
|No
|TBD
|TBD
|TBD
|-
|
65xxxx - 
68xxxx
|Terry Ligocki
|Yes
|Yes
|3,076,778
|{{TM|1RB0LD_0LC1RZ_1RA0RD_1RE1LD_1LF0RC_0LG1LE_1RG0LD}}
|10 ↑↑ 192.67
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|69xxxx
|@poppuncher
|Yes
|Yes
|1,053,119
|{{TM|1RB0LG_0RC1RZ_1LD0LA_1RE1LE_1LC1RF_0RE0RA_0RF1LG}}
|10 ↑↑ 133.85
|[https://drive.google.com/drive/folders/1KlCZqXxqVPuBPkDcCBocuMPA8paq9b8P?usp=drive_link Google Drive folder]
|-
|70xxxx
|@hipparcos
|Yes
|Yes
|798,304
|
{{TM|1RB0LF_1RC1LE_0RD1RA_1RE1RG_0LA1LB_1LE1RG_0RC1RZ}}
|
10 ↑↑ 33.81
|[https://github.com/jhuang97/bb7x2/releases/tag/70xxxx Github release]
|-
|71xxxx
|@hipparcos
|Yes
|Yes
|1,100,790
|{{TM|1RB1RZ_1LC1RD_0LD0LC_1LE1RA_1LF0LE_1RF0RG_1RG0RD}}
|10 ↑↑ 77.50
|[https://github.com/jhuang97/bb7x2/releases/tag/71xxxx Github release]
|-
|75xxxx
|Terry Ligocki
|Yes
|Yes
|1,103,089
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_0RF0LF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|79xxxx
|Terry Ligocki
|Yes
|No
|1,438,112
|TBD
|TBD
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|80xxxx
|@xnoobspeakable
|Yes
|No
|964,396
|TBD
|TBD
| rowspan="2" |[https://drive.google.com/drive/folders/1TpuEC7KottEmvsFnCREugnlVMPaY5ZHi?usp=sharing Google Drive folder]
|-
|81xxxx
|@xnoobspeakable
|No
|No
|TBD
|TBD
|TBD
|-
|
82xxxx - 
99xxxx
|Terry Ligocki
|Yes
|Yes
|15,673,786
|{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ}}
|10 ↑↑ 286.17
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|}
[[Category:BB Domain]]

BB(7)

2025-06-07T04:24:16Z

Hipparcos: /* Current Progress */ started working on 71xxxx

The 7-state, 2-symbol Busy Beaver problem '''BB(7)''' is a mostly unexplored domain with only preliminary information.

The current BB(7) champion is {{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}} discovered by Pavel Kropitz in 2025 proving the lower bound:<math display="block">S(7) > \Sigma(7) > 2 \uparrow^{11} 2 \uparrow^{11} 3</math>

== History ==
Before 2025, the only known BB(7) champions were produced by hand, not by search. Example, Milton Green designed a machine in 1964 that had [[sigma score]] 22,961 and Wythagoras modified a BB(6) champion in 2014 to produce a machine that had sigma score <math>> 10 \uparrow\uparrow 5</math>.

In May 2025, mxdys shared [https://github.com/ccz181078/TM C++ code] that breaks up the BB(7) enumeration into 1 million subtasks which each run for about 2 minutes and leave ~100 holdouts each. Various folks on Discord have been investigating different sections of this domain to search for champions.

Within three days of the code's release, the Ligockis found three champions after applying their deciders to enumerator output. Shawn Ligocki found the first two, {{TM|1RB0RF_1LC0RE_1RD1LB_1LA1LD_0RA0LE_1RG0LB_1RZ1RB}} and {{TM|1RB1RA_1RC0LC_0LD1LG_1LF0LE_1RZ1LF_0LA1LD_1RA1LC}}, with sigma scores of approximately 10 ↑↑ 22 and 10 ↑↑ 35. That evening, Terry Ligocki found {{TM|1RB0LG_1RC0RF_1LD1RZ_1LF0LE_1RA1LD_1LG1RE_0LB0LB}}, with sigma score ~10 ↑↑ 46. These were all outpaced by Pavel's champion.

== Top Halters ==
Based on limited search through a subset of the 1 million subtasks from mxdys's code, the top 20 scoring known machines are:
{| class="wikitable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|Pavel Kropitz
|-
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LF_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|Andrew Ducharme
|-
|{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ}}
|10 ↑↑ 286.17
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC0RA_1RD0RC_1LE1LD_1LA0LF_0LA0LG_1RZ0RD}}
|10 ↑↑ 246.32
|@Iijil
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RA0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LG_1RF0RG_0RA0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RG0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LF0RF_0RA1RE_1RZ0RE}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LF0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_1LG1RE_1LF0RF_0RA1RE_1RZ0RA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_1LG1RE_1LD0RF_0RA1RE_1RZ0RA}}
|10 ↑↑ 188.28
|@XnoobSpeakable, @Peacemaker II
|-
|{{TM|1RB0LG_0RC1RZ_1LD0LA_1RE1LE_1LC1RF_0RE0RA_0RF1LG}}
|10 ↑↑ 133.85
|@poppuncher
|-
|{{TM|1RB1RZ_1RC0RF_1LD1RB_1RG0LE_1LD0RA_1RE0LD_0RC1LF}}
|10 ↑↑ 129.24
|@Iijil
|-
|{{TM|1RB1LF_1RC1RA_1LD0LD_1LA1LE_0LA0LD_1LG0RF_0LE1RZ}}
|10 ↑↑ 116.97
|Terry Ligocki
|-
|{{TM|1RB0RD_1RC0LA_0LA0LE_1RE1RZ_1RF0RA_1LG0LE_1LC0LG}}
|10 ↑↑ 116.05
|
|-
|{{TM|1RB0RD_1RC0RA_0RD1LD_0LE1LF_1LA0LG_0LC1LB_1LC1RZ}}
|10 ↑↑ 115.52
|@prurq
|-
|{{TM|1RB0RF_1RC0RB_0RD0RF_1LE0LG_1LC0RD_1LA0LD_1LF1RZ}}
|10 ↑↑ 114.61
|Andrew Ducharme
|-
|{{TM|1RB0RE_1LC0LA_1LD0LC_0LE0LA_1RF0RG_1RD0LE_1RA1RZ}}
|10 ↑↑ 114.60
|Shawn Ligocki
|-
|{{TM|1RB0RE_0RC1LC_0LD1LF_1LE0LG_1RA0RC_0LB1LA_1LB1RZ}}
|10 ↑↑ 114.57
|Andrew Ducharme
|-
|{{TM|1RB0RG_1LC0LE_1LD0LB_1RB1RE_0RA1RF_0RD1RC_1RD1RZ}}
|10 ↑↑ 113.37
|Terry Ligocki
|}
The top 20 known halters with unique scores are:
{| class="wikitable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|Pavel Kropitz
|-
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LF_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|Andrew Ducharme
|-
|{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ}}
|10 ↑↑ 286.17
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC0RA_1RD0RC_1LE1LD_1LA0LF_0LA0LG_1RZ0RD}}
|10 ↑↑ 246.32
|@Iijil
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RA0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LG_0RC1RZ_1LD0LA_1RE1LE_1LC1RF_0RE0RA_0RF1LG}}
|10 ↑↑ 133.85
|@poppuncher
|-
|{{TM|1RB1RZ_1RC0RF_1LD1RB_1RG0LE_1LD0RA_1RE0LD_0RC1LF}}
|10 ↑↑ 129.24
|@Iijil
|-
|{{TM|1RB1LF_1RC1RA_1LD0LD_1LA1LE_0LA0LD_1LG0RF_0LE1RZ}}
|10 ↑↑ 116.97
|Terry Ligocki
|-
|{{TM|1RB0RD_1RC0LA_0LA0LE_1RE1RZ_1RF0RA_1LG0LE_1LC0LG}}
|10 ↑↑ 116.05
|
|-
|{{TM|1RB0RD_1RC0RA_0RD1LD_0LE1LF_1LA0LG_0LC1LB_1LC1RZ}}
|10 ↑↑ 115.52
|@prurq
|-
|{{TM|1RB0RF_1RC0RB_0RD0RF_1LE0LG_1LC0RD_1LA0LD_1LF1RZ}}
|10 ↑↑ 114.61
|Andrew Ducharme
|-
|{{TM|1RB0RE_1LC0LA_1LD0LC_0LE0LA_1RF0RG_1RD0LE_1RA1RZ}}
|10 ↑↑ 114.60
|Shawn Ligocki
|-
|{{TM|1RB0RE_0RC1LC_0LD1LF_1LE0LG_1RA0RC_0LB1LA_1LB1RZ}}
|10 ↑↑ 114.57
|Andrew Ducharme
|-
|{{TM|1RB0RG_1LC0LE_1LD0LB_1RB1RE_0RA1RF_0RD1RC_1RD1RZ}}
|10 ↑↑ 113.37
|Terry Ligocki
|-
|{{TM|1RB1RZ_1RC1RA_1RD0RB_1LE0RC_1LF0LD_1RG0LF_1RC0LG}}
|10 ↑↑ 108.77
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC1RA_1RD0RG_1LA1RZ_1RA1LF_1LA0LE_0RF1RG}}
|10 ↑↑ 93.81
|Andrew Ducharme
|-
|{{TM|1RB0RF_1LC0LD_1RC0LB_1LE1RG_1RA1RE_1RD0RD_0RA1RZ}}
|10 ↑↑ 93.78
|Terry Ligocki
|-
|{{TM|1RB1LB_1LC1RE_1RD1RC_0RE0RD_1LF0RB_1LF1LG_1RZ0LA}}
|10 ↑↑ 86.40
|Terry Ligocki
|-
|{{TM|1RB1LC_1RC0LG_1RD0RG_0LE0RA_1LC0LF_0LD1LF_1RZ1RA}}
|10 ↑↑ 82.44
|Terry Ligocki
|}

== Current Progress ==
This is a summary of the 1 million subtasks from mxdys's code that have been processed, including further processing by Shawn Ligocki's linear rule code ("TBD" = "To Be Determined", "TBE" = "To Be Entered"):
{| class="wikitable defaultleft"
!rowspan="2"|Task range
!rowspan="2"|Done by
!colspan="2"|Completed
!rowspan="2"|# holdouts
!rowspan="2"|Maximum Score TM
!rowspan="2"|~Sigma
!rowspan="2"|Source
|-
!enumeration
!linear rule
|-
|00xxxx
|@Iijil
|Yes
|Yes
|728,495
|{{TM|1RB0RF_1RC1LF_0RD0RD_1LE0LB_1RA1RZ_1LG1RA_1LD0RC}}
|10 ↑↑ 45.64
| rowspan="10" |[https://drive.google.com/drive/folders/1wniwrAuvsHfkvro8Tg65WAMNZEuIekzD Google Drive folder]
|-
|01xxxx
|@Iijil
|Yes
|Yes
|1,056,253
|TBD
|TBD
|-
|02xxxx
|@Iijil
|Yes
|No
|963,486
|TBD
|TBD
|-
|03xxxx
|@Iijil
|Yes
|No
|1,052,504
|TBD
|TBD
|-
|04xxxx
|@Iijil
|Yes
|No
|955,711
|TBD
|TBD
|-
|05xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|06xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|07xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|08xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|09xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|13xxxx
|Shawn Ligocki
|Yes
|Yes
|1,192,442
|{{TM|1RB0RE_1LC0LA_1LD0LC_0LE0LA_1RF0RG_1RD0LE_1RA1RZ}}
|10 ↑↑ 114.60
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|20xxxx - 
21xxxx
|@C7X
|Yes
|No
|TBD
|TBD
|TBD
|[https://drive.google.com/drive/folders/11iGTKsvu2Y7aFrwOcWS1LYvcN6i_7-JM?usp=sharing Google Drive folder]
|-
|243308
|@uni
|Yes
|No
|TBE
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|[https://discord.com/channels/960643023006490684/1369339127652159509/1373660959960469545 Discord post]
|-
|25xxxx
|@stokastic
|Yes
|No
|1,056,591
|{{TM|1RB1RZ_1LC0LE_0LD0LC_0RE1LB_1RF0RG_0LD1RB_1RD1RA}}
|10 ↑↑ 31.33
| rowspan="10" |[https://drive.google.com/drive/folders/16_qIdWWD-wolj6zURB5ZSbY-otI4zoUF?usp=sharing Google Drive folder]
|-
|26xxxx
|@stokastic
|Yes
|No
|958,289
|1RB1RZ_0LC1RB_0LE0LD_1LE1LD_0RF0LC_0RG1RF_1RD0RA ([https://bbchallenge.org/1RB1RZ_0LC1RB_0LE0LD_1LE1LD_0RF0LC_0RG1RF_1RD0RA bbch])
|10 ↑↑ 36.26
|-
|27xxxx
|@stokastic
|Yes
|No
|1,052,946
|1RB0RG_1LC1LB_0RE0LD_0LC1RF_0RA1RE_0LF0LB_1RF1RZ ([https://bbchallenge.org/1RB0RG_1LC1LB_0RE0LD_0LC1RF_0RA1RE_0LF0LB_1RF1RZ bbch])
|10 ↑↑ 63.56
|-
|28xxxx
|@stokastic
|Yes
|No
|956,935
|TBD
|TBD
|-
|29xxxx
|@stokastic
|Yes
|No
|1,052,415
|TBD
|TBD
|-
|30xxxx
|@stokastic
|Yes
|No
|1,032,095
|TBD
|TBD
|-
|31xxxx
|@stokastic
|Yes
|No
|1,436,970
|TBD
|TBD
|-
|32xxxx
|@stokastic
|Yes
|No
|1,036,950
|TBD
|TBD
|-
|33xxxx
|@stokastic
|Yes
|No
|1,432,081
|TBD
|TBD
|-
|34xxxx
|@stokastic
|Yes
|No
|1,032,970
|TBD
|TBD
|-
|35xxxx
|rowspan="5"|Terry Ligocki
|Yes
|No
|1,437,841
|TBD
|TBD
|rowspan="5"|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|36xxxx
|Yes
|Yes
|798,364
|{{TM|1RB1LD_0LC1LE_1RD1LB_1RD0RA_1LB0RF_0RG1RE_1RZ0RA}}
|10 ↑↑ 26.82
|-
|37xxxx
|Yes
|Yes
|1,098,681
|{{TM|1RB0LA_1RC0LB_1RD0RF_1LE0RC_1LA0LD_1RC1RG_1RF1RZ}}
|10 ↑↑ 108.77
|-
|38xxxx
|Yes
|Yes
|801,308
|{{TM|1RB1RZ_1RC1RA_1RD0RB_1LE0RC_1LF0LD_1RG0LF_1RC0LG}}
|10 ↑↑ 108.77
|-
|39xxxx
|Yes
|Yes
|1,093,938
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RD0LA_1RF0RA_0RG0LA_1RB1RZ}}
|10 ↑↑ 192.67
|-
|40xxxx
| rowspan="6" |Andrew Ducharme
|Yes
|Yes
|730,310
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LF_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
| rowspan="6" |[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|41xxxx
|No
|No
|TBD
|TBD
|TBD
|-
|42xxxx
|No
|No
|TBD
|TBD
|TBD
|-
|43xxxx
|Yes
|Yes
|817,332
|{{TM|1RB0LE_1RC1RA_1RD0RG_1LA1RZ_1RA1LF_1LA0LE_0RF1RG}}
|10 ↑↑ 93.81
|-
|44xxxx
|Yes
|Yes
|729,686
|{{TM|1RB1LC_1RC0RC_1RD1LA_0RE1RF_1LC0LG_1LA1LE_1RZ1LF}}
|10 ↑↑ 76.36
|-
|45xxxx
|Yes
|Yes
|812,973
|{{TM|1RB0RE_0RC1LC_0LD1LF_1LE0LG_1RA0RC_0LB1LA_1LB1RZ}}
|10 ↑↑ 114.57
|-
|49xxxx
|Tobiáš Brichta
|No
|No
|TBD
|TBD
|TBD
|[https://drive.google.com/drive/folders/1-csgJ5uSIX3SKlqTkSnhkUuEYLKgCw81 Google Drive folder]
|-
|500xxx
|@prurq
|Yes
|No
|TBD
|TBD
|TBD
|[https://drive.google.com/drive/folders/145H4sT4F9KJYGSrlIETZdBOIMR7krLQm Google Drive folder]
|-
|60xxxx
|rowspan="3"|@gerbil5709
|Yes
|No
|TBD
|TBD
|TBD
| rowspan="3" |[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing Google Drive folder]
|-
|61xxxx
|No
|No
|TBD
|TBD
|TBD
|-
|62xxxx
|No
|No
|TBD
|TBD
|TBD
|-
|69xxxx
|@poppuncher
|Yes
|No
|TBD
|{{TM|1RB0LG_0RC1RZ_1LD0LA_1RE1LE_1LC1RF_0RE0RA_0RF1LG}}
|10 ↑↑ 133.85
|[https://drive.google.com/drive/folders/1KlCZqXxqVPuBPkDcCBocuMPA8paq9b8P?usp=drive_link Google Drive folder]
|-
|70xxxx
|@hipparcos
|Yes
|Yes
|798,304
|
{{TM|1RB0LF_1RC1LE_0RD1RA_1RE1RG_0LA1LB_1LE1RG_0RC1RZ}} 
{{TM|1RB0LF_1LC1LE_1RE0LD_0LC0LA_1LB1RA_0LG0RC_1RZ0LA}}
|
10 ↑↑ 33.81 
10 ↑↑ 26.63
|[https://github.com/jhuang97/bb7x2/releases/tag/70xxxx Github release]
|-
|71xxxx
|@hipparcos
|No
|No
|TBD
|TBD
|TBD
|
|-
|75xxxx
|Terry Ligocki
|Yes
|Yes
|1,103,089
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_0RF0LF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|80xxxx
|@xnoobspeakable
|Yes
|No
|964,396
|TBD
|TBD
| rowspan="2" |[https://drive.google.com/drive/folders/1TpuEC7KottEmvsFnCREugnlVMPaY5ZHi?usp=sharing Google Drive folder]
|-
|81xxxx
|@xnoobspeakable
|No
|No
|TBD
|TBD
|TBD
|-
|
85xxxx - 
9xxxxx
|Terry Ligocki
|Yes
|Yes
|13,396,923
|{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ}}
|10 ↑↑ 286.17
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|}
[[Category:BB Domain]]

BB(7)

2025-06-05T16:44:02Z

Hipparcos: /* Current Progress */ add link to 70xxxx results

The 7-state, 2-symbol Busy Beaver problem '''BB(7)''' is a mostly unexplored domain with only preliminary information.

The current BB(7) champion is {{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}} discovered by Pavel Kropitz in 2025 proving the lower bound:<math display="block">S(7) > \Sigma(7) > 2 \uparrow^{11} 2 \uparrow^{11} 3</math>

== History ==
Before 2025, the only known BB(7) champions were produced by hand, not by search. Example, Milton Green designed a machine in 1964 that had [[sigma score]] 22,961 and Wythagoras modified a BB(6) champion in 2014 to produce a machine that had sigma score <math>> 10 \uparrow\uparrow 5</math>.

In May 2025, mxdys shared [https://github.com/ccz181078/TM C++ code] that breaks up the BB(7) enumeration into 1 million subtasks which each run for about 2 minutes and leave ~100 holdouts each. Various folks on Discord have been investigating different sections of this domain to search for champions.

== Top Halters ==
Based on limited search through a subset of the 1 million subtasks from mxdys's code, the top 20 scoring known machines are:
{| class="wikitable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|Pavel Kropitz
|-
|{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ}}
|10 ↑↑ 286.17
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC0RA_1RD0RC_1LE1LD_1LA0LF_0LA0LG_1RZ0RD}}
|10 ↑↑ 246.32
|@Iijil
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RA0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LG_1RF0RG_0RA0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RG0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LF0RF_0RA1RE_1RZ0RE}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LF0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_1LG1RE_1LF0RF_0RA1RE_1RZ0RA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_1LG1RE_1LD0RF_0RA1RE_1RZ0RA}}
|10 ↑↑ 188.28
|@XnoobSpeakable, @Peacemaker II
|-
|{{TM|1RB0LG_0RC1RZ_1LD0LA_1RE1LE_1LC1RF_0RE0RA_0RF1LG}}
|10 ↑↑ 133
|@poppuncher
|-
|{{TM|1RB1RZ_1RC0RF_1LD1RB_1RG0LE_1LD0RA_1RE0LD_0RC1LF}}
|10 ↑↑ 129.24
|@Iijil
|-
|{{TM|1RB1LF_1RC1RA_1LD0LD_1LA1LE_0LA0LD_1LG0RF_0LE1RZ}}
|10 ↑↑ 116.97
|Terry Ligocki
|-
|{{TM|1RB0RD_1RC0LA_0LA0LE_1RE1RZ_1RF0RA_1LG0LE_1LC0LG}}
|10 ↑↑ 116.05
|
|-
|{{TM|1RB0RD_1RC0RA_0RD1LD_0LE1LF_1LA0LG_0LC1LB_1LC1RZ}}
|10 ↑↑ 115.52
|@prurq
|-
|{{TM|1RB0RE_1LC0LA_1LD0LC_0LE0LA_1RF0RG_1RD0LE_1RA1RZ}}
|10 ↑↑ 114.60
|Shawn Ligocki
|-
|{{TM|1RB0RE_0RC1LC_0LD1LF_1LE0LG_1RA0RC_0LB1LA_1LB1RZ}}
|10 ↑↑ 114.57
|Andrew Ducharme
|-
|{{TM|1RB0RG_1LC0LE_1LD0LB_1RB1RE_0RA1RF_0RD1RC_1RD1RZ}}
|10 ↑↑ 113.37
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC1RA_1RD0RG_1LA1RZ_1RA1LF_1LA0LE_0RF1RG}}
|10 ↑↑ 93.81
|Andrew Ducharme
|}
The top 20 known halters with unique scores are:
{| class="wikitable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|Pavel Kropitz
|-
|{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ}}
|10 ↑↑ 286.17
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC0RA_1RD0RC_1LE1LD_1LA0LF_0LA0LG_1RZ0RD}}
|10 ↑↑ 246.32
|@Iijil
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RA0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LG_0RC1RZ_1LD0LA_1RE1LE_1LC1RF_0RE0RA_0RF1LG}}
|10 ↑↑ 133
|@poppuncher
|-
|{{TM|1RB1RZ_1RC0RF_1LD1RB_1RG0LE_1LD0RA_1RE0LD_0RC1LF}}
|10 ↑↑ 129.24
|@Iijil
|-
|{{TM|1RB1LF_1RC1RA_1LD0LD_1LA1LE_0LA0LD_1LG0RF_0LE1RZ}}
|10 ↑↑ 116.97
|Terry Ligocki
|-
|{{TM|1RB0RD_1RC0LA_0LA0LE_1RE1RZ_1RF0RA_1LG0LE_1LC0LG}}
|10 ↑↑ 116.05
|
|-
|{{TM|1RB0RD_1RC0RA_0RD1LD_0LE1LF_1LA0LG_0LC1LB_1LC1RZ}}
|10 ↑↑ 115.52
|@prurq
|-
|{{TM|1RB0RE_1LC0LA_1LD0LC_0LE0LA_1RF0RG_1RD0LE_1RA1RZ}}
|10 ↑↑ 114.60
|Shawn Ligocki
|-
|{{TM|1RB0RE_0RC1LC_0LD1LF_1LE0LG_1RA0RC_0LB1LA_1LB1RZ}}
|10 ↑↑ 114.57
|Andrew Ducharme
|-
|{{TM|1RB0RG_1LC0LE_1LD0LB_1RB1RE_0RA1RF_0RD1RC_1RD1RZ}}
|10 ↑↑ 113.37
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC1RA_1RD0RG_1LA1RZ_1RA1LF_1LA0LE_0RF1RG}}
|10 ↑↑ 93.81
|Andrew Ducharme
|-
|{{TM|1RB0RF_1LC0LD_1RC0LB_1LE1RG_1RA1RE_1RD0RD_0RA1RZ}}
|10 ↑↑ 93.78
|Terry Ligocki
|-
|{{TM|1RB1LB_1LC1RE_1RD1RC_0RE0RD_1LF0RB_1LF1LG_1RZ0LA}}
|10 ↑↑ 86.40
|Terry Ligocki
|-
|{{TM|1RB1LC_1RC0LG_1RD0RG_0LE0RA_1LC0LF_0LD1LF_1RZ1RA}}
|10 ↑↑ 82.44
|Terry Ligocki
|-
|{{TM|1RB1LG_1RC0LA_1LD0RF_0LE0LD_1RE0RB_0LB1LF_1RZ1LC}}
|10 ↑↑ 80.18
|Andrew Ducharme
|-
|{{TM|1RB1LC_1RC0RC_1RD1LA_0RE1RF_1LC0LG_1LA1LE_1RZ1LF}}
|10 ↑↑ 76.36
|Andrew Ducharme
|-
|{{TM|1RB0LD_1RC0RF_0RD1RA_1LE0RB_0LA0LB_1RA1RG_0RA1RZ}}
|10 ↑↑ 64.03
|Terry Ligocki
|}

== Current Progress ==
This is a summary of the 1 million subtasks from mxdys's code that have been processed, including further processing by Shawn Ligocki's linear rule code ("TBD" = "To Be Determined", "TBE" = "To Be Entered"):
{| class="wikitable defaultleft"
!rowspan="2"|Task range
!rowspan="2"|Done by
!colspan="2"|Completed
!rowspan="2"|# holdouts
!rowspan="2"|Maximum Score TM
!rowspan="2"|~Sigma
!rowspan="2"|Source
|-
!enumeration
!linear rule
|-
|00xxxx
|@Iijil
|Yes
|Yes
|728,495
|{{TM|1RB0RF_1RC1LF_0RD0RD_1LE0LB_1RA1RZ_1LG1RA_1LD0RC}}
|10 ↑↑ 46
| rowspan="10" |[https://drive.google.com/drive/folders/1wniwrAuvsHfkvro8Tg65WAMNZEuIekzD Google Drive folder]
|-
|01xxxx
|@Iijil
|Yes
|Yes
|1,056,253
|TBD
|TBD
|-
|02xxxx
|@Iijil
|Yes
|No
|963,486
|TBD
|TBD
|-
|03xxxx
|@Iijil
|Yes
|No
|1,052,504
|TBD
|TBD
|-
|04xxxx
|@Iijil
|Yes
|No
|955,711
|TBD
|TBD
|-
|05xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|06xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|07xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|08xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|09xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|13xxxx
|Shawn Ligocki
|Yes
|Yes
|1,192,442
|{{TM|1RB0RE_1LC0LA_1LD0LC_0LE0LA_1RF0RG_1RD0LE_1RA1RZ}}
|10 ↑↑ 114.60
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|20xxxx - 
21xxxx
|@C7X
|Yes
|No
|TBD
|TBD
|TBD
|[https://drive.google.com/drive/folders/11iGTKsvu2Y7aFrwOcWS1LYvcN6i_7-JM?usp=sharing Google Drive folder]
|-
|243308
|@uni
|Yes
|No
|TBE
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|[https://discord.com/channels/960643023006490684/1369339127652159509/1373660959960469545 Discord post]
|-
|25xxxx
|@stokastic
|Yes
|No
|1,056,591
|{{TM|1RB1RZ_1LC0LE_0LD0LC_0RE1LB_1RF0RG_0LD1RB_1RD1RA}}
|10↑↑31.33
| rowspan="10" |[https://drive.google.com/drive/folders/16_qIdWWD-wolj6zURB5ZSbY-otI4zoUF?usp=sharing Google Drive folder]
|-
|26xxxx
|@stokastic
|Yes
|No
|958,289
|TBD
|TBD
|-
|27xxxx
|@stokastic
|Yes
|No
|1,052,946
|TBD
|TBD
|-
|28xxxx
|@stokastic
|Yes
|No
|956,935
|TBD
|TBD
|-
|29xxxx
|@stokastic
|Yes
|No
|1,052,415
|TBD
|TBD
|-
|30xxxx
|@stokastic
|Yes
|No
|1,032,095
|TBD
|TBD
|-
|31xxxx
|@stokastic
|Yes
|No
|1,436,970
|TBD
|TBD
|-
|32xxxx
|@stokastic
|Yes
|No
|1,036,950
|TBD
|TBD
|-
|33xxxx
|@stokastic
|Yes
|No
|1,432,081
|TBD
|TBD
|-
|34xxxx
|@stokastic
|Yes
|No
|1,032,970
|TBD
|TBD
|-
|
35xxxx - 
38xxxx
|Terry Ligocki
|No
|No
|TBD
|TBD
|TBD
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|39xxxx
|Terry Ligocki
|Yes
|Yes
|1,093,938
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RD0LA_1RF0RA_0RG0LA_1RB1RZ}}
|10 ↑↑ 193
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|40xxxx
| rowspan="6" |Andrew Ducharme
|No
|No
|TBD
|TBD
|TBD
| rowspan="6" |[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|41xxxx
|No
|No
|TBD
|TBD
|TBD
|-
|42xxxx
|No
|No
|TBD
|TBD
|TBD
|-
|43xxxx
|Yes
|Yes
|817,332
|{{TM|1RB0LE_1RC1RA_1RD0RG_1LA1RZ_1RA1LF_1LA0LE_0RF1RG}}
|10 ↑↑ 93.81
|-
|44xxxx
|Yes
|Yes
|729,686
|{{TM|1RB1LC_1RC0RC_1RD1LA_0RE1RF_1LC0LG_1LA1LE_1RZ1LF}}
|10 ↑↑ 76.36
|-
|45xxxx
|Yes
|Yes
|812,973
|{{TM|1RB0RE_0RC1LC_0LD1LF_1LE0LG_1RA0RC_0LB1LA_1LB1RZ}}
|10 ↑↑ 114.57
|-
|49xxxx
|Tobiáš Brichta
|No
|No
|TBD
|TBD
|TBD
|[https://drive.google.com/drive/folders/1-csgJ5uSIX3SKlqTkSnhkUuEYLKgCw81 Google Drive folder]
|-
|500xxx
|@prurq
|Yes
|No
|TBD
|TBD
|TBD
|[https://drive.google.com/drive/folders/145H4sT4F9KJYGSrlIETZdBOIMR7krLQm Google Drive folder]
|-
|60xxxx
|@gerbil5709
|Yes
|No
|TBD
|TBD
|TBD
| rowspan="2" |[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing Google Drive folder]
|-
|61xxxx
|@gerbil5709
|No
|No
|TBD
|TBD
|TBD
|-
|69xxxx
|@poppuncher
|Yes
|No
|TBD
|{{TM|1RB0LG_0RC1RZ_1LD0LA_1RE1LE_1LC1RF_0RE0RA_0RF1LG}}
|10 ↑↑ 133
|[https://drive.google.com/drive/folders/1KlCZqXxqVPuBPkDcCBocuMPA8paq9b8P?usp=drive_link Google Drive folder]
|-
|70xxxx
|@hipparcos
|Yes
|Yes
|798,304
|{{TM|1RB0LF_1RC1LE_0RD1RA_1RE1RG_0LA1LB_1LE1RG_0RC1RZ}} 
{{TM|1RB0LF_1LC1LE_1RE0LD_0LC0LA_1LB1RA_0LG0RC_1RZ0LA}}
|10↑↑33.81 
10↑↑26.63
|[https://github.com/jhuang97/bb7x2/releases/tag/70xxxx Github release]
|-
|75xxxx
|Terry Ligocki
|Yes
|Yes
|1,103,089
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_0RF0LF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|80xxxx
|@xnoobspeakable
|Yes
|No
|964,396
|TBD
|TBD
| rowspan="2" |[https://drive.google.com/drive/folders/1TpuEC7KottEmvsFnCREugnlVMPaY5ZHi?usp=sharing Google Drive folder]
|-
|81xxxx
|@xnoobspeakable
|No
|No
|TBD
|TBD
|TBD
|-
|
85xxxx - 
9xxxxx
|Terry Ligocki
|Yes
|Yes
|13,396,923
|
{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ}} 
{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RA0LG_1RB1LG}} 
{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA}} 
{{TM|1RB1LF_1RC1RA_1LD0LD_1LA1LE_0LA0LD_1LG0RF_0LE1RZ}} 
{{TM|1RB0RG_1LC0LE_1LD0LB_1RB1RE_0RA1RF_0RD1RC_1RD1RZ}}
|
10 ↑↑ 286 
10 ↑↑ 193 
10 ↑↑ 188 
10 ↑↑ 117 
10 ↑↑ 113
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|}
[[Category:BB Domain]]

BB(7)

2025-06-05T07:22:50Z

Hipparcos: /* Current Progress */ 70xxxx result update

The 7-state, 2-symbol Busy Beaver problem '''BB(7)''' is a mostly unexplored domain with only preliminary information.

The current BB(7) champion is {{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}} discovered by Pavel Kropitz in 2025 proving the lower bound:<math display="block">S(7) > \Sigma(7) > 2 \uparrow^{11} 2 \uparrow^{11} 3</math>

== History ==
Before 2025, the only known BB(7) champions were produced by hand, not by search. Example, Milton Green designed a machine in 1964 that had [[sigma score]] 22,961 and Wythagoras modified a BB(6) champion in 2014 to produce a machine that had sigma score <math>> 10 \uparrow\uparrow 5</math>.

In May 2025, mxdys shared [https://github.com/ccz181078/TM C++ code] that breaks up the BB(7) enumeration into 1 million subtasks which each run for about 2 minutes and leave ~100 holdouts each. Various folks on Discord have been investigating different sections of this domain to search for champions.

== Top Halters ==
Based on limited search through a subset of the 1 million subtasks from mxdys's code, the top 20 scoring known machines are:
{| class="wikitable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|Pavel Kropitz
|-
|{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ}}
|10 ↑↑ 286.17
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC0RA_1RD0RC_1LE1LD_1LA0LF_0LA0LG_1RZ0RD}}
|10 ↑↑ 246.32
|@Iijil
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RA0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LG_1RF0RG_0RA0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RG0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LF0RF_0RA1RE_1RZ0RE}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LF0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_1LG1RE_1LF0RF_0RA1RE_1RZ0RA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_1LG1RE_1LD0RF_0RA1RE_1RZ0RA}}
|10 ↑↑ 188.28
|@XnoobSpeakable, @Peacemaker II
|-
|{{TM|1RB0LG_0RC1RZ_1LD0LA_1RE1LE_1LC1RF_0RE0RA_0RF1LG}}
|10 ↑↑ 133
|@poppuncher
|-
|{{TM|1RB1RZ_1RC0RF_1LD1RB_1RG0LE_1LD0RA_1RE0LD_0RC1LF}}
|10 ↑↑ 129.24
|@Iijil
|-
|{{TM|1RB1LF_1RC1RA_1LD0LD_1LA1LE_0LA0LD_1LG0RF_0LE1RZ}}
|10 ↑↑ 116.97
|Terry Ligocki
|-
|{{TM|1RB0RD_1RC0LA_0LA0LE_1RE1RZ_1RF0RA_1LG0LE_1LC0LG}}
|10 ↑↑ 116.05
|
|-
|{{TM|1RB0RD_1RC0RA_0RD1LD_0LE1LF_1LA0LG_0LC1LB_1LC1RZ}}
|10 ↑↑ 115.52
|@prurq
|-
|{{TM|1RB0RE_1LC0LA_1LD0LC_0LE0LA_1RF0RG_1RD0LE_1RA1RZ}}
|10 ↑↑ 114.60
|Shawn Ligocki
|-
|{{TM|1RB0RE_0RC1LC_0LD1LF_1LE0LG_1RA0RC_0LB1LA_1LB1RZ}}
|10 ↑↑ 114.57
|Andrew Ducharme
|-
|{{TM|1RB0RG_1LC0LE_1LD0LB_1RB1RE_0RA1RF_0RD1RC_1RD1RZ}}
|10 ↑↑ 113.37
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC1RA_1RD0RG_1LA1RZ_1RA1LF_1LA0LE_0RF1RG}}
|10 ↑↑ 93.81
|Andrew Ducharme
|}
The top 20 known halters with unique scores are:
{| class="wikitable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|Pavel Kropitz
|-
|{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ}}
|10 ↑↑ 286.17
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC0RA_1RD0RC_1LE1LD_1LA0LF_0LA0LG_1RZ0RD}}
|10 ↑↑ 246.32
|@Iijil
|-
|{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RA0LG_1RB1LG}}
|10 ↑↑ 192.67
|Terry Ligocki
|-
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|Terry Ligocki
|-
|{{TM|1RB0LG_0RC1RZ_1LD0LA_1RE1LE_1LC1RF_0RE0RA_0RF1LG}}
|10 ↑↑ 133
|@poppuncher
|-
|{{TM|1RB1RZ_1RC0RF_1LD1RB_1RG0LE_1LD0RA_1RE0LD_0RC1LF}}
|10 ↑↑ 129.24
|@Iijil
|-
|{{TM|1RB1LF_1RC1RA_1LD0LD_1LA1LE_0LA0LD_1LG0RF_0LE1RZ}}
|10 ↑↑ 116.97
|Terry Ligocki
|-
|{{TM|1RB0RD_1RC0LA_0LA0LE_1RE1RZ_1RF0RA_1LG0LE_1LC0LG}}
|10 ↑↑ 116.05
|
|-
|{{TM|1RB0RD_1RC0RA_0RD1LD_0LE1LF_1LA0LG_0LC1LB_1LC1RZ}}
|10 ↑↑ 115.52
|@prurq
|-
|{{TM|1RB0RE_1LC0LA_1LD0LC_0LE0LA_1RF0RG_1RD0LE_1RA1RZ}}
|10 ↑↑ 114.60
|Shawn Ligocki
|-
|{{TM|1RB0RE_0RC1LC_0LD1LF_1LE0LG_1RA0RC_0LB1LA_1LB1RZ}}
|10 ↑↑ 114.57
|Andrew Ducharme
|-
|{{TM|1RB0RG_1LC0LE_1LD0LB_1RB1RE_0RA1RF_0RD1RC_1RD1RZ}}
|10 ↑↑ 113.37
|Terry Ligocki
|-
|{{TM|1RB0LE_1RC1RA_1RD0RG_1LA1RZ_1RA1LF_1LA0LE_0RF1RG}}
|10 ↑↑ 93.81
|Andrew Ducharme
|-
|{{TM|1RB0RF_1LC0LD_1RC0LB_1LE1RG_1RA1RE_1RD0RD_0RA1RZ}}
|10 ↑↑ 93.78
|Terry Ligocki
|-
|{{TM|1RB1LB_1LC1RE_1RD1RC_0RE0RD_1LF0RB_1LF1LG_1RZ0LA}}
|10 ↑↑ 86.40
|Terry Ligocki
|-
|{{TM|1RB1LC_1RC0LG_1RD0RG_0LE0RA_1LC0LF_0LD1LF_1RZ1RA}}
|10 ↑↑ 82.44
|Terry Ligocki
|-
|{{TM|1RB1LG_1RC0LA_1LD0RF_0LE0LD_1RE0RB_0LB1LF_1RZ1LC}}
|10 ↑↑ 80.18
|Andrew Ducharme
|-
|{{TM|1RB1LC_1RC0RC_1RD1LA_0RE1RF_1LC0LG_1LA1LE_1RZ1LF}}
|10 ↑↑ 76.36
|Andrew Ducharme
|-
|{{TM|1RB0LD_1RC0RF_0RD1RA_1LE0RB_0LA0LB_1RA1RG_0RA1RZ}}
|10 ↑↑ 64.03
|Terry Ligocki
|}

== Current Progress ==
This is a summary of the 1 million subtasks from mxdys's code that have been processed, including further processing by Shawn Ligocki's linear rule code ("TBD" = "To Be Determined", "TBE" = "To Be Entered"):
{| class="wikitable defaultleft"
!rowspan="2"|Task range
!rowspan="2"|Done by
!colspan="2"|Completed
!rowspan="2"|# holdouts
!rowspan="2"|Maximum Score TM
!rowspan="2"|~Sigma
!rowspan="2"|Source
|-
!enumeration
!linear rule
|-
|00xxxx
|@Iijil
|Yes
|Yes
|728,495
|{{TM|1RB0RF_1RC1LF_0RD0RD_1LE0LB_1RA1RZ_1LG1RA_1LD0RC}}
|10 ↑↑ 46
| rowspan="10" |[https://drive.google.com/drive/folders/1wniwrAuvsHfkvro8Tg65WAMNZEuIekzD Google Drive folder]
|-
|01xxxx
|@Iijil
|Yes
|Yes
|1,056,253
|TBD
|TBD
|-
|02xxxx
|@Iijil
|Yes
|No
|963,486
|TBD
|TBD
|-
|03xxxx
|@Iijil
|Yes
|No
|1,052,504
|TBD
|TBD
|-
|04xxxx
|@Iijil
|Yes
|No
|955,711
|TBD
|TBD
|-
|05xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|06xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|07xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|08xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|09xxxx
|@Iijil
|Yes
|No
|TBD
|TBD
|TBD
|-
|13xxxx
|Shawn Ligocki
|Yes
|Yes
|1,192,442
|{{TM|1RB0RE_1LC0LA_1LD0LC_0LE0LA_1RF0RG_1RD0LE_1RA1RZ}}
|10 ↑↑ 114.60
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|20xxxx - 
21xxxx
|@C7X
|Yes
|No
|TBD
|TBD
|TBD
|[https://drive.google.com/drive/folders/11iGTKsvu2Y7aFrwOcWS1LYvcN6i_7-JM?usp=sharing Google Drive folder]
|-
|243308
|@uni
|Yes
|No
|TBE
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|[https://discord.com/channels/960643023006490684/1369339127652159509/1373660959960469545 Discord post]
|-
|25xxxx
|@stokastic
|Yes
|No
|1,056,591
|{{TM|1RB1RZ_1LC0LE_0LD0LC_0RE1LB_1RF0RG_0LD1RB_1RD1RA}}
|10↑↑31.33
| rowspan="10" |[https://drive.google.com/drive/folders/16_qIdWWD-wolj6zURB5ZSbY-otI4zoUF?usp=sharing Google Drive folder]
|-
|26xxxx
|@stokastic
|Yes
|No
|958,289
|TBD
|TBD
|-
|27xxxx
|@stokastic
|Yes
|No
|1,052,946
|TBD
|TBD
|-
|28xxxx
|@stokastic
|Yes
|No
|956,935
|TBD
|TBD
|-
|29xxxx
|@stokastic
|Yes
|No
|1,052,415
|TBD
|TBD
|-
|30xxxx
|@stokastic
|Yes
|No
|1,032,095
|TBD
|TBD
|-
|31xxxx
|@stokastic
|Yes
|No
|1,436,970
|TBD
|TBD
|-
|32xxxx
|@stokastic
|Yes
|No
|1,036,950
|TBD
|TBD
|-
|33xxxx
|@stokastic
|Yes
|No
|1,432,081
|TBD
|TBD
|-
|34xxxx
|@stokastic
|Yes
|No
|1,032,970
|TBD
|TBD
|-
|
35xxxx - 
38xxxx
|Terry Ligocki
|No
|No
|TBD
|TBD
|TBD
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|39xxxx
|Terry Ligocki
|Yes
|Yes
|1,093,938
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RD0LA_1RF0RA_0RG0LA_1RB1RZ}}
|10 ↑↑ 193
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|40xxxx
| rowspan="6" |Andrew Ducharme
|No
|No
|TBD
|TBD
|TBD
| rowspan="6" |[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|41xxxx
|No
|No
|TBD
|TBD
|TBD
|-
|42xxxx
|No
|No
|TBD
|TBD
|TBD
|-
|43xxxx
|Yes
|Yes
|817,332
|{{TM|1RB0LE_1RC1RA_1RD0RG_1LA1RZ_1RA1LF_1LA0LE_0RF1RG}}
|10 ↑↑ 93.81
|-
|44xxxx
|Yes
|Yes
|729,686
|{{TM|1RB1LC_1RC0RC_1RD1LA_0RE1RF_1LC0LG_1LA1LE_1RZ1LF}}
|10 ↑↑ 76.36
|-
|45xxxx
|Yes
|Yes
|812,973
|{{TM|1RB0RE_0RC1LC_0LD1LF_1LE0LG_1RA0RC_0LB1LA_1LB1RZ}}
|10 ↑↑ 114.57
|-
|49xxxx
|Tobiáš Brichta
|No
|No
|TBD
|TBD
|TBD
|[https://drive.google.com/drive/folders/1-csgJ5uSIX3SKlqTkSnhkUuEYLKgCw81 Google Drive folder]
|-
|500xxx
|@prurq
|Yes
|No
|TBD
|TBD
|TBD
|[https://drive.google.com/drive/folders/145H4sT4F9KJYGSrlIETZdBOIMR7krLQm Google Drive folder]
|-
|60xxxx
|@gerbil5709
|Yes
|No
|TBD
|TBD
|TBD
| rowspan="2" |[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing Google Drive folder]
|-
|61xxxx
|@gerbil5709
|No
|No
|TBD
|TBD
|TBD
|-
|69xxxx
|@poppuncher
|Yes
|No
|TBD
|{{TM|1RB0LG_0RC1RZ_1LD0LA_1RE1LE_1LC1RF_0RE0RA_0RF1LG}}
|10 ↑↑ 133
|[https://drive.google.com/drive/folders/1KlCZqXxqVPuBPkDcCBocuMPA8paq9b8P?usp=drive_link Google Drive folder]
|-
|70xxxx
|@hipparcos
|Yes
|Yes
|798,304
|{{TM|1RB0LF_1RC1LE_0RD1RA_1RE1RG_0LA1LB_1LE1RG_0RC1RZ}} 
{{TM|1RB0LF_1LC1LE_1RE0LD_0LC0LA_1LB1RA_0LG0RC_1RZ0LA}}
|10↑↑33.81 
10↑↑26.63
|TBE
|-
|75xxxx
|Terry Ligocki
|Yes
|Yes
|1,103,089
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_0RF0LF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|80xxxx
|@xnoobspeakable
|Yes
|No
|964,396
|TBD
|TBD
| rowspan="2" |[https://drive.google.com/drive/folders/1TpuEC7KottEmvsFnCREugnlVMPaY5ZHi?usp=sharing Google Drive folder]
|-
|81xxxx
|@xnoobspeakable
|No
|No
|TBD
|TBD
|TBD
|-
|
85xxxx - 
9xxxxx
|Terry Ligocki
|Yes
|Yes
|13,396,923
|
{{TM|1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ}} 
{{TM|1RB1RZ_1LC0RE_0LD1LB_1RE0LA_1RF0RG_0RA0LG_1RB1LG}} 
{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA}} 
{{TM|1RB1LF_1RC1RA_1LD0LD_1LA1LE_0LA0LD_1LG0RF_0LE1RZ}} 
{{TM|1RB0RG_1LC0LE_1LD0LB_1RB1RE_0RA1RF_0RD1RC_1RD1RZ}}
|
10 ↑↑ 286 
10 ↑↑ 193 
10 ↑↑ 188 
10 ↑↑ 117 
10 ↑↑ 113
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|}
[[Category:BB Domain]]

1RB2LC1RC 2LC---2RB 2LA0LB0RA

2025-04-07T06:04:46Z

Hipparcos: /* Timings */ change section title

{{machine|1RB2LC1RC_2LC---2RB_2LA0LB0RA}}{{unsolved|Does this TM halt? If so, how many steps does it take to halt?}}
{{TM|1RB2LC1RC_2LC---2RB_2LA0LB0RA|undecided}}

This is a [[BB(3,3)]] [[holdout]] which appears to [[probviously]] halt. If can be proven to halt, it will be the BB(3,3) champion, in terms of both steps and tape symbols. However, it could also turn out to be a probviously halting [[Cryptid]].

This is holdout #758 on Justin's 3x3 mugshots. After about 1.8 million steps and up to some relabelling, it is equivalent to holdout #153: {{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}. And if you start in state C it is a [[permutation]] of the same machine. Together, they simulate a complex set of Collatz-like rules with two decreasing parameters.

After active exploration on the #bb3x3 channel by LegionMammal and dyuan, LegionMammal found (and dyuan confirmed) a configuration A(1,c) (defined [https://discord.com/channels/960643023006490684/1259770474897080380/1259968221218607145 here]) which halts and for which a huge "wall" of previous A(1, c') values all reach it. This gives strong evidence that the TM probviosly halts since jumping over this wall is very "unlikely".

NOTE: As of 16 Jul 2024 there is a lot more active work on the #bb3x3 channel with LegionMammal and dyuan not reflected here.

== dyuan01's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1224457633176486041

<pre>
A_1(a, b, c) = 0^inf 1 2^a <C (22)^b (20)^c 0^inf
A_2(a, b, c) = 0^inf 1 2^a <A2 (22)^b (20)^c 0^inf
B(a, b) = 0^inf 1 2^a <B0 (20)^b 0^inf
</pre>

{| class="wikitable"
! From !! To
|-
| A1(0, b, 2n) || A2(1, b+2n+1, 0)
|-
| A1(0, b, 2n+1) || A1(1, 0, b+2n+3)
|-
| A1(m+1, b, 0) || A1(m, 0, b+2)
|-
| A1(m+1, b, n+1) || A2(m, b+1, n)
|-
| A2(0, b, 2n) || A1(2b+3, 0, 2n+1)
|-
| A2(0, b, 2n+1) || A2(2b+3, 2n+1, 0)
|-
| A2(m+1, b, 0) || B(m, b+2)
|-
| A2(m+1, b, n+1) || A1(m, b+2, n)
|-
| B(0, b) || Halt
|-
| B(m+1, 2n) || A2(m, 2n+1, 0)
|-
| B(m+1, 2n+1) || A1(m, 0, 2n+3)
|}
Starting from A1(0, 0, 1) (at step 2).

== savask's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254085725138190336

Let <code>(m, b, n) = A2(m, b, n) = 0^inf 1 2^m <A2 (22)^b (20)^n 0^inf</code>

<pre>
(0, b, n) -> (2b+2, 1, n) if n is even
-> (2b, 1, n+3) if n is odd

(1, b, 0) -> Halt

(2, b, 0) -> (0, b+3, 0) if b is even
-> (0, 1, b+5) if b is odd

(m, b, 0) -> (m-2, b+3, 0) if b is even
-> (m-3, 1, b+3) if b is odd

(1, b, n) -> (0, 1, n+b+2) if n is even
-> Halt if n is odd

(2, b, 1) -> Halt if b is even
-> (0, 1, b+5) if b is odd

(m, b, 1) -> (m-3, 1, b+3)

(m, b, n) -> (m-2, b+3, n-2)
</pre>

https://discord.com/channels/960643023006490684/1084047886494470185/1254306301786198116

<pre>
step (A2 0 b n) | even n = A2 (2*b+2) 1 n
| otherwise = A2 (2*b) 1 (n+3)
-- From now on m > 0
step (A2 1 b 0) = error $ "Halt A2 1 " ++ show b ++ " 0"
step (A2 2 b 0) | even b = A2 0 (b+3) 0
| otherwise = A2 0 1 (b+5)
step (A2 m b 0) | even b = A2 (m-2) (b+3) 0
| otherwise = A2 (m-3) 1 (b+3)
-- From now on n > 0
step (A2 1 b n) | even n = A2 0 1 (n+b+2)
| otherwise = error $ "Halt A2 1 " ++ show b ++ " " ++ show n
step (A2 2 b 1) | even b = error $ "Halt A2 2 " ++ show b ++ " 1"
| otherwise = A2 0 1 (b+5)
step (A2 m b 1) = A2 (m-3) 1 (b+3)
-- Here m > 1, n > 1
step (A2 m b n) = let d2 = (min m n) `div` 2 in A2 (m - 2*d2) (b + 3*d2) (n - 2*d2) -- Accelerated
</pre>

== Shawn's Rules ==
https://discord.com/channels/960643023006490684/1084047886494470185/1254307091863048264

We can reduce the set of rules from savask's list a bit by noticing that we can evaluate so that all rules end with c even:

<pre>
(0, b, 2c) -> (2b+2, 1, 2c)

(1, b, 0) -> Halt
(1, 2b, 2c) -> (0, 1, 2(b+c+1))
(1, 2b+1, 2c) -> (2, 1, 2(b+c+3))

(a, 2b, 0) -> (a-2, 2b+3, 0)
(2, 2b+1, 0) -> (0, 1, 2b+6)
(a, 2b+1, 0) -> (a-3, 1, 2b+4)

(a, b, c) -> (a-2, b+3, c-2)
</pre>

=== Phases ===
We can think of this going through two different phases. "Even Phase" (where <code>a</code> is even) and "Odd Phase" (where <code>a</code> is odd).

<pre>
Even Phase: a,c even:
(0, b, 2c) -> (2b+2, 1, 2c)
(2a+2, 2b, 0) -> (2a, 2b+3, 0)
(2, 2b+1, 0) -> (0, 1, 2(b+3))

To Odd Phase:
(2a+4, 2b+1, 0) -> (2a+1, 1, 2b+4)

Odd Phase: a odd, c even
To Halt:
(1, b, 0) -> Halt
(3, 2b, 0) -> (1, 2b+3, 0) -> Halt

To Even Phase:
(1, 2b, 2c+2) -> (0, 1, 2(b+c+2))
(1, 2b+1, 2c+2) -> (0, 1, 2b+2c+5) -> (2, 1, 2(b+c+4))

(2a+5, 2b, 0) -> (2a+3, 2b+3, 0) -> (2a, 1, 2b+6)
(2a+3, 2b+1, 0) -> (2a, 1, 2b+4)
</pre>

So the only way for this to halt is if it is in "Even Phase" and hits (2k+8, 2k+1, 0) or (4k+12, 4k+3, 0) (which will lead to (1, b, 0) or (3, 2b, 0) eventually).
If <code>a</code> is bigger or smaller, then "Odd Phase" will end going back to "Even Phase" again.

=== Repeated (0, b, 2c) ===

Let <math>f(n) = 3n+4</math>, then<math display="block">(0, b, 2c) \to (0, f(b), 2(c - b - 1))</math> Let<math display="block">h(n) = f^n(1) + 1 = 3^{n+1} - 1</math><math display="block">g(n) = \sum_{k=0}^{n-1} h(k) = \frac{3}{2} (3^n - 1) - n</math>

Then if <math>c > g(n)</math>:<math display="block">(0, 1, 2c) \to (0, f^n(1), 2 (c-g(n))) \to (2 h(n), 1, 2 (c-g(n)))</math>

=== Repeated (0, 1, 2c) ===
https://discord.com/channels/960643023006490684/1084047886494470185/1254635277020954705

Let <math>C(n) = (0, 1, 2n)</math> = <code>0^inf 1 <A2 22 (20)^2n 0^inf</code>

<math display="block">C(g(n) + 8k+1) \to C(g(n) + 8k+1 + n+9)</math><math display="block">\forall k: \frac{h(n) - 45}{65} < k < \frac{h(n) - 22}{38}</math>

Notably, when 8 divides (n+1) then this rule can potentially be applied repeatedly.

Ex: if n = 7, then we get:<math display="block">\forall k \in [101, 172]: C(3273 + 8k) \to C(3273 + 8(k+2))</math>

And we see this starting with <math>C(4137) = C(3273 + 8 \cdot 108)</math> which repeats this rule until we get to <math>C(4665) = C(3273 + 8 \cdot 174)</math>.

And as n gets way bigger, these ranges of repeat will increase exponentially.

== A(a, c) Rules and Timings ==

Let A(a, c) = A1(a, 0, c) = <code>0^∞ 1 2^a <C (20)^c 0^∞</code>, where A1(a, b, c) comes from dyuan01's rules. Then the TM satisfies the following rules once it reaches A(0, 1) after 2 steps. Note that rules (a) and (g) aren't actually reachable from the initial condition.

{| class="wikitable" style="text-align:left"
|+ Rules and associated step counts ([https://discord.com/channels/960643023006490684/1259770474897080380/1324065684677988505 source])
! !! style="text-align:left" | A(a, c) → !! Conditions !! Step count
|-
! style="text-align:right" | (a)
| A(a−c−1, 3c/2+2) || c ≤ a−1, c ≡ 0 (mod 2) || 3c2+8c+5
|-
! style="text-align:right" | (b)
| A(a−c−2, 3(c−1)/2+5) || c ≤ a−2, c ≡ 1 (mod 4) || (6c2+31c+37)/2
|-
! style="text-align:right" | (c)
| A(a−c−4, 3(c−1)/2+8) || c ≤ a−4, c ≡ 3 (mod 4) || 3c2+29c+65
|-
! style="text-align:right" | (d)
| Halt(3(c−1)/2+7) || c = a−3, c ≡ 3 (mod 4) || (6c2+43c+75)/2
|-
! style="text-align:right" | (e)
| A(3c+8, 1) || c = a−2, c ≡ 3 (mod 4) || (6c2+37c+63)/2
|-
! style="text-align:right" | (f)
| Halt(3(c−1)/2+4) || c = a−1, c ≡ 1 (mod 2) || 3c2+8c+6
|-
! style="text-align:right" | (g)
| Halt(a/2+c+4) || c ≥ a, a ≡ 0, c ≡ 0 (mod 2) || 3a2+5a+9c+24
|-
! style="text-align:right" | (h)
| A(1, a/2+c+2) || c ≥ a, a ≡ 0, c ≡ 1 (mod 2) || 3a2+3a+5c+11
|-
! style="text-align:right" | (i)
| A(3a, c−a+4) || c ≥ a, a ≡ 1, c ≡ 0 (mod 2) || 3a2−9a+14c+30
|-
! style="text-align:right" | (j)
| A(3a+2, c−a+1) || c ≥ a, a ≡ 1, c ≡ 1 (mod 2) || 3a2+5c+6
|}

== Equivalence to 1RB0LB0RC_2LC2LA1RA_1RA1LC--- ==
{{TM|1RB0LB0RC_2LC2LA1RA_1RA1LC---}}, #153, eventually becomes equivalent to this machine. As found by [https://discord.com/channels/960643023006490684/1259770474897080380/1260244842999709726 @Legion], after running the #153 machine for 1,790,901 steps, if one permutes the states A,C, and B and exchanges 1 for 2 and L for R, it has the same configuration as TM #758 after it has run 1,841,608 steps.