BusyBeaverWiki - User contributions [en]

Antihydra

2026-03-23T15:07:30Z

Isokate: Removed ending sentence and image for being misleading. Showing the antihydra walk is mathematically random would not imply that it is "probabilistically undecidable". Undecidable is a much stronger condition

{{machine|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA}}{{unsolved|Does Antihydra run forever?}}
{{TM|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA|undecided}}, called '''Antihydra''', is a [[BB(6)]] [[Cryptid]]. Its pseudo-random behaviour was first reported [https://discord.com/channels/960643023006490684/1026577255754903572/1256223215206924318 on Discord] by mxdys on 28 June 2024, and Racheline discovered the high-level rules soon after. It was named after the 2-state, 5-symbol [[Turing machine]] called [[Hydra]] for sharing many similarities to it.<ref>[https://discord.com/channels/960643023006490684/960643023530762341/1257053002859286701 Discord conversation where the machine was named]</ref>

Antihydra 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|10.1017/S0017089508004655}}</ref> (Corollary 4).
<table style="margin: auto; text-align: center;"><tr><td style="width: 200px;">[[File:Antihydra-depiction.png|200px]]<br>Artistic depiction of Antihydra by Jadeix</td><td>      </td><td>
{|class="wikitable" style="margin-left: auto; margin-right: auto;"
! !!0!!1
|-
!A
|1RB
|1RA
|-
!B
|0LC
|1LE
|-
!C
|1LD
|1LC
|-
!D
|1LA
|0LB
|-
!E
|1LF
|1RE
|-
!F
| ---
|0RA
|}
The transition table of Antihydra.
</td><td>      </td><td>[[File:Antihydra_state_diagram.png|200x200px]]
State diagram of Antihydra
</td><td>      </td><td style="width: 220px;">[[File:Antihydra award.jpg|220px]]<br>A community trophy - to be awarded to the first person or group who solves the Antihydra problem
</td><td>      </td><td>[[File:Nico-BB-vs-Antihydra.jpg|thumb|A brave busy beaver confronts the dreaded Antihydra. Copyright [https://www.nicoroper.com/ Nico Roper].]]</td></tr></table>
== Analysis ==
Let <math>A(a,b):=0^\infty\;1^a\;0\;1^b\;\textrm{E}\textrm{>}\;0^\infty</math>. Then,<ref name="bl">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>
<math display="block">\begin{array}{|lll|}\hline
A(a,2b)& \xrightarrow{2a+3b^2+12b+11}& A(a+2,3b+2),\\
A(0,2b+1)&\xrightarrow{3b^2+9b-1}& 0^\infty\;\textrm{<}\textrm{F}\;110\;1^{3b}\;0^\infty,\\
A(a+1,2b+1)&\xrightarrow{3b^2+12b+5}& A(a,3b+3).\\\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\;1^m\;\textrm{E}\textrm{>}\;0\;1^n\;0^\infty</math>. The configuration after two steps is <math>0\;1^{m-1}\;0\;\textrm{A}\textrm{>}\;1^{n+1}\;0^\infty</math>. We note the following shift rule:
<math display="block">\begin{array}{|c|}\hline\textrm{A}\textrm{>}\;1^s\xrightarrow{s}1^s\;\textrm{A}\textrm{>}\\\hline\end{array}</math>
As a result, we get <math>0\;1^{m-1}\;0\;1^{n+1}\;\textrm{A}\textrm{>}\;0^\infty</math> after <math>n+1</math> steps. Advancing two steps produces <math>0\;1^{m-1}\;0\;1^{n+2}\;\textrm{<}\textrm{C}\;0^\infty</math>. A second shift rule is useful here:
<math display="block">\begin{array}{|c|}\hline1^s\;\textrm{<}\textrm{C}\xrightarrow{s}\textrm{<}\textrm{C}\;1^s\\\hline\end{array}</math>
This allows us to reach <math>0\;1^{m-1}\;0\;\textrm{<}\textrm{C}\;1^{n+2}\;0^\infty</math> in <math>n+2</math> steps. Moving five more steps gets us to <math>0\;1^{m-2}\;\textrm{E}\textrm{>}\;0\;1^{n+3}\;0^\infty</math>, which is the same configuration as <math>P(m-2,n+3)</math>. Accounting for the head movement creates the condition that <math>m\ge 4</math>. In summary:
<math display="block">\begin{array}{|c|}\hline P(m,n)\xrightarrow{2n+12}P(m-2,n+3)\text{ if }m\ge 4.\\\hline\end{array}</math>
With <math>A(a,b)</math> we have <math>P(b,0)</math>. As a result, we can apply this rule <math display="inline">\big\lfloor\frac{1}{2}b\big\rfloor-1</math> times (assuming <math>b\ge 4</math>), which creates two possible scenarios:
#If <math>b\equiv0\ (\operatorname{mod}2)</math>, then in <math>\sum_{i=0}^{(b/2)-2}(2\times 3i+12)=\textstyle\frac{3}{4}b^2+\frac{3}{2}b-6</math> steps we arrive at <math display="inline">P\Big(2,\frac{3}{2}b-3\Big)</math>. The matching complete configuration is <math>0^\infty\;1^a\;011\;\textrm{E}\textrm{>}\;0\;1^{(3b)/2-3}\;0^\infty</math>. After <math>3b+4</math> steps this is <math>0^\infty\;1^a\;\textrm{<}\textrm{C}\;00\;1^{(3b)/2}\;0^\infty</math>, which then leads to <math>0^\infty\;\textrm{<}\textrm{C}\;1^a\;00\;1^{(3b)/2}\;0^\infty</math> in <math>a</math> steps. After five more steps, we reach <math>0^\infty\;1\;\textrm{E}\textrm{>}\;1^{a+2}\;00\;1^{(3b)/2}\;0^\infty</math>, from which another shift rule must be applied:<math display="block">\begin{array}{|c|}\hline\textrm{E}\textrm{>}\;1^s\xrightarrow{s}1^s\;\textrm{E}\textrm{>}\\\hline\end{array}</math>Doing so allows us to get the configuration <math>0^\infty\;1^{a+3}\;\textrm{E}\textrm{>}\;00\;1^{(3b)/2}\;0^\infty</math> in <math>a+2</math> steps. In six steps we have <math>0^\infty\;1^{a+2}\;011\;\textrm{E}\textrm{>}\;1^{(3b)/2}\;0^\infty</math>, so we use the shift rule again, ending at <math>0^\infty\;1^{a+2}\;0\;1^{(3b)/2+2}\;\textrm{E}\textrm{>}\;0^\infty</math>, equal to <math display="inline">A\Big(a+2,\frac{3}{2}b+2\Big)</math>, <math display="inline">\frac{3}{2}b</math> steps later. This gives a total of <math display="inline">2a+\frac{3}{4}b^2+6b+11</math> steps.
#If <math>b\equiv1\ (\operatorname{mod}2)</math>, then in <math display="inline">\frac{3}{4}b^2-\frac{27}{4}</math> steps we arrive at <math display="inline">P\Big(3,\frac{3b-9}{2}\Big)</math>. The matching complete configuration is <math>0^\infty\;1^a\;0111\;\textrm{E}\textrm{>}\;0\;1^{(3b-9)/2}\;0^\infty</math>. After <math>3b+2</math> steps this becomes <math>0^\infty\;1^a\;\textrm{<}\textrm{F}\;110\;1^{(3b-3)/2}\;0^\infty</math>. If <math>a=0</math> then we have reached the undefined <code>F0</code> transition with a total of <math display="inline">\frac{3}{4}b^2+3b-\frac{19}{4}</math> steps. Otherwise, continuing for six steps gives us <math>0^\infty\;1^{a-1}\;0111\;\textrm{E}\textrm{>}\;1^{(3b-3)/2}\;0^\infty</math>. We conclude with the configuration <math>0^\infty\;1^{a-1}\;0\;1^{(3b+3)/2}\;\textrm{E}\textrm{>}\;0^\infty</math>, equal to <math display="inline">A\Big(a-1,\frac{3b+3}{2}\Big)</math>, in <math display="inline">\frac{3b-3}{2}</math> steps. This gives a total of <math display="inline">\frac{3}{4}b^2+\frac{9}{2}b-\frac{1}{4}</math> steps.
The information above can be summarized as
<math display="block">A(a,b)\rightarrow\begin{cases}A\Big(a+2,\frac{3}{2}b+2\Big)&\text{if }b\ge 2,b\equiv0\pmod{2};\\0^\infty\;\textrm{<}\textrm{F}\;110\;1^{(3b-3)/2}\;0^\infty&\text{if }b\ge3,b\equiv1\pmod{2},\text{ and }a=0;\\A\Big(a-1,\frac{3b+3}{2}\Big)&\text{if }b\ge3,b\equiv1\pmod{2},\text{ and }a>0.\end{cases}</math>
Substituting <math>b\leftarrow 2b</math> for the first case and <math>b\leftarrow 2b+1</math> for the other two yields the final result.
</div></div>
In effect, the halting problem for Antihydra is about whether repeatedly applying the function <math display="inline">f(n)=\Big\lfloor\frac{3n}{2}\Big\rfloor+2</math> will at some point produce more odd values of <math>n</math> than twice the number of even values.

These rules can be modified to use the function <math display="inline">H(n)=\Big\lfloor\frac{3n}{2}\Big\rfloor</math>, or the [[Hydra function]], which strengthens Antihydra's similarities to Hydra. In this variant of the sequence, each value is shifted up by 4, including the initial one. This keeps parity of the original, yet the terms can now be related using <math>H</math>:
<math display="block">H^i(8)=f^i(4)+4</math>
where superscripts denote iterated application. Here <math>H^i(8)</math> corresponds to the variant sequence and <math>f^i(4)</math> to the original one.

<div class="toccolours mw-collapsible mw-collapsed">'''Proof (trivial)'''<div class="mw-collapsible-content">
We use the following lemma
<math display="block">\forall n : H(n+4)=f(n)+4</math>
which is clear from the definitions:
<math display="block">\Big \lfloor \frac{3(n+4)}{2} \Big \rfloor = \Big \lfloor \frac{3(n)}{2} \Big \rfloor + 2 + 4</math>
<div class="toccolours mw-collapsible mw-collapsed">'''(Details)'''<div class="mw-collapsible-content">
<math display="block">\Big \lfloor \frac{3(n+4)}{2} \Big \rfloor</math>
<math display="block">= \Big \lfloor \frac{3(n)+12}{2} \Big \rfloor</math>
<math display="block">= \Big \lfloor \frac{3(n)}{2}+6 \Big \rfloor</math>
<math display="block">= \Big \lfloor \frac{3(n)}{2} \Big \rfloor + 6</math>
<math display="block">= \Big \lfloor \frac{3(n)}{2} \Big \rfloor + 2 + 4</math>
</div></div>

The proof is by induction. The base case, <math> H^0(8)=f^0(4)+4 </math> is equivalent to the trivial <math>8=4+4</math>. The induction step is next. Starting from the induction hypothesis:

<math display="block">H^i(8)=f^i(4)+4</math>
<math display="block">H(H^i(8))=H(f^i(4)+4)</math>
Use the lemma:
<math display="block">H(H^i(8))=f(f^i(4))+4</math>
<math display="block">H^{i+1}(8)=f^{i+1}(4)+4</math>
which was to be shown. Thus, for all i <math>\in \mathbb{N}</math>:
<math display="block">H^i(8)=f^i(4)+4</math>
</div></div>
== Trajectory ==
[[File:Antihydra Walk.png|thumb|Path of parity of repeated applications of Hydra map for Antihydra.]]
Starting from a blank tape, Antihydra reaches <math>A(0, 4)</math> in 11 steps and then the rules are repeatedly applied. So far, Antihydra has been simulated to <math>2^{38}</math> rule steps,<ref>https://discord.com/channels/960643023006490684/1026577255754903572/1271528180246773883</ref> at which point <math>a</math> exceeds <math>2^{37}</math>. Here are the first few:
<math display="block">\begin{array}{|c|}\hline A(0,4)\xrightarrow{47}A(2,8)\xrightarrow{111}A(4,14)\xrightarrow{250}A(6,23)\xrightarrow{500}A(5,36)\xrightarrow{1209}A(7,56)\xrightarrow{2713}A(9,86)\rightarrow\cdots\\\hline\end{array}</math>
The trajectory of <math>a</math> values resembles a random walk in which the walker can only move in step sizes +2 or -1 with equal probability, starting at position 0. If <math>P(n)</math> is the probability that the walker will reach position -1 from position <math>n</math>, then it can be seen that <math display="inline">P(n)=\frac{1}{2}P(n-1)+\frac{1}{2}P(n+2)</math>. Solutions to this recurrence relation come in the form <math display="inline"> P(n)=c_0{\left(\frac{\sqrt{5}-1}{2}\right)}^n+c_1+c_2{\left(-\frac{1+\sqrt{5}}{2}\right)}^n</math>, which after applying the appropriate boundary conditions reduces to <math display="inline">P(n)={\left(\frac{\sqrt{5}-1}{2}\right)}^{n+1}</math>. This means that if the walker were to get to the position of the current <math>a</math> value, then the probability of it ever reaching position -1 is less than <math display="inline">{\left( \frac{\sqrt{5}-1}{2} \right)}^{2^{37}}\approx 2.884\times 10^{-28723042565}</math>. This combined with the fact that the expected position of the walker after <math>k</math> steps is <math display="inline">\frac{1}{2}k</math> strongly suggests Antihydra [[probviously]] runs indefinitely.

== More Analysis ==
The <math>A</math> recurrence is equivalent to <math display="inline">D(0)=7, D(n+1)=\lceil D(n)\frac32\rceil</math><ref>Formalized proof at https://github.com/rwst/Antihydra-Basics/blob/main/AntihydraBasics/Antihydra.lean</ref><ref>Formalized proof at https://github.com/rwst/Antihydra-Basics/blob/main/AntihydraBasics/Basics.lean</ref> which is of advantage because in the Odlyzko-Wilf paper<ref>https://scholar.archive.org/work/usw755p7rzgtbnfpmkliokwdfa/access/wayback/https://www.cambridge.org/core/services/aop-cambridge-core/content/view/13435C4851F0CA24F64E08357C9D64F1/S0017089500008272a.pdf/div-class-title-functional-iteration-and-the-josephus-problem-div.pdf</ref> they showed that <math display="inline">D(n)=\lfloor K\cdot(\frac32)^n\rfloor</math>, for some <math>K</math>. They showed this for starting value <math>D(0)=1</math> but the proof works perfectly for any starting value except that the constant <math>K</math> will be different<ref>Formalized proof at https://github.com/rwst/Antihydra-Basics/blob/main/AntihydraBasics/Constant.lean</ref>. This means that the halting problem is a question of the parities of <math>D(n)</math> (as hinted above). However, a similar question on the parity of <math display="inline">\lfloor \xi\cdot(\frac32)^n\rfloor</math> has come up with [https://en.wikipedia.org/wiki/Mahler%27s_3/2_problem Mahler's Z-number problem]. That problem is formulated as a condition on the fractional parts of <math display="inline">\xi\cdot(\frac32)^n</math> but this is just another form. The Z-number problem is a long-standing open question and it could be answered if it were proven that <math display="inline">\{ \xi\cdot(\frac32)^n\}</math>, with <math>\{x\}</math> the fractional part of <math>x</math>, is uniformly distributed (or equidistributed) over <math>(0,1(</math>. A positive answer to that could also mean that the parity vector of <math>D(n)</math> is normal and thus a random walk.

== Code ==
The following Python program implements the abstracted behavior of the Antihydra. Proving whether it halts or not would also solve the Antihydra problem:<syntaxhighlight lang="python" line="1">
# Current value of the iterated Hydra function starting with initial value 8 (the values do not overflow)
h = 8 # 4 shifted by 4.
# (Collatz-like) condition counter that keeps track of how many odd and even numbers have been encountered
c = 0
# If c equals -1 there have been (strictly) more than twice as many odd as even numbers and the program halts
while c != -1:
# If h is even, add 2 to c so even numbers count twice
if h % 2 == 0:
c += 2
else:
c -= 1
# Add the current hydra value divided by two (integer division, rounding down) to itself (Hydra function, instead of Antihydra)
# Note that integer division by 2 is equivalent to one bit shift to the right (h >> 1)
h += h//2
</syntaxhighlight>

The variable values of this iteration have been put into the On-Line Encyclopedia of Integer Sequences (OEIS):

* Hydra function values with Antihydra's starting value 8: https://oeis.org/A386792
* Antihydra's condition values: https://oeis.org/A385902

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(6)]][[Category:Cryptids]]

Bug Game

2025-10-03T18:51:08Z

Isokate: Added source for Bug(7,7) = 218. (Feel free to change the text of the citation)

[[File:Bug Game Example.png|thumb|An example of a Bug Game maze]]
The '''Bug Game''' is an optimization game in which players design a 2d ''maze'' that a ''bug'' will be slowest to solve. The bug follows a relatively simple algorithm which preferentially visits locations less visited which is guaranteed to always eventually find a way to the destination (if such a path exists), but by exploiting the details of the tie-breaking logic, some mazes can trap the bug for a long time. You can play online at https://buglab.ru/

== History ==
The Bug Game was invented by a group of Russian students and their teacher (see [https://buglab.ru/index.asp?main=avtors authors]) at "Нортландия" (Nortlandiya) summer school. It was shared as a CodeForce [https://codeforces.com/blog/entry/115144 competition on 16 Apr 2023]. It was introduced to the [[bbchallenge]] community by @savask on 11 Sep 2025 ([https://discord.com/channels/960643023006490684/1362008236118511758/1415723582989930679 Discord]).

== Rules ==
A maze is a rectangular grid of tiles. The top left corner tile is the bug starting position (<code>S</code>)) and the bottom right corner is the destination (<code>F</code>)). All other tiles may be set to either wall (<code>#</code>) or empty (<code>.</code>). The maze has implicit walls around the outside of this rectangle. The domain (or rectangular grid size) is specified as HxW (height by width), the original buglab and CodeForce challenges are for the 19x29 domain.

For a given maze, the bug is placed on the start position (facing up) and repeatedly makes a step until it reaches the destination. At each stem, the bug will move to the orthogonally adjacent empty tile which has been visited least. If there is a tie then the bug will tie break among those least visited options by first preferring to continue to go straight ahead and second preferring directions in the order Down, Right, Up, Left.

The score of a maze is the number of steps needed for the bug to reach the destination. Bug(H,W) is the maximum score across all HxW mazes. The champion mazes (for a given domain) are the collection of mazes which score this maximum value.

A helpful abstraction is to think about a maze as an undirected graph/network with each tile as a node and adjacent tiles connected by edges.

== Growth Rate ==
Bug(H,W) is a computable function. For every maze, if there is a path to the destination, the bug will eventually succeed in finite time. It is also computable to detect that there exists a path to the destination (this is a graph connectivity problem). And finally there are finitely many (<math>2^{HW-2}</math>) mazes in each domain, therefor all can be searched and scored in finite time.

Furthermore, there is a known upper bound <math>Bug(H,W) \le 4^{HW}</math> first discovered by Daniel Yuan on 11 Sep 2025 ([https://discord.com/channels/960643023006490684/1362008236118511758/1415874391199449088] and [https://discord.com/channels/960643023006490684/1362008236118511758/1416144180039651401]) and further described by Shawn Ligocki ([https://discord.com/channels/960643023006490684/1362008236118511758/1416158428287602752]). The crux of the argument is that there is a limit to how different the visit counts of any two adjacent tiles can be. Specifically, if <math>v(a)</math> is the final visit count for a tile ''a'' and <math>deg(a)</math> is the degree (number of adjacent tiles), then for any two adjacent tiles ''a,b''

<math display="block">v(a) \ge \left\lfloor \frac{v(b)}{deg(b)} \right\rfloor</math>

In a rectangular grid, <math>deg(b) \le 4</math> and so we have approximately <math>v(b) \le 4 v(a)</math> (due to the floor function, the exact relationship is slightly weaker like <math>v(b)+1 <= 4 (v(a)+1))</math>). Then you can calculate maximum visit counts for all tiles/nodes and sum them up, this can never by greater than <math>4^{HW}</math>.

== Known Champions ==
This is a list of some known values for Bug function and an example champion (there may be other champions tied for first place not listed). In the mazes below (<code>-</code>) indicates that this tile may be either wall or empty, it does not matter because the bug never visits that tile.

=== Square Domains ===
Bug(2,2) = 2
<pre>
####
#S-#
#.F#
####
</pre>

Bug(3,3) = 8
<pre>
#####
#S..#
#.#.#
#.#F#
#####
</pre>

Bug(4,4) = 20
<pre>
######
#S...#
#..###
#....#
#..#F#
######
</pre>

Bug(5,5) = 42
<pre>
#######
#S...##
#.....#
#.....#
#.#.###
#.#..F#
#######
</pre>

Bug(6,6) = 96
<pre>
########
#S.....#
#.###.##
#.#...##
#.#....#
#..#.###
#..#..F#
########
</pre>

Bug(7,7) = 218 ([https://katelyndoucette.com/articles/bugs-mazes-and-bradys-algorithm Source])
<pre>
#########
#S.###..#
#......##
#.#.##..#
#..#...##
#..#....#
#...#.###
#..#-..F#
#########
</pre>

Bug(8,8) = 506 ([https://discord.com/channels/960643023006490684/1362008236118511758/1423502208422510716 Discord Link])
<pre>
##########
#S.#.....#
#.#..##.##
#.#.##..##
#....##..#
#.#.#...##
#..##....#
#....#.###
#....#..F#
##########
</pre>

== Current Champions ==
These are some best known mazes (and scores) for domains that have not been exhaustively solved yet.

Bug(19,29) ≥ 11,160,428 (Daniel Yuan 12 Sep 2025 [https://discord.com/channels/960643023006490684/1362008236118511758/1416241487452049469])
<pre>
###############################
#S##.##.....#..#.##.....#....##
#.....##...#......#.#..##.##.##
#..#.#...#.#..##..#.##.##.#...#
#.....#.#...#.#...#..#.##.##.##
#..#.#...#.#...#.##.##.#...#.##
#..#.##.#...#.##.#...#.##.##.##
#.#...#..#.#..##..#.##.##.##.##
#..#.#...#.#...#.##.##.##.#...#
#.#...#.#...#.#...#.#...#.##.##
#..#.#...#.#...#.#..##.##..#.##
#.#..#..##.##.##..#.#...#.##..#
#..#..#.#...#.#..##.##.##.##.##
#..#.#...#.##..#.##.##.#..##.##
#.#...#.#...#.##.##.##.##.#..##
#..##...#..#..#...#.##.#..##..#
#...#..#.#.##.##.##.##.#.#...##
#..#.##.#...#..#.#...#.#.#....#
#.#......#....#...#.##.#.##.###
#...#....#....#.....##...##..F#
###############################
</pre>

Note: the [https://buglab.ru/index.asp?main=rating BugLab Ratings] page lists the current 19x29 champion at score 100,353,979,636 (as of 30 Sep 2025). But the actual maze is a secret.

== See Also ==
* Original Game website: https://buglab.ru/
* Known Exact Values of Bug(H,W): [https://docs.google.com/spreadsheets/d/1eTaddIAiXGR--RvFbQfnwjXHVWMpPxDuOFKbgQ1XCoI/edit?usp=sharing Spreadsheet]

Beaver Math Olympiad

2025-08-28T01:19:24Z

Isokate: Minor wording changes, removed f^0(b) = b because it's redundant

'''Beaver Mathematical Olympiad''' (BMO) is an attempt to re-formulate the halting problem for some particular Turing machines as a mathematical problem in a style suitable for a hypothetical math olympiad.

The purpose of the BMO is twofold. First, statements where non-essential details (related to tape encoding, number of steps, etc.) are discarded are more suitable to be shared with mathematicians who perhaps are able to help. Second, it's a way to jokingly highlight how a hard question could appear deceptively simple.

== Unsolved problems ==

=== 1. {{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}} ===

Let <math>(a_n)_{n \ge 1}</math> and <math>(b_n)_{n \ge 1}</math> be two sequences such that <math>(a_1, b_1) = (1, 2)</math> and

<math display="block">(a_{n+1}, b_{n+1}) = \begin{cases}
(a_n-b_n, 4b_n+2) & \text{if }a_n \ge b_n \\
(2a_n+1, b_n-a_n) & \text{if }a_n < b_n
\end{cases}</math>

for all positive integers <math>n</math>. Does there exist a positive integer <math>i</math> such that <math>a_i = b_i</math>?

The first 10 values of <math>(a_n, b_n)</math> are <math>(1, 2), (3, 1), (2, 6), (5, 4), (1, 18), (3, 17), (7, 14), (15, 7), (8, 30), (17, 22)</math>.

=== 2. [[Hydra]] and [[Antihydra]] ===

Let <math>(a_n)_{n \ge 0}</math> be a sequence such that <math>a_{n+1} = a_n+\left\lfloor\frac{a_n}{2}\right\rfloor</math> for all non-negative integers <math>n</math>.

# If <math>a_0=3</math>, does there exist a non-negative integer <math>k</math> such that the list of numbers <math>a_0, a_1, a_2, \dots, a_k</math> have more than twice as many even numbers as odd numbers? ([[Hydra]])
# If <math>a_0=8</math>, does there exist a non-negative integer <math>k</math> such that the list of numbers <math>a_0, a_1, a_2, \dots, a_k</math> have more than twice as many odd numbers as even numbers? ([[Antihydra]])

=== 5. {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}} ===

Let <math>(a_n)_{n \ge 1}</math> and <math>(b_n)_{n \ge 1}</math> be two sequences such that <math>(a_1, b_1) = (0, 5)</math> and

<math display="block">(a_{n+1}, b_{n+1}) = \begin{cases}
(a_n+1, b_n-f(a_n)) & \text{if } b_n \ge f(a_n) \\
(a_n, 3b_n+a_n+5) & \text{if } b_n < f(a_n)
\end{cases}</math>

where <math>f(x)=10\cdot 2^x-1</math> for all non-negative integers <math>x</math>.

Does there exist a positive integer <math>i</math> such that <math>b_i = f(a_i)-1</math>?

=== 6. {{TM|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD|undecided}} ===
Let <math>f(b) = b + k + 3a</math>, where <math>k</math> and <math>a</math> are non-negative integers satisfying <math>b = (2a+1)\cdot 2^k</math>.

Now consider the iterated application of the function <math>f^{n+1}(b) = f(f^n(b)))</math>. Does there exist a non-negative integer <math>n</math> such that <math>f^n(6)</math> equals a power of 2?

== Solved problems ==

=== 3. {{TM|1RB0RB3LA4LA2RA_2LB3RA---3RA4RB|non-halt}} and {{TM|1RB1RB3LA4LA2RA_2LB3RA---3RA4RB|non-halt}} ===

Let <math>v_2(n)</math> be the largest integer <math>k</math> such that <math>2^k</math> divides <math>n</math>. Let <math>(a_n)_{n \ge 0}</math> be a sequence such that

<math display="block">a_n = \begin{cases}
2 & \text{if } n=0 \\
a_{n-1}+2^{v_2(a_{n-1})+2}-1 & \text{if } n \ge 1
\end{cases}</math>

for all non-negative integers <math>n</math>. Is there an integer <math>n</math> such that <math>a_n=4^k</math> for some positive integer <math>k</math>?

Link to Discord discussion: https://discord.com/channels/960643023006490684/1084047886494470185/1252634913220591728

=== 4. {{TM|1RB3RB---1LB0LA_2LA4RA3LA4RB1LB|non-halt}} ===

Bonnie the beaver was bored, so she tried to construct a sequence of integers <math>\{a_n\}_{n \ge 0}</math>. She first defined <math>a_0=2</math>, then defined <math>a_{n+1}</math> depending on <math>a_n</math> and <math>n</math> using the following rules:

* If <math>a_n \equiv 0\text{ (mod 3)}</math>, then <math>a_{n+1}=\frac{a_n}{3}+2^n+1</math>.
* If <math>a_n \equiv 2\text{ (mod 3)}</math>, then <math>a_{n+1}=\frac{a_n-2}{3}+2^n-1</math>.

With these two rules alone, Bonnie calculates the first few terms in the sequence: <math>2, 0, 3, 6, 11, 18, 39, 78, 155, 306, \dots</math>. At this point, Bonnie plans to continue writing terms until a term becomes <math>1\text{ (mod 3)}</math>. If Bonnie sticks to her plan, will she ever finish?

<div class="toccolours mw-collapsible mw-collapsed">'''Solution'''<div class="mw-collapsible-content">
How to guess the closed-form solution: Firstly, notice that <math>a_n \approx \frac{3}{5} \times 2^n</math>. Secondly, calculate the error term <math>a_n - \frac{3}{5} \times 2^n</math>. The error term appears to have a period of 4. This leads to the following guess:

<math display="block">a_n=\frac{3}{5}\begin{cases}
2^n+\frac{7}{3} &\text{if } n\equiv 0 \pmod{4}\\
2^n-2 &\text{if } n\equiv 1 \pmod{4}\\
2^n+1 &\text{if } n\equiv 2 \pmod{4}\\
2^n+2 &\text{if } n\equiv 3 \pmod{4}\\
\end{cases}</math>

This closed-form solution can be proven correct by induction. Unfortunately, the induction may require a lot of tedious calculations.

For all <math>k</math>, we have <math>a_{4k} \equiv 2\text{ (mod 3)}</math> and <math>a_{4k+1} \equiv a_{4k+2} \equiv a_{4k+3} \equiv 0\text{ (mod 3)}</math>. Therefore, Bonnie will never finish.
</div></div>

Beaver Math Olympiad

2025-08-26T21:21:15Z

Isokate: Added BMO6

'''Beaver Mathematical Olympiad''' (BMO) is an attempt to re-formulate the halting problem for some particular Turing machines as a mathematical problem in a style suitable for a hypothetical math olympiad.

The purpose of the BMO is twofold. First, statements where non-essential details (related to tape encoding, number of steps, etc.) are discarded are more suitable to be shared with mathematicians who perhaps are able to help. Second, it's a way to jokingly highlight how a hard question could appear deceptively simple.

== Unsolved problems ==

=== 1. {{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}} ===

Let <math>(a_n)_{n \ge 1}</math> and <math>(b_n)_{n \ge 1}</math> be two sequences such that <math>(a_1, b_1) = (1, 2)</math> and

<math display="block">(a_{n+1}, b_{n+1}) = \begin{cases}
(a_n-b_n, 4b_n+2) & \text{if }a_n \ge b_n \\
(2a_n+1, b_n-a_n) & \text{if }a_n < b_n
\end{cases}</math>

for all positive integers <math>n</math>. Does there exist a positive integer <math>i</math> such that <math>a_i = b_i</math>?

The first 10 values of <math>(a_n, b_n)</math> are <math>(1, 2), (3, 1), (2, 6), (5, 4), (1, 18), (3, 17), (7, 14), (15, 7), (8, 30), (17, 22)</math>.

=== 2. [[Hydra]] and [[Antihydra]] ===

Let <math>(a_n)_{n \ge 0}</math> be a sequence such that <math>a_{n+1} = a_n+\left\lfloor\frac{a_n}{2}\right\rfloor</math> for all non-negative integers <math>n</math>.

# If <math>a_0=3</math>, does there exist a non-negative integer <math>k</math> such that the list of numbers <math>a_0, a_1, a_2, \dots, a_k</math> have more than twice as many even numbers as odd numbers? ([[Hydra]])
# If <math>a_0=8</math>, does there exist a non-negative integer <math>k</math> such that the list of numbers <math>a_0, a_1, a_2, \dots, a_k</math> have more than twice as many odd numbers as even numbers? ([[Antihydra]])

=== 5. {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}} ===

Let <math>(a_n)_{n \ge 1}</math> and <math>(b_n)_{n \ge 1}</math> be two sequences such that <math>(a_1, b_1) = (0, 5)</math> and

<math display="block">(a_{n+1}, b_{n+1}) = \begin{cases}
(a_n+1, b_n-f(a_n)) & \text{if } b_n \ge f(a_n) \\
(a_n, 3b_n+a_n+5) & \text{if } b_n < f(a_n)
\end{cases}</math>

where <math>f(x)=10\cdot 2^x-1</math> for all non-negative integers <math>x</math>.

Does there exist a positive integer <math>i</math> such that <math>b_i = f(a_i)-1</math>?

=== 6. {{TM|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD|undecided}} ===
Let <math>f(b) = b + k + 3a</math>, where k and a are integers satisfying <math>b = (2a+1)*2^k</math>

Now consider the iterated application of the function <math>f^n(b) = f(f^{n-1}(b)))</math>. Does <math>f^n(6)</math> equal a power of 2 for any n?

== Solved problems ==

=== 3. {{TM|1RB0RB3LA4LA2RA_2LB3RA---3RA4RB|non-halt}} and {{TM|1RB1RB3LA4LA2RA_2LB3RA---3RA4RB|non-halt}} ===

Let <math>v_2(n)</math> be the largest integer <math>k</math> such that <math>2^k</math> divides <math>n</math>. Let <math>(a_n)_{n \ge 0}</math> be a sequence such that

<math display="block">a_n = \begin{cases}
2 & \text{if } n=0 \\
a_{n-1}+2^{v_2(a_{n-1})+2}-1 & \text{if } n \ge 1
\end{cases}</math>

for all non-negative integers <math>n</math>. Is there an integer <math>n</math> such that <math>a_n=4^k</math> for some positive integer <math>k</math>?

Link to Discord discussion: https://discord.com/channels/960643023006490684/1084047886494470185/1252634913220591728

=== 4. {{TM|1RB3RB---1LB0LA_2LA4RA3LA4RB1LB|non-halt}} ===

Bonnie the beaver was bored, so she tried to construct a sequence of integers <math>\{a_n\}_{n \ge 0}</math>. She first defined <math>a_0=2</math>, then defined <math>a_{n+1}</math> depending on <math>a_n</math> and <math>n</math> using the following rules:

* If <math>a_n \equiv 0\text{ (mod 3)}</math>, then <math>a_{n+1}=\frac{a_n}{3}+2^n+1</math>.
* If <math>a_n \equiv 2\text{ (mod 3)}</math>, then <math>a_{n+1}=\frac{a_n-2}{3}+2^n-1</math>.

With these two rules alone, Bonnie calculates the first few terms in the sequence: <math>2, 0, 3, 6, 11, 18, 39, 78, 155, 306, \dots</math>. At this point, Bonnie plans to continue writing terms until a term becomes <math>1\text{ (mod 3)}</math>. If Bonnie sticks to her plan, will she ever finish?

<div class="toccolours mw-collapsible mw-collapsed">'''Solution'''<div class="mw-collapsible-content">
How to guess the closed-form solution: Firstly, notice that <math>a_n \approx \frac{3}{5} \times 2^n</math>. Secondly, calculate the error term <math>a_n - \frac{3}{5} \times 2^n</math>. The error term appears to have a period of 4. This leads to the following guess:

<math display="block">a_n=\frac{3}{5}\begin{cases}
2^n+\frac{7}{3} &\text{if } n\equiv 0 \pmod{4}\\
2^n-2 &\text{if } n\equiv 1 \pmod{4}\\
2^n+1 &\text{if } n\equiv 2 \pmod{4}\\
2^n+2 &\text{if } n\equiv 3 \pmod{4}\\
\end{cases}</math>

This closed-form solution can be proven correct by induction. Unfortunately, the induction may require a lot of tedious calculations.

For all <math>k</math>, we have <math>a_{4k} \equiv 2\text{ (mod 3)}</math> and <math>a_{4k+1} \equiv a_{4k+2} \equiv a_{4k+3} \equiv 0\text{ (mod 3)}</math>. Therefore, Bonnie will never finish.
</div></div>

1RB1LA 1LC0RE 1LF1LD 0RB0LA 1RC1RE ---0LD

2025-08-11T04:39:45Z

Isokate: Replaced the rules with the shifted-up-by-3 version, and removed the heuristic argument section (because the argument was bad)

{{machine|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD}}{{unsolved|Does this TM run forever?}}
{{TM|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD}} is a [[probviously]] non-halting [[BB(6)]] [[Cryptid]] first discovered and analyzed by @mxdys on [https://discord.com/channels/960643023006490684/1239205785913790465/1326911501357023296 9 Jan 2025]. Mxdys derived the lower level rules, and Racheline and Katelyn Doucette independently derived the higher level rules later on.

Determining whether this machine halts requires proving that a highly chaotically growing sequence never intersects with a value equal to <math>2^n</math>. It is believed to be a [[Cryptid]], because proving this seems to require a deep understanding of how addition of two integers affects the number of factors of 2 in the sum, and/or much stronger ways of characterizing when two sequences can share terms in common. Both of which are believed to be out of reach of current mathematics.

== Analysis ==
=== Low Level Rules ===
The original reported low level rules derived by @mxdys:

<pre>
1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD

start: (3,1)
(0,2+c) --> (4+c,1)
(1,c) --> halt
(2+2b,c) --> (7+5b+c,1)
(3+2b,c) --> (b,4+b+c)

(b,c) := 0^inf <A 1^b 00 1^c 0^inf
</pre>

Or the following rewritten form by Andrew Ducharme:

<pre>
start: (3,1)
(1,c) --> halt
(2b,c) --> (2+5b+c,1)
(2b+1,c) --> (b-1,3+b+c)

(b,c) := 0^inf <A 1^b 00 1^c 0^inf
</pre>

=== Higher Level Rules ===
Further derivation and analysis of the higher level rules took place on [https://discord.com/channels/960643023006490684/1400226828396003480 July 31 2025]<br>
The low level rules can be abstracted up a level by noticing that the c parameter always gets set to a consistent starting value of 1 when the rule triggered by b being even is encountered. It's possible to, through induction, generate a mapping from each <math>(b_n, 1)</math> to the next <math>(b_{n+1}, 1)</math>. This allows one to completely eliminate the c parameter and have a set of rules entirely dependent on the value of b.

Rules derived by Katelyn Doucette:
<pre>
Let v(b) denote the largest power of 2 that divides b.

START: b = 6

If b = 2^v(b):
HALT
else:
b --> b + v(b) + 3/2 * (b/2^v(b) - 1)
</pre>

Important to note, the actual machine seems to work with an alternative formulation of the above rules where b and its halting problem are shifted down by 3. The version with b shifted up by 3 is shown instead due to stylistic reasons, as well as improved computation speed.

== Trajectory ==
At a high level, the machine's halting problem is governed by a highly chaotically growing sequence. The first few terms of the sequence are:
<math display="block">\begin{array}{|c|}\hline 6 \rightarrow 10 \rightarrow 17 \rightarrow 41 \rightarrow 101 \rightarrow 251 \rightarrow 626 \rightarrow 1095 \rightarrow 2736 \rightarrow 2995 \rightarrow \cdots\\\hline\end{array}</math>
This sequence has been calculated out to over 17 million terms, with the final value of b calculated before the program was terminated reaching <math> >10^{4,800,000} </math>. No power of 2 was ever encountered (which would lead to halting), and the most factors of 2 any term had was 24.

The growth rate of this sequence was characterized by @LegionMammal978 as below:<br>
Assuming that the lower bits of b are random and uniform (which is well-supported empirically), it grows by an average log-factor of <math>0.652355</math>, which corresponds to <math>O(1.92006^b)</math>, plus or minus a random walk on the log scale.
[[Category:Cryptids]]

BB(6)

2025-08-01T04:55:15Z

Isokate: /* Cryptids */

The 6-state, 2-symbol Busy Beaver problem, '''BB(6)''', refers to the unsolved 6<sup>th</sup> value of the [[Busy Beaver function]]. With the discovery of the [[Cryptid]] machine [[Antihydra]] in June 2024, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(6) and thus [https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html BB(6) is Hard].

The current BB(6) champion {{TM|1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE|halt}} was discovered by mxdys in June 2025, proving the lower bound:

<math display="block">S(6) > \Sigma(6) > 2 \uparrow\uparrow\uparrow 5</math>

== Techniques ==
Simulating tetrational machines, such as the former champion {{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}, requires [[Accelerated simulator|accelerated simulation]] that can handle Collatz Level 2 [[Inductive rule|inductive rules]]. In other words, it requires a simulator that can prove the rules:

<math display="block">\begin{array}{lcl}
C(4k) & \to & {\operatorname{Halt}}\Big(\frac{3^{k+3} - 11}{2}\Big) \\
C(4k+1) & \to & C\Big(\frac{3^{k+3} - 11}{2}\Big) \\
C(4k+2) & \to & C\Big(\frac{3^{k+3} - 11}{2}\Big) \\
C(4k+3) & \to & C\Big(\frac{3^{k+3} + 1}{2}\Big) \\
\end{array}</math>

and also compute the remainder mod 3 of numbers produced by applying these rules 15 times (which requires some fancy math related to [[wikipedia:Euler's_totient_function|Euler's totient function]]).

== Cryptids ==
Several [[Turing machines]] have been found that are [[Cryptids]], considered so because each of them have a [[Collatz-like]] halting problem, a type of problem that is generally difficult to solve. However, probabilistic arguments have allowed all but one of them to be categorized as [[probviously]] halting or probviously non-halting.

Probviously non-halting Cryptids:

* {{TM|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA}}, [[Antihydra]]
* {{TM|1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA|undecided}}, a variant of [[Hydra]] and Antihydra
* {{TM|1RB1LD_1RC1RE_0LA1LB_0LD1LC_1RF0RA_---0RC|undecided}}, similar to Antihydra
* {{TM|1RB0LD_1RC1RF_1LA0RA_0LA0LE_1LD1LA_0RB---|undecided}}, similar to Antihydra
* {{TM|1RB0LB_1LC0RE_1LA1LD_0LC---_0RB0RF_1RE1RB|undecided}}, similar to Antihydra
* {{TM|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD|undecided}}

Probviously halting Cryptids:

* {{TM|1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA}}, [[Lucy's Moonlight]]
* {{TM|1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC|undecided}}, a family of 16 related TMs
* {{TM|1RB1RE_1LC1LD_---1LA_1LB1LE_0RF0RA_1LD1RF}}
* {{TM|1RB0RE_1LC1LD_0RA0LD_1LB0LA_1RF1RA_---1LB}}
* {{TM|1RB0LC_0LC0RF_1RD1LC_0RA1LE_---0LD_1LF1LA}}
* {{TM|1RB0LC_1LC0RD_1LF1LA_1LB1RE_1RB1LE_---0LE}}
* {{TM|1RB---_0RC0RE_1RD1RF_1LE0LB_1RC0LD_1RC1RA}}
* {{TM|1RB0LD_1RC1RA_1LD0RB_1LE1LA_1RF0RC_---1RE}}

Although {{TM|1RB1LE_0LC0LB_1RD1LC_1RD1RA_1RF0LA_---1RE}} behaves similarly to the probviously halting Cryptids, it is estimated to have a 3/5 chance of becoming a [[translated cycler]] and a 2/5 chance of halting.

There are a few machines considered notable for their chaotic behaviour, but which have not been classified as Cryptids due to seemingly lacking a connection to any known open mathematical problems, such as Collatz-like problems.

Potential Cryptids:

* {{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}
* {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}}
* {{TM|1RB0RB_1LC1RE_1LF0LD_1RA1LD_1RC1RB_---1LC|undecided}}

== Top Halters ==
Below is a table of the machines with the 10 highest known runtimes.<ref>Shawn Ligocki's list of 6-state, 2-symbol machines with large runtimes ([https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/6x2.txt Link])</ref> Their sigma scores are expressed using an extension of Knuth's up-arrow notation.<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/06/25/ext-up-notation.html "Extending Up-arrow Notation"]</ref>
{| class="wikitable"
|+Top Known BB(6) Halters
!Standard format
!(approximate) Σ
|-
|{{TM|1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE|halt}}
|2 ↑↑↑ 5
|-
|{{TM|1RB1LC_1LA1RE_0RD0LA_1RZ1LB_1LD0RF_0RD1RB|halt}}
|10 ↑↑ 11010000
|-
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE}}
|10 ↑↑ 15.60465
|-
|{{TM|1RB0LF_1RC1RB_1LD0RA_1LB0LE_1RZ0LC_1LA1LF}}
|10 ↑↑ 7.52390
|-
|{{TM|1RB0LF_1RC1RB_1LD0RA_1RF0LE_1RZ0LC_1LA1LF}}
|10 ↑↑ 7.52390
|-
|{{TM|1RB0LF_1RC1RB_1LD0RA_1LF0LE_1RZ0LC_1LA1LF}}
|10 ↑↑ 7.52390
|-
|{{TM|1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA}}
|10 ↑↑ 7.23619
|-
|{{TM|1RB1RA_1LC1LE_1RE0LD_1LC0LF_1RZ0RA_0RA0LB}}
|10 ↑↑ 6.96745
|-
|{{TM|1RB0RF_1LC0RA_1RZ0LD_1LE1LD_1RB1RC_0LD0RE}}
|10 ↑↑ 5.77573
|-
|{{TM|1RB0LA_1LC1LF_0LD0LC_0LE0LB_1RE0RA_1RZ1LD}}
|10 ↑↑ 5.63534
|}
The runtimes are presumed to be about <math>\text{score}^2</math> which is roughly indistinguishable in tetration notation.

== Holdouts ==
[[File:BB6 num holdouts over time.png|thumb|Number of BB(6) holdouts over time]]
@mxdys's informal [[Holdouts lists|holdouts list]] has 2891 machines up to equivalence as of July 2025.

== References ==
<references />
[[Category:BB Domain]]

1RB1LA 1LC0RE 1LF1LD 0RB0LA 1RC1RE ---0LD

2025-08-01T04:51:05Z

Isokate:

{{machine|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD}}{{unsolved|Does this TM run forever?}}
{{TM|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD}} is a [[Probviously]] Nonhalting [[BB(6)]] [[Cryptid]] first discovered and analyzed by @mxdys on [https://discord.com/channels/960643023006490684/1239205785913790465/1326911501357023296 9 Jan 2025]. Mxdys derived the lower level rules, and Racheline and Katelyn Doucette independently derived the higher level rules later on.

Determining whether this machine halts requires proving that a highly chaotically growing sequence never intersects with a value equal to <math>2^n - 3</math>. It is believed to be a [[Cryptid]], because proving this seems to require a deep understanding of how addition of two integers affects the number of factors of 2 in the sum, and/or much stronger ways of characterizing when two sequences can share terms in common. Both of which are believed to be out of reach of current mathematics.

== Analysis ==
=== Low Level Rules ===
The original reported low level rules derived by @mxdys:

<pre>
1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD

start: (3,1)
(0,2+c) --> (4+c,1)
(1,c) --> halt
(2+2b,c) --> (7+5b+c,1)
(3+2b,c) --> (b,4+b+c)

(b,c) := 0^inf <A 1^b 00 1^c 0^inf
</pre>

Or the following rewritten form by Andrew Ducharme:

<pre>
start: (3,1)
(1,c) --> halt
(2b,c) --> (2+5b+c,1)
(2b+1,c) --> (b-1,3+b+c)

(b,c) := 0^inf <A 1^b 00 1^c 0^inf
</pre>

=== Higher Level Rules ===
Further derivation and analysis of the higher level rules took place on [https://discord.com/channels/960643023006490684/1400226828396003480 July 31 2025]<br>
The low level rules can be abstracted up a level by noticing that the c parameter always gets set to a consistent starting value of 1 when the rule triggered by b being even is encountered. It's possible to, through induction, generate a mapping from each <math>(b_n, 1)</math> to the next <math>(b_{n+1}, 1)</math>. This allows one to completely eliminate the c parameter and have a set of rules entirely dependent on the value of b.

Rules derived by Katelyn Doucette:
<pre>
Let n denote the exponent of the largest power of 2 that divides (b + 3)
START: b = 3

b --> b + n + 3/2 * ((b+3)/2^n - 1)

Halt if b = 2^n - 3
</pre>

Alternative formulations can be derived by shifting b to b + 3.

== Trajectory ==
At a high level, the machine's halting problem is governed by a highly chaotically growing sequence. The first few terms of the sequence are:
<math display="block">\begin{array}{|c|}\hline 3 \rightarrow 7 \rightarrow 14 \rightarrow 38 \rightarrow 98 \rightarrow 248 \rightarrow 623 \rightarrow 1092 \rightarrow 2733 \rightarrow 2992 \rightarrow \cdots\\\hline\end{array}</math>
This sequence has been calculated out to over 17 million terms, with the final value of b calculated before the program was terminated reaching <math> >10^{4,800,000} </math>. Not a single term was of the form <math> 2^n - 3 </math> that would cause halting. The largest value of n encountered was 24.

The growth rate of this sequence was characterized by @LegionMammal978 as below:<br>
Assuming that the lower bits of b are random and uniform (which is well-supported empirically), it grows by an average log-factor of <math>0.652355</math>, which corresponds to <math>O(1.92006^b)</math>, plus or minus a random walk on the log scale.

=== Heuristic Argument For Nonhalting ===
If you pick an arbitrary integer, the chance that it has n factors of 2 is <math>\frac{1}{2^{n+1}}</math>. Since the sequence grows roughly as fast as <math> 2^n - 3 </math>, the chance of it hitting a large enough n decreases exponentially with the number of terms you go into the sequence. Thus, the chance of term k in the sequence halting is roughly <math>\frac{1}{1.92^{k}}</math>. By the time you get out to <math> k > 17,000,000 </math>, the probability of the sequences colliding is tiny.

BB(7)

2025-07-27T13:25:35Z

Isokate: Fixed holdouts number for 19XXXX (1,601,356 -> 1,099,752. Old number included decided TM's by Enumerate.py)

The 7-state, 2-symbol Busy Beaver problem, '''BB(7)''', refers to the unsolved 7<sup>th</sup> value of the [[Busy Beaver function]]. With the compilation of the [[Cryptid]] machine [[Bigfoot]] into a 7-state, 2-symbol machine in May 2024, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(7).

The current BB(7) champion {{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}} was discovered by Pavel Kropitz in May 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. In 1964, Milton Green designed a machine that had [[sigma score]] 22,961. In 2014, Wythagoras modified a BB(6) champion 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. A few days later, Pavel found a TM that outpaces all of them.

Pavel's champion is enumerated in subtask 243308.

== 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 sortable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|data-sort-value="10 ↑↑ 9999"|<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|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LE_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|Andrew Ducharme
|-
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LE_0RD0LG_1LB0LE}}
|10 ↑↑ 519.20
|@gerbil5709, Terry Ligocki
|-
|{{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_1RC0LE_0RD1RB_1LE1RA_1LF0LG_0LG0RG_1LB1RG}}
|10 ↑↑ 243.88
|@Iijil, Andrew Ducharme
|-
|{{TM|1RB0RB_1LC1RG_1RD1RC_1RE0RA_1LF0LB_1RF0LE_0RD1RZ}}
|10 ↑↑ 228.78
|Terry Ligocki
|-
|{{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|1RB0LD_0LC1RZ_1RA0RD_1RE1LD_1LF0RC_0LG1LE_1RC0LD}}
|10 ↑↑ 192.67
|Andrew Ducharme
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE1LG_1RF0LG_0RA0LA_0RF1RZ}}
|10 ↑↑ 192.67
|Andrew Ducharme
|-
|{{TM|1RB1LA_1LC0RF_0LD0RD_1RF1LE_1LB1RZ_1RG0RA_0RA0LA}}
|10 ↑↑ 192.67
|@C7X
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE0LA_1RF0RA_0RG0LA_1RB1RZ}}
|10 ↑↑ 192.67
|@Iijil, Terry Ligocki
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE0LA_1RF0RA_1RG0LA_0LE1RZ}}
|10 ↑↑ 192.67
|@Iijil, Terry Ligocki
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE0LG_1RF0RA_0RA0LA_1RB1RZ}}
|10 ↑↑ 192.67
|@Iijil, Terry Ligocki
|}

The top 20 known halters with unique scores are:

{| class="wikitable sortable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|data-sort-value="10 ↑↑ 9999"|<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_1RC0LE_0RD1RB_1LE1RA_1LF0LG_0LG0RG_1LB1RG}}
|10 ↑↑ 243.88
|@Iijil, Andrew Ducharme
|-
|{{TM|1RB0RB_1LC1RG_1RD1RC_1RE0RA_1LF0LB_1RF0LE_0RD1RZ}}
|10 ↑↑ 228.78
|Terry Ligocki
|-
|{{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|1RB0RF_1RC1RZ_0LD1RF_0RA1LE_0LC1LF_1LE0RG_0LE1RA}}
|10 ↑↑ 136.64
|Katelyn Doucette, Andrew Ducharme
|-
|{{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|1RB0LD_1RC1RA_0RD1RG_1LE1LF_0LF1LE_0RA0LD_0RA1RZ}}
|10 ↑↑ 124.86
|Terry Ligocki
|-
|{{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|1RB0RG_1LC0LE_1LD0LB_0LE1RE_0RA1RF_0RD1RC_1RD1RZ}}
|10 ↑↑ 114.83
|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
|}

== Current Progress ==
This is a summary of the 1 million subtasks from mxdys's code that have been executed and their output processed by Shawn Ligocki's linear rule code.
{| class="wikitable sortable 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
|-
|00-01xxxx
|@Iijil
|Yes
|Yes
|1,545,673
|{{TM|1RB0LE_1RC0RA_1RD0RC_1LE1LD_1LA0LF_0LA0LG_1RZ0RD}}
|10 ↑↑ 246.32
|[https://drive.google.com/drive/folders/1wniwrAuvsHfkvro8Tg65WAMNZEuIekzD Google Drive folder]
|-
|02-04xxxx
|
@Iijil<br/>
Terry Ligocki
|Yes
|Yes
|2,279,734
|{{TM|1RB0LF_1RC1RA_1RD0RG_1LE1RZ_1LA0LF_1RA1LE_0RE1RG}}
|10 ↑↑ 93.81
|
[https://drive.google.com/drive/folders/1wniwrAuvsHfkvro8Tg65WAMNZEuIekzD @Iijil]<br/>
[https://drive.google.com/drive/folders/1yQFLcznvNzEF9uWXL1xkJhhfxPDtbC7x?usp=drive_link Terry Ligocki]
|-
|05-09xxxx
|
@Iijil<br/>
Andrew Ducharme
|Yes
|Yes
|3,889,955
|{{TM|1RB1RZ_1RC0LE_0RD1RB_1LE1RA_1LF0LG_0LG0RG_1LB1RG}}
|10 ↑↑ 243.88
|
[https://drive.google.com/drive/folders/1wniwrAuvsHfkvro8Tg65WAMNZEuIekzD @Iijil]<br/>
[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Andrew]
|-
|10-12xxxx
|Andrew Ducharme
|Yes
|Yes
|2,708,888
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LE_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|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/1yQFLcznvNzEF9uWXL1xkJhhfxPDtbC7x?usp=drive_link Google Drive folder]
|-
|14-16xxxx
|Andrew Ducharme
|Yes
|Yes
|2,701,637
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_0RF0LD_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|17-18xxxx
|
@gerbil5709<br/>
Terry Ligocki
|Yes
|Yes
|1,898,156
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE0LA_1RF0RA_0RG0LA_1RB1RZ}}
|10 ↑↑ 192.67
|
[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing @gerbil5709]<br/>
[https://drive.google.com/drive/folders/1yQFLcznvNzEF9uWXL1xkJhhfxPDtbC7x?usp=drive_link Terry Ligocki]
|-
|19xxxx
|
Katelyn Doucette<br/>
Andrew Ducharme
|Yes
|Yes
|1,099,752
|{{TM|1RB0RF_1RC1RZ_0LD1RF_0RA1LE_0LC1LF_1LE0RG_0LE1RA}}
|10 ↑↑ 136.64
|[https://drive.google.com/drive/folders/1-eGxVc3kmGIEJFShG4olPX3sGci2SPaA?usp=sharing Google Drive folder]
|-
|20-23xxxx
| @C7X
|Yes
|Yes
|4,528,827
|{{TM|1RB1LA_1LC0RF_0LD0RD_1RF1LE_1LB1RZ_1RG0RA_0RA0LA}}
|10 ↑↑ 192.67
| [https://drive.google.com/drive/folders/11iGTKsvu2Y7aFrwOcWS1LYvcN6i_7-JM?usp=sharing Google Drive folder]
|-
|24xxxx
|Andrew Ducharme
|Yes
|Yes
|712,356
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}*
|data-sort-value="10 ↑↑ 9999"|<math>2 \uparrow^{11} 2 \uparrow^{11} 3^*</math>
|[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|25-34xxxx
|@stokastic
|Yes
|Yes
|10,339,816
|{{TM|1RB0LC_1LC0LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LC}}
|10 ↑↑ 140.28
|[https://drive.google.com/drive/folders/16_qIdWWD-wolj6zURB5ZSbY-otI4zoUF?usp=sharing Google Drive folder]
|-
|35-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/1yQFLcznvNzEF9uWXL1xkJhhfxPDtbC7x?usp=drive_link Google Drive folder]
|-
|40-47xxxx
|Andrew Ducharme
|Yes
|Yes
|6,181,327
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LF_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|48xxxx
|@star
|Yes
|No
|954,005
|TBD
|TBD
|[https://drive.google.com/file/d/1HbIX46_6V-etFWTv4FvWZmb7AHIiWB1v/view?usp=sharing Google Drive file]
|-
|49xxxx
|
Tobiáš Brichta<br/>
Terry Ligocki
|Yes
|Yes
|804,722
|{{TM|1RB0LG_1RC0RG_0LD1RE_1RD0RE_1LF1RB_0LA1RZ_1LC1LG}}
|10 ↑↑ 126.20
|
[https://drive.google.com/drive/folders/1-csgJ5uSIX3SKlqTkSnhkUuEYLKgCw81 Tobiáš Brichta]<br/>
[https://drive.google.com/drive/folders/1yQFLcznvNzEF9uWXL1xkJhhfxPDtbC7x?usp=drive_link Terry Ligocki]
|-
|50xxxx
|
@prurq<br/>
Andrew Ducharme
|Yes
|Yes
|797,224
|{{TM|1RB0RD_1RC0RA_0RD1LD_0LE1LF_1LA0LG_0LC1LB_1LC1RZ}}
|10 ↑↑ 115.52
|[https://drive.google.com/drive/folders/145H4sT4F9KJYGSrlIETZdBOIMR7krLQm Google Drive folder]
|-
|51-53xxxx
|
@gerbil5709<br/>
Terry Ligocki
|Yes
|Yes
|3,016,175
|{{TM|1RB0LC_1LC0LD_1LA1LB_0LG1RE_0RF0RF_0RA1RE_1RZ1LC}}
|10 ↑↑ 140.28
|
[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing @gerbil5709]<br/>
[https://drive.google.com/drive/folders/1yQFLcznvNzEF9uWXL1xkJhhfxPDtbC7x?usp=drive_link Terry Ligocki]
|-
|54-59xxxx
|Terry Ligocki
|Yes
|Yes
|5,689,850
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_0RF0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|[https://drive.google.com/drive/folders/1yQFLcznvNzEF9uWXL1xkJhhfxPDtbC7x?usp=drive_link Google Drive folder]
|-
|60-64xxxx
|
@gerbil5709<br/>
Terry Ligocki
|Yes
|Yes
|3,817,876
||{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LE_0RD0LG_1LB0LE}}
|10 ↑↑ 519.20
|
[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing @gerbil5709]<br/>
[https://drive.google.com/drive/folders/1yQFLcznvNzEF9uWXL1xkJhhfxPDtbC7x?usp=drive_link Terry Ligocki]
|-
|65-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/1yQFLcznvNzEF9uWXL1xkJhhfxPDtbC7x?usp=drive_link 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]
|-
|70-71xxxx
|@hipparcos
|Yes
|Yes
|1,899,094
|{{TM|1RB1RZ_1LC1RD_0LD0LC_1LE1RA_1LF0LE_1RF0RG_1RG0RD}}
|10 ↑↑ 77.50
|[https://github.com/jhuang97/bb7x2/releases Github release]
|-
|72-79xxxx
|Terry Ligocki
|Yes
|Yes
|7,627,514
|{{TM|1RB0RB_1LC1RG_1RD1RC_1RE0RA_1LF0LB_1RF0LE_0RD1RZ}}
|10 ↑↑ 228.78
|[https://drive.google.com/drive/folders/1yQFLcznvNzEF9uWXL1xkJhhfxPDtbC7x?usp=drive_link Google Drive folder]
|-
|80-81xxxx
|@xnoobspeakable
|Yes
|Yes
|1,537,533
|{{TM|1RB0LA_0RC1RZ_0RD0RG_1LE1RA_1LF1LD_1RG0RG_1RD1RC}}
|10 ↑↑ 74.85
|[https://drive.google.com/drive/folders/1TpuEC7KottEmvsFnCREugnlVMPaY5ZHi?usp=sharing Google Drive folder]
|-
|82-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/1yQFLcznvNzEF9uWXL1xkJhhfxPDtbC7x?usp=drive_link Google Drive folder]
|}
<nowiki>*</nowiki>The current BB(7) champion TM {{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}* was discovered by Pavel Kropitz in the enumeration of subtask 243308. The remaining subtasks in the 24xxxx range were enumerated and filtered by Andrew Ducharme.
[[Category:BB Domain]]

BB(7)

2025-07-16T18:04:22Z

Isokate: /* Current Progress */

The 7-state, 2-symbol Busy Beaver problem, '''BB(7)''', refers to the unsolved 7<sup>th</sup> value of the [[Busy Beaver function]]. With the compilation of the [[Cryptid]] machine [[Bigfoot]] into a 7-state, 2-symbol machine in May 2024, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(7).

The current BB(7) champion {{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}} was discovered by Pavel Kropitz in May 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. In 1964, Milton Green designed a machine that had [[sigma score]] 22,961. In 2014, Wythagoras modified a BB(6) champion 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. A few days later, Pavel found a TM that outpaces all of them.

Pavel's champion is enumerated in subtask 243308.

== 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 sortable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|data-sort-value="10 ↑↑ 9999"|<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|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LE_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|Andrew Ducharme
|-
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LE_0RD0LG_1LB0LE}}
|10 ↑↑ 519.20
|@gerbil5709, Terry Ligocki
|-
|{{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_1RC0LE_0RD1RB_1LE1RA_1LF0LG_0LG0RG_1LB1RG}}
|10 ↑↑ 243.88
|@Iijil, Andrew Ducharme
|-
|{{TM|1RB0RB_1LC1RG_1RD1RC_1RE0RA_1LF0LB_1RF0LE_0RD1RZ}}
|10 ↑↑ 228.78
|Terry Ligocki
|-
|{{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|1RB0LD_0LC1RZ_1RA0RD_1RE1LD_1LF0RC_0LG1LE_1RC0LD}}
|10 ↑↑ 192.67
|Andrew Ducharme
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE1LG_1RF0LG_0RA0LA_0RF1RZ}}
|10 ↑↑ 192.67
|Andrew Ducharme
|-
|{{TM|1RB1LA_1LC0RF_0LD0RD_1RF1LE_1LB1RZ_1RG0RA_0RA0LA}}
|10 ↑↑ 192.67
|@C7X
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE0LA_1RF0RA_0RG0LA_1RB1RZ}}
|10 ↑↑ 192.67
|@Iijil, Terry Ligocki
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE0LA_1RF0RA_1RG0LA_0LE1RZ}}
|10 ↑↑ 192.67
|@Iijil, Terry Ligocki
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE0LG_1RF0RA_0RA0LA_1RB1RZ}}
|10 ↑↑ 192.67
|@Iijil, Terry Ligocki
|}

The top 20 known halters with unique scores are:

{| class="wikitable sortable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|data-sort-value="10 ↑↑ 9999"|<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_1RC0LE_0RD1RB_1LE1RA_1LF0LG_0LG0RG_1LB1RG}}
|10 ↑↑ 243.88
|@Iijil, Andrew Ducharme
|-
|{{TM|1RB0RB_1LC1RG_1RD1RC_1RE0RA_1LF0LB_1RF0LE_0RD1RZ}}
|10 ↑↑ 228.78
|Terry Ligocki
|-
|{{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|1RB0RF_1RC1RZ_0LD1RF_0RA1LE_0LC1LF_1LE0RG_0LE1RA}}
|10 ↑↑ 136.64
|Katelyn Doucette, Andrew Ducharme
|-
|{{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|1RB0LD_1RC1RA_0RD1RG_1LE1LF_0LF1LE_0RA0LD_0RA1RZ}}
|10 ↑↑ 124.86
|Terry Ligocki
|-
|{{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|1RB0RG_1LC0LE_1LD0LB_0LE1RE_0RA1RF_0RD1RC_1RD1RZ}}
|10 ↑↑ 114.83
|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
|}

== 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"). A cell in '''bold font''' means no one has signed up to do either the enumeration or apply the Ligocki code for that row's subtasks. You can help, especially with applying the Ligocki filters! Download the enumerated TMs from the linked source in the far right column of the table below, put your name alongside the enumerator's in the "Done by" column, turn off the bold font on your chosen task range, and return with the number of holdouts, the maximum score TM, and its approximate sigma value when you're done.

After downloading the Ligocki codebase `busy-beaver-main` [https://github.com/sligocki/busy-beaver here], you can install the dependencies by running `python3 -m pip install -r requirements.txt`, then perform the filtering on holdouts from subtasks between start_number and end_number by running the bash command:<syntaxhighlight lang="bash">
for x in {start_number..end_number}; do busy-beaver-main/Code/Enumerate.py --infile your-path-to-holdouts/holdouts_${x}.txt --outfile your-save-path/bb7_${x}.out.pb -r --no-steps --exp-linear-rules --max-loops=100_000 --block-mult=2 --force --save-freq=100; done
</syntaxhighlight>
{| class="wikitable sortable 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
|-
|00-01xxxx
|@Iijil
|Yes
|Yes
|1,545,673
|{{TM|1RB0LE_1RC0RA_1RD0RC_1LE1LD_1LA0LF_0LA0LG_1RZ0RD}}
|10 ↑↑ 246.32
|[https://drive.google.com/drive/folders/1wniwrAuvsHfkvro8Tg65WAMNZEuIekzD Google Drive folder]
|-
|02-04xxxx
|
@Iijil<br/>
Terry Ligocki
|Yes
|Yes
|2,279,734
|{{TM|1RB0LF_1RC1RA_1RD0RG_1LE1RZ_1LA0LF_1RA1LE_0RE1RG}}
|10 ↑↑ 93.81
|
[https://drive.google.com/drive/folders/1wniwrAuvsHfkvro8Tg65WAMNZEuIekzD @Iijil]<br/>
[https://drive.google.com/drive/folders/1uaSs-CfT6yX2UIboCaNi2U651bEYa_y0?usp=drive_link Terry Ligocki]
|-
|05-09xxxx
|
@Iijil<br/>
Andrew Ducharme
|Yes
|Yes
|3,889,955
|{{TM|1RB1RZ_1RC0LE_0RD1RB_1LE1RA_1LF0LG_0LG0RG_1LB1RG}}
|10 ↑↑ 243.88
|
[https://drive.google.com/drive/folders/1wniwrAuvsHfkvro8Tg65WAMNZEuIekzD @Iijil]<br/>
[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Andrew]
|-
|10-12xxxx
|Andrew Ducharme
|Yes
|Yes
|2,708,888
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LE_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|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]
|-
|14-16xxxx
|Andrew Ducharme
|Yes
|Yes
|2,701,637
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_0RF0LD_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|17-18xxxx
|
@gerbil5709<br/>
Terry Ligocki
|Yes
|Yes
|1,898,156
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE0LA_1RF0RA_0RG0LA_1RB1RZ}}
|10 ↑↑ 192.67
|
[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing @gerbil5709]<br/>
[https://drive.google.com/drive/folders/1uaSs-CfT6yX2UIboCaNi2U651bEYa_y0?usp=drive_link Terry Ligocki]
|-
|19xxxx
|Katelyn Doucette
|Yes
|Yes
|1,601,356
|{{TM|1RB0RF_1RC1RZ_0LD1RF_0RA1LE_0LC1LF_1LE0RG_0LE1RA}}
|10 ↑↑ 136.64
|[https://drive.google.com/drive/folders/1-eGxVc3kmGIEJFShG4olPX3sGci2SPaA?usp=sharing Google Drive folder]
|-
|20-22xxxx
| rowspan="2" | @C7X
|Yes
|Yes
|3,347,034
|{{TM|1RB1LA_1LC0RF_0LD0RD_1RF1LE_1LB1RZ_1RG0RA_0RA0LA}}
|10 ↑↑ 192.67
| rowspan="2" | [https://drive.google.com/drive/folders/11iGTKsvu2Y7aFrwOcWS1LYvcN6i_7-JM?usp=sharing Google Drive folder]
|-
|23xxxx
|Yes
|No
|1,049,137
|TBD
|TBD
|-
|24xxxx
|Andrew Ducharme
|Yes
|Yes
|712,356
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}*
|data-sort-value="10 ↑↑ 9999"|<math>2 \uparrow^{11} 2 \uparrow^{11} 3^*</math>
|[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|25-34xxxx
|@stokastic
|Yes
|Yes
|10,339,816
|{{TM|1RB0LC_1LC0LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LC}}
|10 ↑↑ 140.28
|[https://drive.google.com/drive/folders/16_qIdWWD-wolj6zURB5ZSbY-otI4zoUF?usp=sharing Google Drive folder]
|-
|35-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]
|-
|40-47xxxx
|Andrew Ducharme
|Yes
|Yes
|6,181,327
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LF_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|48xxxx
|@star
|No
|No
|TBD
|TBD
|TBD
|
|-
|49xxxx
|
Tobiáš Brichta<br/>
Terry Ligocki
|Yes
|Yes
|804,722
|{{TM|1RB0LG_1RC0RG_0LD1RE_1RD0RE_1LF1RB_0LA1RZ_1LC1LG}}
|10 ↑↑ 126.20
|
[https://drive.google.com/drive/folders/1-csgJ5uSIX3SKlqTkSnhkUuEYLKgCw81 Tobiáš Brichta]<br/>
[https://drive.google.com/drive/folders/1uaSs-CfT6yX2UIboCaNi2U651bEYa_y0?usp=drive_link Terry Ligocki]
|-
|50xxxx
|
@prurq<br/>
Andrew Ducharme
|Yes
|Yes
|797,224
|{{TM|1RB0RD_1RC0RA_0RD1LD_0LE1LF_1LA0LG_0LC1LB_1LC1RZ}}
|10 ↑↑ 115.52
|[https://drive.google.com/drive/folders/145H4sT4F9KJYGSrlIETZdBOIMR7krLQm Google Drive folder]
|-
|51-53xxxx
|
@gerbil5709<br/>
Terry Ligocki
|Yes
|Yes
|3,016,175
|{{TM|1RB0LC_1LC0LD_1LA1LB_0LG1RE_0RF0RF_0RA1RE_1RZ1LC}}
|10 ↑↑ 140.28
|
[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing @gerbil5709]<br/>
[https://drive.google.com/drive/folders/1uaSs-CfT6yX2UIboCaNi2U651bEYa_y0?usp=drive_link Terry Ligocki]
|-
|54-59xxxx
|Terry Ligocki
|Yes
|Yes
|5,689,850
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_0RF0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|60-64xxxx
|
@gerbil5709<br/>
Terry Ligocki
|Yes
|Yes
|3,817,876
||{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LE_0RD0LG_1LB0LE}}
|10 ↑↑ 519.20
|
[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing @gerbil5709]<br/>
[https://drive.google.com/drive/folders/1uaSs-CfT6yX2UIboCaNi2U651bEYa_y0?usp=drive_link Terry Ligocki]
|-
|65-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]
|-
|70-71xxxx
|@hipparcos
|Yes
|Yes
|1,899,094
|{{TM|1RB1RZ_1LC1RD_0LD0LC_1LE1RA_1LF0LE_1RF0RG_1RG0RD}}
|10 ↑↑ 77.50
|[https://github.com/jhuang97/bb7x2/releases Github release]
|-
|72-79xxxx
|Terry Ligocki
|Yes
|Yes
|7,627,514
|{{TM|1RB0RB_1LC1RG_1RD1RC_1RE0RA_1LF0LB_1RF0LE_0RD1RZ}}
|10 ↑↑ 228.78
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|80-81xxxx
|@xnoobspeakable
|Yes
|Yes
|1,537,533
|{{TM|1RB0LA_0RC1RZ_0RD0RG_1LE1RA_1LF1LD_1RG0RG_1RD1RC}}
|10 ↑↑ 74.85
|[https://drive.google.com/drive/folders/1TpuEC7KottEmvsFnCREugnlVMPaY5ZHi?usp=sharing Google Drive folder]
|-
|82-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]
|}
<nowiki>*</nowiki>The current BB(7) champion TM {{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}* was discovered by Pavel Kropitz in the enumeration of subtask 243308. The remaining subtasks in the 24xxxx range were enumerated and filtered by Andrew Ducharme.
[[Category:BB Domain]]

BB(7)

2025-07-10T23:02:44Z

Isokate: /* Current Progress */

The 7-state, 2-symbol Busy Beaver problem, '''BB(7)''', refers to the unsolved 7<sup>th</sup> value of the [[Busy Beaver function]]. With the compilation of the [[Cryptid]] machine [[Bigfoot]] into a 7-state, 2-symbol machine in May 2024, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(7).

The current BB(7) champion {{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}} was discovered by Pavel Kropitz in May 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. In 1964, Milton Green designed a machine that had [[sigma score]] 22,961. In 2014, Wythagoras modified a BB(6) champion 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. A few days later, Pavel found a TM that outpaces all of them.

Pavel's champion is enumerated in subtask 243308.

== 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 sortable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|data-sort-value="10 ↑↑ 9999"|<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|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LE_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|Andrew Ducharme
|-
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LE_0RD0LG_1LB0LE}}
|10 ↑↑ 519.20
|@gerbil5709, Terry Ligocki
|-
|{{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_1RC0LE_0RD1RB_1LE1RA_1LF0LG_0LG0RG_1LB1RG}}
|10 ↑↑ 243.88
|@Iijil, Andrew Ducharme
|-
|{{TM|1RB0RB_1LC1RG_1RD1RC_1RE0RA_1LF0LB_1RF0LE_0RD1RZ}}
|10 ↑↑ 228.78
|Terry Ligocki
|-
|{{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|1RB0LD_0LC1RZ_1RA0RD_1RE1LD_1LF0RC_0LG1LE_1RC0LD}}
|10 ↑↑ 192.67
|Andrew Ducharme
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE1LG_1RF0LG_0RA0LA_0RF1RZ}}
|10 ↑↑ 192.67
|Andrew Ducharme
|-
|{{TM|1RB1LA_1LC0RF_0LD0RD_1RF1LE_1LB1RZ_1RG0RA_0RA0LA}}
|10 ↑↑ 192.67
|@C7X
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE0LA_1RF0RA_0RG0LA_1RB1RZ}}
|10 ↑↑ 192.67
|@Iijil, Terry Ligocki
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE0LA_1RF0RA_1RG0LA_0LE1RZ}}
|10 ↑↑ 192.67
|@Iijil, Terry Ligocki
|-
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE0LG_1RF0RA_0RA0LA_1RB1RZ}}
|10 ↑↑ 192.67
|@Iijil, Terry Ligocki
|}

The top 20 known halters with unique scores are:

{| class="wikitable sortable"
!TM
!Approximate sigma score
!Discoverer
|-
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}
|data-sort-value="10 ↑↑ 9999"|<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_1RC0LE_0RD1RB_1LE1RA_1LF0LG_0LG0RG_1LB1RG}}
|10 ↑↑ 243.88
|@Iijil, Andrew Ducharme
|-
|{{TM|1RB0RB_1LC1RG_1RD1RC_1RE0RA_1LF0LB_1RF0LE_0RD1RZ}}
|10 ↑↑ 228.78
|Terry Ligocki
|-
|{{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|1RB0LD_1RC1RA_0RD1RG_1LE1LF_0LF1LE_0RA0LD_0RA1RZ}}
|10 ↑↑ 124.86
|Terry Ligocki
|-
|{{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|1RB0RG_1LC0LE_1LD0LB_0LE1RE_0RA1RF_0RD1RC_1RD1RZ}}
|10 ↑↑ 114.83
|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|1RB0RC_1LC1LD_1RA0RD_0LF1LE_0LB1LA_0RE0LG_1LB1RZ}}
|10 ↑↑ 114.37
|@C7X
|}

== 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"). A cell in '''bold font''' means no one has signed up to do either the enumeration or apply the Ligocki code for that row's subtasks. You can help, especially with applying the Ligocki filters! Download the enumerated TMs from the linked source in the far right column of the table below, put your name alongside the enumerator's in the "Done by" column, turn off the bold font on your chosen task range, and return with the number of holdouts, the maximum score TM, and its approximate sigma value when you're done.

After downloading the Ligocki codebase `busy-beaver-main` [https://github.com/sligocki/busy-beaver here], you can install the dependencies by running `python3 -m pip install -r requirements.txt`, then perform the filtering on holdouts from subtasks between start_number and end_number by running the bash command:<syntaxhighlight lang="bash">
for x in {start_number..end_number}; do busy-beaver-main/Code/Enumerate.py --infile your-path-to-holdouts/holdouts_${x}.txt --outfile your-save-path/bb7_${x}.out.pb -r --no-steps --exp-linear-rules --max-loops=100_000 --block-mult=2 --force --save-freq=100; done
</syntaxhighlight>
{| class="wikitable sortable 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="2"|@Iijil
|Yes
|Yes
|728,495
|{{TM|1RB0RF_1RC1LF_0RD0RD_1LE0LB_1RA1RZ_1LG1RA_1LD0RC}}
|10 ↑↑ 45.64
| rowspan="2" |[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
| rowspan="3"|
@Iijil<br/>
Terry Ligocki
|Yes
|Yes
|738,265
|{{TM|1RB0LD_1LC1LD_1RE0RA_1LB0RG_1RZ1RF_0LC1RF_0RE1RD}}
|10 ↑↑ 26.82
| rowspan="3" |
[https://drive.google.com/drive/folders/1wniwrAuvsHfkvro8Tg65WAMNZEuIekzD @Iijil]<br/>
[https://drive.google.com/drive/folders/1uaSs-CfT6yX2UIboCaNi2U651bEYa_y0?usp=drive_link Terry Ligocki]
|-
|03xxxx
|Yes
|Yes
|810910
|{{TM|1RB0RE_1LB0LC_1RD1LG_0RA1RZ_1RF1RE_0RB1LC_1LF0LE}}
|10 ↑↑ 47.06390
|-
|04xxxx
|Yes
|No
|955,711
|TBD
|TBD
|-
|05-09xxxx
|
@Iijil<br/>
Andrew Ducharme
|Yes
|Yes
|3,889,955
|{{TM|1RB1RZ_1RC0LE_0RD1RB_1LE1RA_1LF0LG_0LG0RG_1LB1RG}}
|10 ↑↑ 243.88
|[https://uoregon-my.sharepoint.com/:f:/r/personal/aducharm_uoregon_edu/Documents/bb7x2?csf=1&web=1&e=VwAOfU OneDrive folder]
|-
|10-12xxxx
|Andrew Ducharme
|Yes
|Yes
|2,708,888
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LE_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|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]
|-
|14-16xxxx
|Andrew Ducharme
|Yes
|Yes
|2,701,637
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_0RF0LD_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|17xxxx
| rowspan="2" |
@gerbil5709<br/>
Terry Ligocki
|Yes
|Yes
|1,101,230
|{{TM|1RB1LA_1LC0RE_0LD1LB_1RE0LA_1RF0RA_0RG0LA_1RB1RZ}}
|10 ↑↑ 192.67
| rowspan="2" |
[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing @gerbil5709]<br/>
[https://drive.google.com/drive/folders/1uaSs-CfT6yX2UIboCaNi2U651bEYa_y0?usp=drive_link Terry Ligocki]
|-
|18xxxx
|Yes
|Yes
|796,926
|{{TM|1RB0RF_1LC0RA_1LD0LB_1LE0LD_1RA1RE_0RB0RG_1RZ0LE}}
|~10 ↑↑ 93.88
|-
|19xxxx
|Katelyn Doucette
|Yes
|No
|1,433,181
|TBD
|TBD
|[https://drive.google.com/file/d/1KnEvE3K7pKwf-2ibi3TRgrKb14yELQM-/view?usp=sharing Google Drive folder]
|-
|20-21xxxx
| rowspan="2" | @C7X
|Yes
|Yes
|1,543,948
|{{TM|1RB1LA_1LC0RF_0LD0RD_1RF1LE_1LB1RZ_1RG0RA_0RA0LA}}
|10 ↑↑ 192.67
| rowspan="2" | [https://drive.google.com/drive/folders/11iGTKsvu2Y7aFrwOcWS1LYvcN6i_7-JM?usp=sharing Google Drive folder]
|-
|22-23xxxx
|Yes
|No
|2,008,495
|TBD
|TBD
|-
|24xxxx
|Andrew Ducharme
|Yes
|Yes
|712,356
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}*
|data-sort-value="10 ↑↑ 9999"|<math>2 \uparrow^{11} 2 \uparrow^{11} 3^*</math>
|[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|25-34xxxx
|@stokastic
|Yes
|Yes
|10,339,816
|{{TM|1RB0LC_1LC0LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LC}}
|10 ↑↑ 140.28
|[https://drive.google.com/drive/folders/16_qIdWWD-wolj6zURB5ZSbY-otI4zoUF?usp=sharing Google Drive folder]
|-
|35-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]
|-
|40-47xxxx
|Andrew Ducharme
|Yes
|Yes
|6,181,327
|{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LF_0RD1LF_1LB0LE}}
|10 ↑↑ 519.20
|[https://drive.google.com/drive/folders/16uDjgOahkhAMWv3v-YWmxJG7xxsBvj4h?usp=sharing Google Drive folder]
|-
|48xxxx
|@star
|No
|No
|TBD
|TBD
|TBD
|
|-
|49xxxx
|Tobiáš Brichta
|Yes
|No
|1,049,506
|TBD
|TBD
|[https://drive.google.com/drive/folders/1-csgJ5uSIX3SKlqTkSnhkUuEYLKgCw81 Google Drive folder]
|-
|50xxxx
|
@prurq<br/>
Andrew Ducharme
|Yes
|Yes
|797,224
|{{TM|1RB0RD_1RC0RA_0RD1LD_0LE1LF_1LA0LG_0LC1LB_1LC1RZ}}
|10 ↑↑ 115.52
|[https://drive.google.com/drive/folders/145H4sT4F9KJYGSrlIETZdBOIMR7krLQm Google Drive folder]
|-
|51xxxx
| rowspan="3" |
@gerbil5709<br/>
Terry Ligocki
|Yes
|Yes
|1,101,195
|{{TM|1RB1RC_0RC1RB_0LD0RA_1LE0RA_1LF1LD_0LA1LG_0LD1RZ}}
|10 ↑↑ 132.84
| rowspan="3" |
[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing @gerbil5709]<br/>
[https://drive.google.com/drive/folders/1uaSs-CfT6yX2UIboCaNi2U651bEYa_y0?usp=drive_link Terry Ligocki]
|-
|52xxxx
|Yes
|Yes
|807,349
|{{TM|1RB0LG_1LC0RA_1LD0LB_0LE0RD_0RF1LA_1LA1RE_1RE1RZ}}
|10 ↑↑ 61.28
|-
|53xxxx
|Yes
|Yes
|1,107,631
|{{TM|1RB0LC_1LC0LD_1LA1LB_0LG1RE_0RF0RF_0RA1RE_1RZ1LC}}
|10 ↑↑ 140.28
|-
|54-59xxxx
|Terry Ligocki
|Yes
|Yes
|5,689,850
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_0RF0RF_0RA1RE_1RZ1LA}}
|10 ↑↑ 188.28
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|60-64xxxx
|
@gerbil5709<br/>
Terry Ligocki
|Yes
|Yes
|3,817,876
||{{TM|1RB1RZ_0RC0RE_1LD1LA_1LC0LG_0RF1LE_0RD0LG_1LB0LE}}
|10 ↑↑ 519.20
|
[https://drive.google.com/drive/folders/1kAvBebeF09CEVocCk5bGKlDJfRN8co_i?usp=sharing @gerbil5709]<br/>
[https://drive.google.com/drive/folders/1uaSs-CfT6yX2UIboCaNi2U651bEYa_y0?usp=drive_link Terry Ligocki]
|-
|65-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]
|-
|70-71xxxx
|@hipparcos
|Yes
|Yes
|1,899,094
|{{TM|1RB1RZ_1LC1RD_0LD0LC_1LE1RA_1LF0LE_1RF0RG_1RG0RD}}
|10 ↑↑ 77.50
|[https://github.com/jhuang97/bb7x2/releases Github release]
|-
|72-79xxxx
|Terry Ligocki
|Yes
|Yes
|7,627,514
|{{TM|1RB0RB_1LC1RG_1RD1RC_1RE0RA_1LF0LB_1RF0LE_0RD1RZ}}
|10 ↑↑ 228.78
|[https://drive.google.com/drive/folders/1_lIqfvj4_J7WWl5LOBUp_pntoI99QYui Google Drive folder]
|-
|80xxxx
| rowspan="2" |@xnoobspeakable
|Yes
|Yes
|733,278
|{{TM|1RB0LD_0RC0RE_1LD0RA_1LA0LF_1RC1RC_1LG1RZ_1LA1LE}}
|10 ↑↑ 40.66
| rowspan="2" |[https://drive.google.com/drive/folders/1TpuEC7KottEmvsFnCREugnlVMPaY5ZHi?usp=sharing Google Drive folder]
|-
|81xxxx
|Yes
|No
|1,046,139
|TBD
|TBD
|-
|82-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]
|}
<nowiki>*</nowiki>The current BB(7) champion TM {{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF}}* was discovered by Pavel Kropitz in the enumeration of subtask 243308. The remaining subtasks in the 24xxxx range were enumerated and filtered by Andrew Ducharme.
[[Category:BB Domain]]

BB(6)

2025-06-11T01:55:28Z

Isokate: /* Top Halters */

The 6-state, 2-symbol Busy Beaver problem '''BB(6)''' is unsolved. With the discovery of [[Antihydra]] in 2024, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(6).

The current BB(6) champion {{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}} was discovered by Pavel Kropitz in 2022 proving the lower bound:<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/06/21/bb-6-2-t15.html "BB(6, 2) > 10↑↑15"]</ref><ref>Pascal Michel. [https://bbchallenge.org/~pascal.michel/ha#tm62 Historical survey of Busy Beavers]</ref>

<math display="block">S(6) > \Sigma(6) > 10 \uparrow\uparrow 15</math>

== Techniques ==
In order to simulate the current BB(6) champion requires [[Accelerated simulator|accelerated simulation]] that can handle Collatz Level 2 [[Inductive rule|inductive rules]]. In other words, it requires a simulator that can prove the rules:

<math display="block">\begin{array}{lcl}
C(4k) & \to & {\operatorname{Halt}}\Big(\frac{3^{k+3} - 11}{2}\Big) \\
C(4k+1) & \to & C\Big(\frac{3^{k+3} - 11}{2}\Big) \\
C(4k+2) & \to & C\Big(\frac{3^{k+3} - 11}{2}\Big) \\
C(4k+3) & \to & C\Big(\frac{3^{k+3} + 1}{2}\Big) \\
\end{array}</math>

and also compute the remainder mod 3 of numbers produced by applying these rules 15 times (which requires some fancy math related to [[wikipedia:Euler's_totient_function|Euler's totient function]]).

== Cryptids ==
Several [[Turing machines]] have been found that are [[Cryptids]], considered so because each of them have a [[Collatz-like]] halting problem, a type of problem that is generally difficult to solve. However, probabilistic arguments have allowed all but one of them to be categorized as [[probviously]] halting or probviously non-halting.

Probviously non-halting Cryptids:

* [[Antihydra]]
* {{TM|1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA|undecided}}, a variant of [[Hydra]] and Antihydra
* {{TM|1RB1LD_1RC1RE_0LA1LB_0LD1LC_1RF0RA_---0RC|undecided}}, similar to Antihydra
* {{TM|1RB0LD_1RC1RF_1LA0RA_0LA0LE_1LD1LA_0RB---|undecided}}, similar to Antihydra
* {{TM|1RB0LB_1LC0RE_1LA1LD_0LC---_0RB0RF_1RE1RB|undecided}}, similar to Antihydra

Probviously halting Cryptids:

* [[Lucy's Moonlight]]
* {{TM|1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC|undecided}}, a family of 16 related TMs
* {{TM|1RB1RE_1LC1LD_---1LA_1LB1LE_0RF0RA_1LD1RF}}
* {{TM|1RB0RE_1LC1LD_0RA0LD_1LB0LA_1RF1RA_---1LB}}
* {{TM|1RB0LC_0LC0RF_1RD1LC_0RA1LE_---0LD_1LF1LA}}
* {{TM|1RB0LC_1LC0RD_1LF1LA_1LB1RE_1RB1LE_---0LE}}
Although {{TM|1RB1LE_0LC0LB_1RD1LC_1RD1RA_1RF0LA_---1RE}} behaves similarly to the probviously halting Cryptids, it is estimated to have a 3/5 chance of becoming a [[translated cycler]] and a 2/5 chance of halting.

There are a few machines considered notable for their chaotic behaviour, but which have not been classified as Cryptids due to seemingly lacking a connection to any known open mathematical problems, such as Collatz-like problems.

Potential Cryptids:

* {{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}
* {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}}
* {{TM|1RB0RB_1LC1RE_1LF0LD_1RA1LD_1RC1RB_---1LC|undecided}}
* {{TM|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD}}

== Top Halters ==
Below is a table of the machines with the 10 highest known runtimes.<ref>Shawn Ligocki's list of 6-state, 2-symbol machines with large runtimes ([https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/6x2.txt Link])</ref> Their sigma scores are expressed using an extension of Knuth's up-arrow notation.<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/06/25/ext-up-notation.html "Extending Up-arrow Notation"]</ref>
{| class="wikitable"
|+Top Known BB(6) Halters
!TM
!approximate sigma score
|-
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE}}
|10 ↑↑ 15.60465
|-
|{{TM|1RB0LF_1RC1RB_1LD0RA_1LB0LE_1RZ0LC_1LA1LF}}
|10 ↑↑ 7.52390
|-
|{{TM|1RB0LF_1RC1RB_1LD0RA_1RF0LE_1RZ0LC_1LA1LF}}
|10 ↑↑ 7.52390
|-
|{{TM|1RB0LF_1RC1RB_1LD0RA_1LF0LE_1RZ0LC_1LA1LF}}
|10 ↑↑ 7.52390
|-
|{{TM|1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA}}
|10 ↑↑ 7.23619
|-
|{{TM|1RB1RA_1LC1LE_1RE0LD_1LC0LF_1RZ0RA_0RA0LB}}
|10 ↑↑ 6.96745
|-
|{{TM|1RB0RF_1LC0RA_1RZ0LD_1LE1LD_1RB1RC_0LD0RE}}
|10 ↑↑ 5.77573
|-
|{{TM|1RB0LA_1LC1LF_0LD0LC_0LE0LB_1RE0RA_1RZ1LD}}
|10 ↑↑ 5.63534
|-
|{{TM|1RB1RE_1LC1LF_1RD0LB_1LE0RC_1RA0LD_1RZ1LC}}
|10 ↑↑ 5.56344
|-
|{{TM|1RB0LE_0RC1RA_0LD1RF_1RE0RB_1LA0LC_0RD1RZ}}
|10 ↑↑ 5.12468
|}
The runtimes are presumed to be about <math>\text{score}^2</math> which is roughly indistinguishable in tetration notation.

== Holdouts ==
@mxdys's informal [[Holdouts lists|holdouts list]] is down to 4408 machines as of 8 Nov 2024.

== References ==
<references />
[[Category:BB Domain]]

1RB1RA 1LC1LE 1RE0LD 1LC0LF 1RZ0RA 0RA0LB

2025-06-11T01:50:27Z

Isokate: Created page with "{{Machine|1RB1RA_1LC1LE_1RE0LD_1LC0LF_---0RA_0RA0LB}} {{TM|1RB1RA_1LC1LE_1RE0LD_1LC0LF_1RZ0RA_0RA0LB}} is a tetrational halting BB(6) TM first discovered and analyzed by @poppuncher. It was shared on Discord on 5 Jun 2025 ([https://discord.com/channels/960643023006490684/1380384286942822561 Discord Link]). It is a translated counter that halts with a final sigma score of roughly <math>10 \uparrow \uparrow 6.96745</math>. == Analysis by @poppuncher == Most of the ini..."

{{Machine|1RB1RA_1LC1LE_1RE0LD_1LC0LF_---0RA_0RA0LB}}
{{TM|1RB1RA_1LC1LE_1RE0LD_1LC0LF_1RZ0RA_0RA0LB}} is a tetrational halting [[BB(6)]] TM first discovered and analyzed by @poppuncher. It was shared on Discord on 5 Jun 2025 ([https://discord.com/channels/960643023006490684/1380384286942822561 Discord Link]). It is a translated counter that halts with a final sigma score of roughly <math>10 \uparrow \uparrow 6.96745</math>.

== Analysis by @poppuncher ==
Most of the initial analysis was done on its sister machine {{TM|1RB0RF_1LC0RA_1RZ0LD_1LE1LD_1RB1RC_0LD0RE}} which has identical behavior but with different starting conditions. In contrast, this machine instead halts with a smaller, though still enormous, sigma score of roughly <math>10 \uparrow \uparrow 5.77573</math>. The following explanation describes this sister machine, but aside from the starting conditions and states, it applies to the larger machine as well.

<pre>
basically, there is a unary counter on one side and a weird binary counter on the other side.

the weird binary counter behaves as if counting the number of bit flips required to increment a binary number (let's call it A) of a given length n, until it reaches 2^n. the number of flips are written to the unary counter, which then resets, and the process starts again with a new binary string.

For example, let n = 6 and A = 48, which is 110000 in binary, then it will count up to 1000000. there is a formula for the number of bit flips required, which is 2^(n+1) - 2*A - 1 + pop_count(A), where pop_count is the number of '1's in the binary representation of A. In this example
it evaluates to 2^7-2*48-1+2 = 33.

Note that leading zeroes are allowed, so if n = 9 and A = 48, then
we are counting 000110000 until it reaches 1000000000, and the count will be 2^10-2*48-1+2 = 417.

now for the halting part, i can prove that the following rules:
A> 0 1^(5n+0) -> (10 110)^n <D 01
A> 0 1^(5n+1) -> (10 110)^n 10 <D 01
A> 0 1^(5n+2) -> (10 110)^n 110 <D 01
A> 0 1^(5n+3) -> (10 110)^n 10 10 10 <D 01
A> 0 1^(5n+4) -> Halt(3n+3)

the binary counter encodes the binary string such that "10" on the tape corresponds to 0, and "110" corresponds to 1, (also the most significant bit is on the right, so we need to flip it)

for example at t = 159, the tape is 0^inf 10 10 10 10 110 110 <D 01 0^inf, which corresponds to 110000 (this is also the example earlier, with n = 6 and A = 48).
with this in mind, i got the following rules:
A(n) is the numerical value of the binary string, L(n) is the length of the string, P(n) is the count of '1's in the string, and R(n) is the amount of increments made on the unary counter, counting the number of bit flips before it resets
initial conditions: A(1) = 0, L(1) = 2
P(n) := pop_count(A(n))
R(n) := 2^(1 + L(n)) - 2*A(n) - 1 + P(n)
k(n) := R(n)//5 (division without remainder)
r(n) := R(n) % 5, (so R(n) = 5*k(n) + r(n))

then we have P(1) = 0, R(1) = 7;

the rules:
if R(n) mod 5 == 4 then halt
otherwise
let a(r) = {0, 1, 1, 3} (for 0 <= r < 4)
then
L(n+1) = L(n) + 1 + 2 * k(n) + a(r(n))
A(n+1) = 2 ^ (2 + L(n)) * ( 2^(2*k(n)) - 1 ) / 3 + (if r(n) = 2 then 2 ^ ( L(n)+1 + 2*k(n) ) otherwise 0)
P(n+1) = pop_count(A(n+1)) = k(n) + (if r(n) = 2 then 1 otherwise 0)
</pre>

== Analysis by [[User:isokate|Katelyn Doucette]]==
The machine follows these rules:

<pre>
Let s = 2^{b+2} - 2 + 2^{b+2}((4^k - 1)/3) + k

START = A(1, 3)

A(5k + 0, b) -> A(s + 1, b + 2k + 1)

A(5k + 1, b) -> A(s + 1 + 2^{(b+2k+1)+1}, b + 2k + 2)

A(5k + 2, b) -> A(s + 2, b + 2k + 2)

A(5k + 3, b) -> A(s + 1 + 2^{b+2k+2}(7), b + 2k + 4)

A(5k + 4, b) -> Halt(b + 3k + 4)
</pre>

And runs through seven of these resets before reaching <math>5k + 4</math> and halting.

These configurations are identifiable as the transition of this form:
<code>1^(5k+r) 01 <B (01)^b</code>

== Evaluation==
Both @poppuncher and [[User:isokate|Katelyn Doucette]]'s rules were evaluated on both machines and line up with one another providing high confidence that the analyses and final sigma scores are correct.

@poppuncher's rules were evaluated by [[User:sligocki|Shawn Ligocki]].

BB(6)

2025-06-11T01:17:50Z

Isokate: /* Top Halters */

The 6-state, 2-symbol Busy Beaver problem '''BB(6)''' is unsolved. With the discovery of [[Antihydra]] in 2024, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(6).

The current BB(6) champion {{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}} was discovered by Pavel Kropitz in 2022 proving the lower bound:<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/06/21/bb-6-2-t15.html "BB(6, 2) > 10↑↑15"]</ref><ref>Pascal Michel. [https://bbchallenge.org/~pascal.michel/ha#tm62 Historical survey of Busy Beavers]</ref>

<math display="block">S(6) > \Sigma(6) > 10 \uparrow\uparrow 15</math>

== Techniques ==
In order to simulate the current BB(6) champion requires [[Accelerated simulator|accelerated simulation]] that can handle Collatz Level 2 [[Inductive rule|inductive rules]]. In other words, it requires a simulator that can prove the rules:

<math display="block">\begin{array}{lcl}
C(4k) & \to & {\operatorname{Halt}}\Big(\frac{3^{k+3} - 11}{2}\Big) \\
C(4k+1) & \to & C\Big(\frac{3^{k+3} - 11}{2}\Big) \\
C(4k+2) & \to & C\Big(\frac{3^{k+3} - 11}{2}\Big) \\
C(4k+3) & \to & C\Big(\frac{3^{k+3} + 1}{2}\Big) \\
\end{array}</math>

and also compute the remainder mod 3 of numbers produced by applying these rules 15 times (which requires some fancy math related to [[wikipedia:Euler's_totient_function|Euler's totient function]]).

== Cryptids ==
Several [[Turing machines]] have been found that are [[Cryptids]], considered so because each of them have a [[Collatz-like]] halting problem, a type of problem that is generally difficult to solve. However, probabilistic arguments have allowed all but one of them to be categorized as [[probviously]] halting or probviously non-halting.

Probviously non-halting Cryptids:

* [[Antihydra]]
* {{TM|1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA|undecided}}, a variant of [[Hydra]] and Antihydra
* {{TM|1RB1LD_1RC1RE_0LA1LB_0LD1LC_1RF0RA_---0RC|undecided}}, similar to Antihydra
* {{TM|1RB0LD_1RC1RF_1LA0RA_0LA0LE_1LD1LA_0RB---|undecided}}, similar to Antihydra
* {{TM|1RB0LB_1LC0RE_1LA1LD_0LC---_0RB0RF_1RE1RB|undecided}}, similar to Antihydra

Probviously halting Cryptids:

* [[Lucy's Moonlight]]
* {{TM|1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC|undecided}}, a family of 16 related TMs
* {{TM|1RB1RE_1LC1LD_---1LA_1LB1LE_0RF0RA_1LD1RF}}
* {{TM|1RB0RE_1LC1LD_0RA0LD_1LB0LA_1RF1RA_---1LB}}
* {{TM|1RB0LC_0LC0RF_1RD1LC_0RA1LE_---0LD_1LF1LA}}
* {{TM|1RB0LC_1LC0RD_1LF1LA_1LB1RE_1RB1LE_---0LE}}
Although {{TM|1RB1LE_0LC0LB_1RD1LC_1RD1RA_1RF0LA_---1RE}} behaves similarly to the probviously halting Cryptids, it is estimated to have a 3/5 chance of becoming a [[translated cycler]] and a 2/5 chance of halting.

There are a few machines considered notable for their chaotic behaviour, but which have not been classified as Cryptids due to seemingly lacking a connection to any known open mathematical problems, such as Collatz-like problems.

Potential Cryptids:

* {{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}
* {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}}
* {{TM|1RB0RB_1LC1RE_1LF0LD_1RA1LD_1RC1RB_---1LC|undecided}}
* {{TM|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD}}

== Top Halters ==
Below is a table of the machines with the 10 highest known runtimes.<ref>Shawn Ligocki's list of 6-state, 2-symbol machines with large runtimes ([https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/6x2.txt Link])</ref> Their sigma scores are expressed using an extension of Knuth's up-arrow notation.<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/06/25/ext-up-notation.html "Extending Up-arrow Notation"]</ref>
{| class="wikitable"
|+Top Known BB(6) Halters
!TM
!approximate sigma score
|-
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE}}
|10 ↑↑ 15.60465
|-
|{{TM|1RB0LF_1RC1RB_1LD0RA_1LB0LE_1RZ0LC_1LA1LF}}
|10 ↑↑ 7.52390
|-
|{{TM|1RB0LF_1RC1RB_1LD0RA_1RF0LE_1RZ0LC_1LA1LF}}
|10 ↑↑ 7.52390
|-
|{{TM|1RB0LF_1RC1RB_1LD0RA_1LF0LE_1RZ0LC_1LA1LF}}
|10 ↑↑ 7.52390
|-
|{{TM|1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA}}
|10 ↑↑ 7.23619
|-
|{{TM|1RB1RA_1LC1LE_1RE0LD_1LC0LF_---0RA_0RA0LB}}
|10 ↑↑ 6.96745
|-
|{{TM|1RB0RF_1LC0RA_---0LD_1LE1LD_1RB1RC_0LD0RE}}
|10 ↑↑ 5.77573
|-
|{{TM|1RB0LA_1LC1LF_0LD0LC_0LE0LB_1RE0RA_1RZ1LD}}
|10 ↑↑ 5.63534
|-
|{{TM|1RB1RE_1LC1LF_1RD0LB_1LE0RC_1RA0LD_1RZ1LC}}
|10 ↑↑ 5.56344
|-
|{{TM|1RB0LE_0RC1RA_0LD1RF_1RE0RB_1LA0LC_0RD1RZ}}
|10 ↑↑ 5.12468
|}
The runtimes are presumed to be about <math>\text{score}^2</math> which is roughly indistinguishable in tetration notation.

== Holdouts ==
@mxdys's informal [[Holdouts lists|holdouts list]] is down to 4408 machines as of 8 Nov 2024.

== References ==
<references />
[[Category:BB Domain]]

Shift overflow counter

2025-06-04T20:41:25Z

Isokate: /* Examples */

'''Shift overflow counter''' is an informal class of Turing machines. A typical Turing machine in this class has the following behavior:

* it represents digits as short fixed-length blocks of symbols
* it spends most of its time implementing basic double counter until one of the sides overflows (expands) which leads to changing the offsets of blocks, making them non-valid representations of digits
* after “Counter Phase” there is a “Reset Phase” where the contents are “reparsed”, creating a new double counter configuration. The new configuration could lead to halting.

Note: some examples (like the Halthing shift-overflow counters below) use a counter on one side and a [[bouncer]] (sometimes called unary counter) on the other.

== Examples ==
* Skelet holdouts: [[Skelet 34]], [[Skelet 33]], [[Skelet 35]], [[Skelet 15]], [[Skelet 26]]
* {{TM|1RB1LD_1RC0RB_1LA0LE_1LC0LA_1RZ1RB}}
* {{TM|1RB0RF_1LC1RB_0RD0LB_---0LE_1RE0RA_1RD1RE}}
* {{TM|1RB1LD_1RC0RB_1LA1LE_1LC0LA_1RZ0RD}}

Halting shift-overflow counters:
* Current longest running [[BB(2,5)]] TM: {{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ}}
* Current fifth longest running [[BB(6)]] TM: {{TM|1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA}}

== Related links ==
* [https://www.sligocki.com/2023/02/02/skelet-34.html Skelet #34 is Infinite]
* [https://www.sligocki.com/2023/02/05/shift-overflow.html Shift Overflow Counters]
* [https://discuss.bbchallenge.org/t/skelet-26-and-15-do-not-halt-coq-proof/183 Skelet #26 and #15 do not halt - Coq proof]
* [https://discuss.bbchallenge.org/t/skelet-34-and-35-coq-proof/165 Skelet #34 and #35 – Coq proof]
* [https://discuss.bbchallenge.org/t/skelet-33-doesnt-halt-coq-proof/180 Skelet #33 doesn’t halt - Coq proof]

[[Category:Stub]]
[[Category:Zoology]]

1RB0LF 1RC1RB 1LD0RA 1LB0LE 1RZ0LC 1LA1LF

2025-06-04T15:49:39Z

Isokate: /* Related TMs */

{{Machine|1RB0LF_1RC1RB_1LD0RA_1LB0LE_1RZ0LC_1LA1LF}}
{{TM|1RB0LF_1RC1RB_1LD0RA_1LB0LE_1RZ0LC_1LA1LF}} is a long running Halting [[BB(6)]] TM first analyzed by Katelyn Doucette on 1 Jun 2025 ([https://discord.com/channels/960643023006490684/1375512968569028648/1378916236104171562 Discord Link]). It is a [[shift overflow counter]] that halts with a final sigma score of roughly <math>10 \uparrow \uparrow 7.52390</math>. It is currently the second longest known running halting [[BB(6)]] TM.

== Analysis by [[User:isokate|Katelyn Doucette]]==
(These rules were automatically generated by https://github.com/Laturas/shift_overflow_subset_decider)

<pre>
START = A(5, 2^2 - 1, 0) at step 57
A(3k, 2^n - 1, 0) -> HALT
A(3k + 1, 2^n - 1, 0) -> A(5, 2^2 - 1, n + 2k + 0)
A(3k + 2, 2^n - 1, 0) -> A(5, 2^2 - 1, n + 2k + 1)
A(a, 2^n - 1, c) -> A(a + 2^n (4(4^c - 1)/3) - 3c, 2^{n+2c} - 1, 0)

---------- RULE EVALUATION ----------
START = A(5, 2^2 - 1, 0)
A(5, 2^2 - 1, 0) -> A(5, 2^2 - 1, 5) -> A(5446, 2^12 - 1, 0) (mod 6377292)
A(5446, 2^12 - 1, 0) -> A(5, 2^2 - 1, 3642) -> A(195563, 2^7286 - 1, 0) (mod 708588)
A(195563, 2^7286 - 1, 0) -> A(5, 2^2 - 1, 137661) -> A(72002, 2^39128 - 1, 0) (mod 78732)
A(72002, 2^39128 - 1, 0) -> A(5, 2^2 - 1, 8397) -> A(7430, 2^8048 - 1, 0) (mod 8748)
A(7430, 2^8048 - 1, 0) -> A(5, 2^2 - 1, 1337) -> A(838, 2^732 - 1, 0) (mod 972)
A(838, 2^732 - 1, 0) -> A(5, 2^2 - 1, 318) -> A(107, 2^98 - 1, 0) (mod 108)
A(107, 2^98 - 1, 0) -> A(5, 2^2 - 1, 25) -> A(6, 2^4 - 1, 0) (mod 12)
-> HALT
</pre>

== Analysis by [[User:sligocki|Shawn Ligocki]]==
https://discord.com/channels/960643023006490684/1375512968569028648/1378925307544997898

<pre>
1RB0LF_1RC1RB_1LD0RA_1LB0LE_---0LC_1LA1LF
0 (5, 2, 5, 2, 0, 1)
1 (((-46 + 2^14)/3), 12, 5, 2, 0, 1)
2 (((-11 + 2^((56 + 2^16)/9) + -1 * 2^15)/3), ((38 + 2^16)/9), 5, 2, 0, 1)
3 (((-14 + 2^((62 + 2^((74 + 2^16)/9))/9) + -1 * 2^((65 + 2^16)/9))/3), ((44 + 2^((74 + 2^16)/9))/9), 5, 2, 0, 1)
4 (((-14 + 2^((62 + 2^((80 + 2^((74 + 2^16)/9))/9))/9) + -1 * 2^((71 + 2^((74 + 2^16)/9))/9))/3), ((44 + 2^((80 + 2^((74 + 2^16)/9))/9))/9), 5, 2, 0, 1)
5 (((-14 + 2^((62 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9) + -1 * 2^((71 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/3), ((44 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9), 5, 2, 0, 1)
6 (((-11 + 2^((56 + 2^((80 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/9) + -1 * 2^((71 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/3), ((38 + 2^((80 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/9), 5, 2, 0, 1)
7 (((-14 + 2^((62 + 2^((74 + 2^((80 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/9))/9) + -1 * 2^((65 + 2^((80 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/9))/3), ((44 + 2^((74 + 2^((80 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/9))/9), 5, 2, 0, 1)
Halted with score: ~10↑↑7.52390 = ((34 + 2^((71 + 2^((74 + 2^((80 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/9))/9))/9)
</pre>

== Equivalent TMs ==
The following TMs have near identical behavior, producing the same values but do so slightly more efficiently:
<pre>
1RB0LF_1RC1RB_1LD0RA_1LF0LE_---0LC_1LA1LF
1RB0LF_1RC1RB_1LD0RA_1RF0LE_---0LC_1LA1LF
</pre>

== Related TMs ==
This TM is part of a broader family of 15 turing machines with similar rules. The family is made up of the following:
<pre>
1RB1RA_1LC0RF_---0LD_0LE0LB_1LF1LE_1RA0LE
1RB0RE_1LC0RF_1LD1LC_1RA0LB_---0RD_1RB1RF
1RB0LF_1RC1RB_1LD0RA_0RF0LE_---0LC_1LA1LF
1RB0LF_1RC1RB_1LD0RA_0RA0LE_---0LC_1LA1LF
1RB0LF_1LC1LB_1RD0LB_1RE1RD_1LA0RC_---0LE
1RB0LF_1RC1RB_1LD0RA_1RA0LE_---0LC_1LA1LF
1RB0LE_1LC0RD_1LA1LC_---0RA_1LC0RF_1RE1RF
1RB0LF_1RC1RB_1LD0RA_1LA0LE_---0LC_1LA1LF
1RB0LD_1RC0RF_1RD1RC_1LE0RC_1LA1LE_---0RA
1RB0LF_1RC1RB_1LD0RA_1RF0LE_---0LC_1LA1LF
1RB0LD_1RC0RF_1LA1LC_1LC0RE_1RD1RE_---0RA
1RB1RA_1LC0RA_1LD1LC_1RE0LB_0LA0RF_---0RD
1RB0LC_0LC0RF_1LE0RD_1RC1RD_1LA1LE_---0RA
1RB0LF_1RC1RB_1LD0RA_1LB0LE_---0LC_1LA1LF
1RB0LF_1RC1RB_1LD0RA_1LF0LE_---0LC_1LA1LF
</pre>

All of these turing machines have been shown to halt. Interestingly, <code>1RB1RA_1LC0RF_---0LD_0LE0LB_1LF1LE_1RA0LE</code> is the only one to halt when the unary counter is equal to 1 mod 3 or 2 mod 3 instead of 0 mod 3.

All of these machines are fundamentally characterized by the rule <code>A(a, 2^n - 1, c) -> A(a + 2^n (4(4^c - 1)/3) - 3c, 2^{n+2c} - 1, 0)</code> and only differ in starting conditions and reset behavior.

{{TM|1RB1LE_1RC1RC_1LD0LF_1LE1LD_1RF0LC_1RZ0RA}} exhibits similar behavior but never halts. See proof at: ([https://discord.com/channels/960643023006490684/1375512968569028648/1378916236104171562 Discord Link]).

BB(6)

2025-06-02T21:11:10Z

Isokate: /* Top Halters */

The 6-state, 2-symbol Busy Beaver problem '''BB(6)''' is unsolved. With the discovery of [[Antihydra]] in 2024, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(6).

The current BB(6) champion {{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}} was discovered by Pavel Kropitz in 2022 proving the lower bound:<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/06/21/bb-6-2-t15.html "BB(6, 2) > 10↑↑15"]</ref><ref>Pascal Michel. [https://bbchallenge.org/~pascal.michel/ha#tm62 Historical survey of Busy Beavers]</ref>

<math display="block">S(6) > \Sigma(6) > 10 \uparrow\uparrow 15</math>

== Techniques ==
In order to simulate the current BB(6) champion requires [[Accelerated simulator|accelerated simulation]] that can handle Collatz Level 2 [[Inductive rule|inductive rules]]. In other words, it requires a simulator that can prove the rules:

<math display="block">\begin{array}{lcl}
C(4k) & \to & {\operatorname{Halt}}\Big(\frac{3^{k+3} - 11}{2}\Big) \\
C(4k+1) & \to & C\Big(\frac{3^{k+3} - 11}{2}\Big) \\
C(4k+2) & \to & C\Big(\frac{3^{k+3} - 11}{2}\Big) \\
C(4k+3) & \to & C\Big(\frac{3^{k+3} + 1}{2}\Big) \\
\end{array}</math>

and also compute the remainder mod 3 of numbers produced by applying these rules 15 times (which requires some fancy math related to [[wikipedia:Euler's_totient_function|Euler's totient function]]).

== Cryptids ==
Several [[Turing machines]] have been found that are [[Cryptids]], considered so because each of them have a [[Collatz-like]] halting problem, a type of problem that is generally difficult to solve. However, probabilistic arguments have allowed all but one of them to be categorized as [[probviously]] halting or probviously non-halting.

Probviously non-halting Cryptids:

* [[Antihydra]]
* {{TM|1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA|undecided}}, a variant of [[Hydra]] and Antihydra
* {{TM|1RB1LD_1RC1RE_0LA1LB_0LD1LC_1RF0RA_---0RC|undecided}}, similar to Antihydra
* {{TM|1RB0LD_1RC1RF_1LA0RA_0LA0LE_1LD1LA_0RB---|undecided}}, similar to Antihydra
* {{TM|1RB0LB_1LC0RE_1LA1LD_0LC---_0RB0RF_1RE1RB|undecided}}, similar to Antihydra

Probviously halting Cryptids:

* [[Lucy's Moonlight]]
* {{TM|1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC|undecided}}, a family of 16 related TMs
* {{TM|1RB1RE_1LC1LD_---1LA_1LB1LE_0RF0RA_1LD1RF}}
* {{TM|1RB0RE_1LC1LD_0RA0LD_1LB0LA_1RF1RA_---1LB}}
* {{TM|1RB0LC_0LC0RF_1RD1LC_0RA1LE_---0LD_1LF1LA}}
* {{TM|1RB0LC_1LC0RD_1LF1LA_1LB1RE_1RB1LE_---0LE}}
Although {{TM|1RB1LE_0LC0LB_1RD1LC_1RD1RA_1RF0LA_---1RE}} behaves similarly to the probviously halting Cryptids, it is estimated to have a 3/5 chance of becoming a [[translated cycler]] and a 2/5 chance of halting.

There are a few machines considered notable for their chaotic behaviour, but which have not been classified as Cryptids due to seemingly lacking a connection to any known open mathematical problems, such as Collatz-like problems.

Potential Cryptids:

* {{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}
* {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}}
* {{TM|1RB0RB_1LC1RE_1LF0LD_1RA1LD_1RC1RB_---1LC|undecided}}
* {{TM|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD}}

== Top Halters ==
Below is a table of the machines with the 10 highest known runtimes.<ref>Shawn Ligocki's list of 6-state, 2-symbol machines with large runtimes ([https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/6x2.txt Link])</ref> Their sigma scores are expressed using an extension of Knuth's up-arrow notation.<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/06/25/ext-up-notation.html "Extending Up-arrow Notation"]</ref>
{| class="wikitable"
|+Top Known BB(6) Halters
!TM
!approximate sigma score
|-
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE}}
|10 ↑↑ 15.60465
|-
|{{TM|1RB0LF_1RC1RB_1LD0RA_1LB0LE_1RZ0LC_1LA1LF}}
|10 ↑↑ 7.52390
|-
|{{TM|1RB0LF_1RC1RB_1LD0RA_1RF0LE_1RZ0LC_1LA1LF}}
|10 ↑↑ 7.52390
|-
|{{TM|1RB0LF_1RC1RB_1LD0RA_1LF0LE_1RZ0LC_1LA1LF}}
|10 ↑↑ 7.52390
|-
|{{TM|1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA}}
|10 ↑↑ 7.23619
|-
|{{TM|1RB0LA_1LC1LF_0LD0LC_0LE0LB_1RE0RA_1RZ1LD}}
|10 ↑↑ 5.63534
|-
|{{TM|1RB1RE_1LC1LF_1RD0LB_1LE0RC_1RA0LD_1RZ1LC}}
|10 ↑↑ 5.56344
|-
|{{TM|1RB0LE_0RC1RA_0LD1RF_1RE0RB_1LA0LC_0RD1RZ}}
|10 ↑↑ 5.12468
|-
|{{TM|1RB0RF_1LC1LB_0RE0LD_0LC0LB_0RA1RE_0RD1RZ}}
|10 ↑↑ 5.03230
|-
|{{TM|1RB1LA_1LC0RF_1LD1LC_1LE0RE_0RB0LC_1RZ1RA}}
|10 ↑↑ 4.91072
|}
The runtimes are presumed to be about <math>\text{score}^2</math> which is roughly indistinguishable in tetration notation.

== Holdouts ==
@mxdys's informal [[Holdouts lists|holdouts list]] is down to 4408 machines as of 8 Nov 2024.

== References ==
<references />
[[Category:BB Domain]]

1RB0LF 1RC1RB 1LD0RA 1LB0LE 1RZ0LC 1LA1LF

2025-06-02T20:48:02Z

Isokate: Created page with "{{TM|1RB0LF_1RC1RB_1LD0RA_1LB0LE_1RZ0LC_1LA1LF}} is a long running Halting BB(6) TM first analyzed by Katelyn Doucette on 1 Jun 2025 ([https://discord.com/channels/960643023006490684/1375512968569028648/1378916236104171562 Discord Link]). It is a shift overflow counter that halts with a final sigma score of roughly <math>10 \uparrow \uparrow 7.52390</math>. It is currently the second longest known running halting BB(6) TM. == Analysis by User:isokate|Katel..."

{{TM|1RB0LF_1RC1RB_1LD0RA_1LB0LE_1RZ0LC_1LA1LF}} is a long running Halting [[BB(6)]] TM first analyzed by Katelyn Doucette on 1 Jun 2025 ([https://discord.com/channels/960643023006490684/1375512968569028648/1378916236104171562 Discord Link]). It is a [[shift overflow counter]] that halts with a final sigma score of roughly <math>10 \uparrow \uparrow 7.52390</math>. It is currently the second longest known running halting [[BB(6)]] TM.

== Analysis by [[User:isokate|Katelyn Doucette]]==
(These rules were automatically generated by https://github.com/Laturas/shift_overflow_subset_decider)

<pre>
START = A(5, 2^2 - 1, 0) at step 57
A(3k, 2^n - 1, 0) -> HALT
A(3k + 1, 2^n - 1, 0) -> A(5, 2^2 - 1, n + 2k + 0)
A(3k + 2, 2^n - 1, 0) -> A(5, 2^2 - 1, n + 2k + 1)
A(a, 2^n - 1, c) -> A(a + 2^n (4(4^c - 1)/3) - 3c, 2^{n+2c} - 1, 0)

---------- RULE EVALUATION ----------
START = A(5, 2^2 - 1, 0)
A(5, 2^2 - 1, 0) -> A(5, 2^2 - 1, 5) -> A(5446, 2^12 - 1, 0) (mod 6377292)
A(5446, 2^12 - 1, 0) -> A(5, 2^2 - 1, 3642) -> A(195563, 2^7286 - 1, 0) (mod 708588)
A(195563, 2^7286 - 1, 0) -> A(5, 2^2 - 1, 137661) -> A(72002, 2^39128 - 1, 0) (mod 78732)
A(72002, 2^39128 - 1, 0) -> A(5, 2^2 - 1, 8397) -> A(7430, 2^8048 - 1, 0) (mod 8748)
A(7430, 2^8048 - 1, 0) -> A(5, 2^2 - 1, 1337) -> A(838, 2^732 - 1, 0) (mod 972)
A(838, 2^732 - 1, 0) -> A(5, 2^2 - 1, 318) -> A(107, 2^98 - 1, 0) (mod 108)
A(107, 2^98 - 1, 0) -> A(5, 2^2 - 1, 25) -> A(6, 2^4 - 1, 0) (mod 12)
-> HALT
</pre>

== Analysis by [[User:sligocki|Shawn Ligocki]]==
https://discord.com/channels/960643023006490684/1375512968569028648/1378925307544997898

<pre>
1RB0LF_1RC1RB_1LD0RA_1LB0LE_---0LC_1LA1LF
0 (5, 2, 5, 2, 0, 1)
1 (((-46 + 2^14)/3), 12, 5, 2, 0, 1)
2 (((-11 + 2^((56 + 2^16)/9) + -1 * 2^15)/3), ((38 + 2^16)/9), 5, 2, 0, 1)
3 (((-14 + 2^((62 + 2^((74 + 2^16)/9))/9) + -1 * 2^((65 + 2^16)/9))/3), ((44 + 2^((74 + 2^16)/9))/9), 5, 2, 0, 1)
4 (((-14 + 2^((62 + 2^((80 + 2^((74 + 2^16)/9))/9))/9) + -1 * 2^((71 + 2^((74 + 2^16)/9))/9))/3), ((44 + 2^((80 + 2^((74 + 2^16)/9))/9))/9), 5, 2, 0, 1)
5 (((-14 + 2^((62 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9) + -1 * 2^((71 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/3), ((44 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9), 5, 2, 0, 1)
6 (((-11 + 2^((56 + 2^((80 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/9) + -1 * 2^((71 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/3), ((38 + 2^((80 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/9), 5, 2, 0, 1)
7 (((-14 + 2^((62 + 2^((74 + 2^((80 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/9))/9) + -1 * 2^((65 + 2^((80 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/9))/3), ((44 + 2^((74 + 2^((80 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/9))/9), 5, 2, 0, 1)
Halted with score: ~10↑↑7.52390 = ((34 + 2^((71 + 2^((74 + 2^((80 + 2^((80 + 2^((80 + 2^((74 + 2^16)/9))/9))/9))/9))/9))/9))/9)
</pre>

== Equivalent TMs ==
The following TMs have near identical behavior, producing the same values but do so slightly more efficiently:
<pre>
1RB0LF_1RC1RB_1LD0RA_1LF0LE_---0LC_1LA1LF
1RB0LF_1RC1RB_1LD0RA_1RF0LE_---0LC_1LA1LF
</pre>

== Related TMs ==
This TM is part of a broader family of 15 turing machines with similar rules. The family is made up of the following:
<pre>
1RB1RA_1LC0RF_---0LD_0LE0LB_1LF1LE_1RA0LE
1RB0RE_1LC0RF_1LD1LC_1RA0LB_---0RD_1RB1RF
1RB0LF_1RC1RB_1LD0RA_0RF0LE_---0LC_1LA1LF
1RB0LF_1RC1RB_1LD0RA_0RA0LE_---0LC_1LA1LF
1RB0LF_1LC1LB_1RD0LB_1RE1RD_1LA0RC_---0LE
1RB0LF_1RC1RB_1LD0RA_1RA0LE_---0LC_1LA1LF
1RB0LE_1LC0RD_1LA1LC_---0RA_1LC0RF_1RE1RF
1RB0LF_1RC1RB_1LD0RA_1LA0LE_---0LC_1LA1LF
1RB0LD_1RC0RF_1RD1RC_1LE0RC_1LA1LE_---0RA
1RB0LF_1RC1RB_1LD0RA_1RF0LE_---0LC_1LA1LF
1RB0LD_1RC0RF_1LA1LC_1LC0RE_1RD1RE_---0RA
1RB1RA_1LC0RA_1LD1LC_1RE0LB_0LA0RF_---0RD
1RB0LC_0LC0RF_1LE0RD_1RC1RD_1LA1LE_---0RA
1RB0LF_1RC1RB_1LD0RA_1LB0LE_---0LC_1LA1LF
1RB0LF_1RC1RB_1LD0RA_1LF0LE_---0LC_1LA1LF
</pre>

All of these turing machines have been shown to halt. Interestingly, <code>1RB1RA_1LC0RF_---0LD_0LE0LB_1LF1LE_1RA0LE</code> is the only one to halt when the unary counter is equal to 1 mod 3 or 2 mod 3 instead of 0 mod 3.

All of these machines are fundamentally characterized by the rule <code>A(a, 2^n - 1, c) -> A(a + 2^n (4(4^c - 1)/3) - 3c, 2^{n+2c} - 1, 0)</code> and only differ in starting conditions and reset behavior.

{{TM|1RB1LE_1RC1RC_1LD0LF_1LE1LD_1RF0LC_1RZ0RA}} is also believed to exhibit similar behavior but has not yet been thoroughly analyzed.