BusyBeaverWiki - User contributions [en]

Fractran

2026-06-03T23:55:35Z

Hsjoihs: /* BBf(15) Family */ Using the variable name "n" here is misleading (since another variable named "n" is set equal to 2 in the paragraph immediately preceding it)

'''Fractran''' (originally styled FRACTRAN) is an esoteric [[Turing complete]] model of computation invented by John Conway in 1987.<ref>Conway, John H. (1987). "FRACTRAN: A Simple Universal Programming Language for Arithmetic". ''Open Problems in Communication and Computation''. Springer-Verlag New York, Inc. pp. 4–26. <nowiki>http://doi.org/10.1007/978-1-4612-4808-8_2</nowiki></ref> In this model a program is simply a finite list of fractions (rational numbers), the program state is an integer. For more details see https://en.wikipedia.org/wiki/FRACTRAN.

Discord user Coda came up with a way to transform any Fractran program into a Turing Machine, see [https://discord.com/channels/960643023006490684/1438019511155691521/1441844795613122560 source].

'''BB_fractran'''(n) or '''BBf'''(n) is the Busy Beaver function for Fractran programs. Holdouts lists by Daniel Yuan: [https://github.com/int-y1/BBFractran/blob/main/holdout/README.md Holdouts lists]

== Definition ==
A Fractran program is a list of rational numbers <math>[q_0, q_1, \dots, q_{k-1}]</math> called rules and a Fractran state is an integer <math>s \in \mathbb{Z}</math>. The numerator and denominator of any rational number fraction do not share any prime factors (they are in reduced form). We say that a rule <math>q_i</math> applies to state <math>s</math> if <math>s \cdot q_i \in \mathbb{Z}</math>. If no rule applies, we say that the computation has halted otherwise we apply the first applicable rule at each step. In that case we say <math>s \to t</math> and <math>t = s \cdot q_i</math> and <math>i = \min \{ i : s \cdot q_i \in \mathbb{Z} \}</math>. As with [[Turing machines]], we will write <math>s \xrightarrow{N} t</math> if <math>s \to s_1 \to \cdots \to s_{N-1} \to t</math> (s goes to t after N steps) and <math>s \to^* t</math> or <math>s \to^+ t</math> if <math>s \xrightarrow{N} t</math> for some N≥0 or N≥1 (respectively). We say that a program has runtime N (or halts in N steps) starting in state s if <math>s \xrightarrow{N} t</math> and computation halts on t.

Let <math>\Omega(n)</math> be the total number of prime factors of a positive integer n. In other words, <math>\Omega(2^{a_0} 3^{a_1} \cdots p_n^{a_n}) = \sum_{k=0}^n a_n</math>. Then given a rule <math>\frac{a}{b}</math> we say that <math>\text{size} \left( \frac{a}{b} \right) = \Omega(a) + \Omega(b)</math>. And the size of a Fractran program <math>[q_0, q_1, \dots, q_{k-1}]</math> is <math>k + \sum_{i=0}^{k-1} \text{size}(q_i)</math>.

BB_fractran(n) or BBf(n) is the maximum runtime starting in state 2 for all halting Fractran programs of size n. It is a non-computable function akin to the [[Busy Beaver Functions]] since Fractran is Turing Complete.

== Vector Representation ==
Fractran programs are not easy to interpret, in fact it may be completely unclear at first that they can perform any computation at all. One of the key insights is to represent all numbers (states and rules) in their prime factorization form. For example, we can use a vector <math>[ a_0, a_1, \dots, a_{n-1} ] \in \mathbb{Z}^n</math> to represent the number <math>2^{a_0} 3^{a_1} \cdots p_{n-1}^{a_{n-1}}</math>.

Let the vector representation (for a sufficiently large n) for a state <math>a = 2^{a_0} 3^{a_1} \cdots p_{n-1}^{a_{n-1}}</math> be <math>v(a) = [ a_0, a_1, \dots, a_{n-1} ] \in \mathbb{N}^n</math> and the vector representation for a rule <math>\frac{a}{b}</math> be <math>v \left( \frac{a}{b} \right) = v(a) - v(b) \in \mathbb{Z}^n</math> (Note that this is just an extension of the original definition extended to allow negative <math>a_i</math>).

Now, rule q applies to state s iff <math>v(s) + v(q) \in \mathbb{N}^n</math> (all components of the vector are ≥0) and if <math>s \to t</math> then <math>v(t) = v(s) + v(q)</math>. So the Fractran multiplication model is completely equivalent to the vector adding model. For presentation, we will represent a Fractran program with a matrix where each row is the vector representation for a rule.

For example, the BBf(15) champion (<code>[1/45, 4/5, 3/2, 25/3]</code>) in vector representation would be:

<math display="block">\begin{bmatrix}
0 & -2 & -1 \\
2 & 0 & -1 \\
-1 & 1 & 0 \\
0 & -1 & 2
\end{bmatrix}</math>

In this representation, it becomes much easier to reason about Fractran programs and describe general rules. It is also very easy to calculate the size of a rule or program in vector representation. It is the sum of absolute values of all elements in the matrix + number of rules (number of rows).

=== Relationship to VAS / Petri Nets ===
Using vector representation, Fractran programs are a deterministic version of [[wikipedia:Vector_addition_system|Vector Addition Systems (VAS)]] (and, equivalently, [[wikipedia:Petri_net|Petri Nets]]). VAS are identical to Fractran programs in vector representation except that the rules are unordered and non-deterministic, they are used to model distributed systems where precise order of rule execution cannot be predicted. Interestingly, many problems about VAS are actually decidable, but their runtimes are extremely slow. Notably, the reachability problem (given states A and B are there a sequence of rules so that <math>A \to^* B</math>) is "Ackermann-complete" meaning that the optimal algorithm has worst-case runtime akin to the famously fast-growing Ackermann function.<ref>Czerwiński, Wojciech; Orlikowski, Łukasz (2021). ''Reachability in Vector Addition Systems is Ackermann-complete''. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). https://arxiv.org/abs/2104.13866.</ref>

== Visualizing Fractran Programs' Space-Time Diagrams ==
Katelyn Doucette's Fractran space-time diagram visualizer produces the following space-time diagrams for some notable Fractran Programs, under the following principle: Each color represents a prime factor. Left -> right colors indicating the index of that register, and how wide the color is representing how big the value is at that step. Source code: https://github.com/Laturas/FractranVisualizer
{| class="wikitable"
|+
|[[File:Fractran_22_Cryptid.webp|alt=The space-time diagram of Fenrir|460x460px]]
The space-time diagram of Fenrir
|[[File:Hydra.webp|alt=The space-time diagram of Hydra.|460x460px]]
The space-time diagram of Hydra.
|[[File:Bbf21 champ full.png|alt=The space-time diagram of the BBf(21) champion.|400x400px]]

The space-time diagram of the BBf(21) champion. The width & height of the diagram can be set in the visualizer.
|[[File:Space_Needle.webp|alt=The space-time diagram of Space Needle.|460x460px]]
The space-time diagram of Space Needle.
|}

== Deciders ==
[[File:Fractran deciders.png|alt=Fractran deciders|thumb|All Fractran deciders summarized and their relations, shared by Daniel Yuan on [https://discord.com/channels/960643023006490684/1438019511155691521/1439001835904958655 14 Nov 2025]]]Many specialized deciders have been invented to prove Fractran programs non-halting. See image at right. There are three extra deciders: [https://discord.com/channels/960643023006490684/1438019511155691521/1449775657554022531 Spanning Vectors Masked,] which should be very effective, but implementing it is in-progress, a version of Spanning Vectors Masked - [https://discord.com/channels/960643023006490684/1438019511155691521/1453217977385091092 Masked Linear Invariant] - which is very powerful, and some holdouts were removed by [[User:Sligocki|Shawn Ligocki]] with [https://lsv.ens-paris-saclay.fr/Software/fast/ FAST] (Fast Acceleration of Symbolic Transition systems), a pre-existing general tool.

-d released a new decider on 25 Jan 2026: [https://discord.com/channels/960643023006490684/1438019511155691521/1464873923647639703 Beeping Permutation].

== Champions ==
The table of champions is split into two pieces: the first for small champions (up to BBf(14)) which all share the same relatively simple behavior (sequential programs) is collapsed by default; the second for champions BBf(15) and beyond which have more complex and varied behavior.
All small champions as well as the first few larger ones were discovered and proven maximal by Jason Yuen (@-d) in their initial enumeration on [https://discord.com/channels/960643023006490684/1362008236118511758/1434033599094587595 1 Nov 2025].

BBf(21) and below are solved. BBf(22) is the smallest domain to contain a Cryptid, all other machines are solved there. Enumeration of BBf(23) will take roughly 10 days ([https://github.com/int-y1/BBFractran/blob/main/enumerate/fractran20260416.cpp Enum script]).

<div class="toccolours mw-collapsible mw-collapsed">'''Small Champions'''<div class="mw-collapsible-content">
{| class="wikitable"
|+
!n
!BBf(n)
!Example Champion
!Vector Representation
|-
| 2 || 1 || <code>[1/2]</code>
|<math>\begin{bmatrix}
-1
\end{bmatrix}</math>
|-
| 3 || 1 || <code>[3/2]</code>
|<math>\begin{bmatrix}
-1 & 1
\end{bmatrix}</math>
|-
| 4 || 1 || <code>[9/2]</code>
|<math>\begin{bmatrix}
-1 & 2
\end{bmatrix}</math>
|-
| 5 || 2 || <code>[3/2, 1/3]</code>
|<math>\begin{bmatrix}
-1 & 1 \\
0 & -1
\end{bmatrix}</math>
|-
| 6 || 3 || <code>[9/2, 1/3]</code>
|<math>\begin{bmatrix}
-1 & 2 \\
0 & -1
\end{bmatrix}</math>
|-
| 7 || 4 || <code>[27/2, 1/3]</code>
|<math>\begin{bmatrix}
-1 & 3 \\
0 & -1
\end{bmatrix}</math>
|-
| 8 || 5 || <code>[81/2, 1/3]</code>
|<math>\begin{bmatrix}
-1 & 4 \\
0 & -1
\end{bmatrix}</math>
|-
| 9 || 6 || <code>[243/2, 1/3]</code>
|<math>\begin{bmatrix}
-1 & 5 \\
0 & -1
\end{bmatrix}</math>
|-
| 10 || 7 || <code>[729/2, 1/3]</code>
|<math>\begin{bmatrix}
-1 & 6 \\
0 & -1
\end{bmatrix}</math>
|-
| 11 || 10 || <code>[27/2, 25/3, 1/5]</code>
|<math>\begin{bmatrix}
-1 & 3 & 0 \\
0 & -1 & 2 \\
0 & 0 & -1
\end{bmatrix}</math>
|-
| 12 || 13 || <code>[81/2, 25/3, 1/5]</code>
|<math>\begin{bmatrix}
-1 & 4 & 0 \\
0 & -1 & 2 \\
0 & 0 & -1
\end{bmatrix}</math>
|-
| 13 || 17 || <code>[81/2, 125/3, 1/5]</code>
|<math>\begin{bmatrix}
-1 & 4 & 0 \\
0 & -1 & 3 \\
0 & 0 & -1
\end{bmatrix}</math>
|-
| 14 || 21 || <code>[243/2, 125/3, 1/5]</code>
|<math>\begin{bmatrix}
-1 & 5 & 0 \\
0 & -1 & 3 \\
0 & 0 & -1
\end{bmatrix}</math>
|}
</div></div>

{| class="wikitable"
|+
!n
!BBf(n)
!Example Champion
!Vector Representation
!Champion Found
!Holdouts Proven
|-
| 15 || 28 || <code>[1/45, 4/5, 3/2, 25/3]</code>
|<math>\begin{bmatrix}
0 & -2 & -1 \\
2 & 0 & -1 \\
-1 & 1 & 0 \\
0 & -1 & 2
\end{bmatrix}</math>
|Jason Yuen (@-d) [https://discord.com/channels/960643023006490684/1362008236118511758/1434033599094587595 1 Nov 2025]
|Jason Yuen (@-d) [https://discord.com/channels/960643023006490684/1362008236118511758/1434033599094587595 1 Nov 2025]
|-
| 16 || 53 || <code>[1/45, 4/5, 3/2, 125/3]</code>
|<math>\begin{bmatrix}
0 & -2 & -1 \\
2 & 0 & -1 \\
-1 & 1 & 0 \\
0 & -1 & 3
\end{bmatrix}</math>
|Jason Yuen (@-d) [https://discord.com/channels/960643023006490684/1362008236118511758/1434033599094587595 1 Nov 2025]
|Jason Yuen (@-d) [https://discord.com/channels/960643023006490684/1362008236118511758/1434033599094587595 1 Nov 2025]
|-
| 17 || 107 || <code>[5/6, 49/2, 3/5, 40/7]</code>
|<math>\begin{bmatrix}
-1 & -1 & 1 & 0 \\
-1 & 0 & 0 & 2 \\
0 & 1 & -1 & 0 \\
3 & 0 & 1 & -1
\end{bmatrix}</math>
|Jason Yuen (@-d) [https://discord.com/channels/960643023006490684/1362008236118511758/1434313398799175710 1 Nov 2025]
|Daniel Yuan (@dyuan01) [https://discord.com/channels/960643023006490684/1362008236118511758/1434771877376557086 3 Nov 2025]
|-
| 18 || 211 || <code>[5/6, 49/2, 3/5, 80/7]</code>
|<math>\begin{bmatrix}
-1 & -1 & 1 & 0 \\
-1 & 0 & 0 & 2 \\
0 & 1 & -1 & 0 \\
4 & 0 & 1 & -1
\end{bmatrix}</math>
|Jason Yuen (@-d) [https://discord.com/channels/960643023006490684/1362008236118511758/1435313806493614131 4 Nov 2025]
|Jason Yuen (@-d) [https://discord.com/channels/960643023006490684/1362008236118511758/1436661215911870584 8 Nov 2025]
|-
| 19 || 370 || <code>[5/6, 49/2, 3/5, 160/7]</code>
|<math>\begin{bmatrix}
-1 & -1 & 1 & 0 \\
-1 & 0 & 0 & 2 \\
0 & 1 & -1 & 0 \\
5 & 0 & 1 & -1
\end{bmatrix}</math>
|@creeperman7002 [https://discord.com/channels/960643023006490684/1362008236118511758/1435763150489387090 5 Nov 2025]
|Decider: Daniel Yuan (@dyuan01) [https://discord.com/channels/960643023006490684/1438019511155691521/1438558242388312165 13 Nov 2025]
3 Holdouts: Racheline & Shawn Ligocki
|-
|20
|746
|<code>[7/15, 22/3, 6/77, 5/2, 9/5]</code>
|<math>\begin{bmatrix}
0 & -1 & -1 & 1 & 0 \\
1 & -1 & 0 & 0 & 1 \\
1 & 1 & 0 & -1 & -1 \\
-1 & 0 & 1 & 0 & 0 \\
0 & 2 & -1 & 0 & 0
\end{bmatrix}</math>
|Jason Yuen (@-d) [https://discord.com/channels/960643023006490684/1438019511155691521/1438480761169776733 13 Nov 2025]
|Decider: Jason Yuen (@-d)
([https://github.com/int-y1/BBFractran/tree/main/holdout Enum+initial])
Daniel Yuan (@dyuan01) [https://discord.com/channels/960643023006490684/1438019511155691521/1438559507579011194 13] and [https://discord.com/channels/960643023006490684/1438019511155691521/1438996636389998773 14 Nov 2025]

Shawn Ligocki (@sligocki) [https://discord.com/channels/960643023006490684/1438019511155691521/1447069110541484146 7] and [https://discord.com/channels/960643023006490684/1438019511155691521/1453213088630444168 24 Dec 2025]
6 Holdouts: Jason Yuen (@-d) [https://discord.com/channels/960643023006490684/1438019511155691521/1452913055053778945 23 Dec 2025]
|-
|21
|31,957,632
|<code>[7/15, 4/3, 27/14, 5/2, 9/5]</code>
|<math>\begin{bmatrix}
0 & -1 & -1 & 1 \\
2 & -1 & 0 & 0 \\
-1 & 3 & 0 & -1 \\
-1 & 0 & 1 & 0 \\
0 & 2 & -1 & 0
\end{bmatrix}</math>
|Jason Yuen (@-d) [https://discord.com/channels/960643023006490684/1438019511155691521/1439759182587891894 16 Nov 2025]
|140 holdouts remain. [https://discord.com/channels/960643023006490684/1438019511155691521/1464873923647639703 25 Jan 2026]
Claude Opus 4.6 proof of nonhalting of all 140: [https://discord.com/channels/960643023006490684/1438019511155691521/1485168251997786173 28 March 2026]
|-
|22
|<math>> 1.146 \times 10^{62}</math>
|<code>[1/12, 9/10, 14/3, 11/2, 5/7, 3/11]</code>
|<math>\begin{bmatrix}
-2 & -1 & 0 & 0 & 0 \\
-1 & 2 & -1 & 0 & 0 \\
1 & -1 & 0 & 1 & 0 \\
-1 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & -1 & 0 \\
0 & 1 & 0 & 0 & -1
\end{bmatrix}</math>
|Shawn Ligocki (@sligocki) [https://discord.com/channels/960643023006490684/1438019511155691521/1448912286713384961 11 Dec 2025] and Jason Yuen (@-d)[https://discord.com/channels/960643023006490684/1438019511155691521/1448953682237460480 <nowiki>[1]</nowiki>]
|2003 holdouts remain. [https://discord.com/channels/960643023006490684/1438019511155691521/1464873923647639703 25 Jan 2026]
Claude Opus 4.6 gave a proof of all machines but the Fenrir-family, see [https://discord.com/channels/960643023006490684/1438019511155691521/1493027835559022824 Discord].

Known [[Cryptid|Cryptids]]:

# Fenrir
|-
|23
|<math>> 4.393 \times 10^{124}</math>
|<code>[10/3, 9/14, 5/4, 121/2, 7/5, 3/11]</code>
|<math>\begin{bmatrix}
1 & -1 & 1 & 0 & 0 \\
-1 & 2 & 0 & -1 & 0 \\
-2 & 0 & 1 & 0 & 0 \\
-1 & 0 & 0 & 0 & 2 \\
0 & 0 & -1 & 1 & 0 \\
0 & 1 & 0 & 0 & -1
\end{bmatrix}</math>
|Shawn Ligocki (@sligocki) [https://discord.com/channels/960643023006490684/1438019511155691521/1510781736374763702 1 Jun 2026]
|Known [[Cryptid|Cryptids]]:

# Frankenstein's Monster
# Antihydra-like Cryptid
|}

=== Behavior of Champions ===

==== Sequential programs ====
All champions up to BBf(14) have very simple behavior. They are all of the form: <math>\left[ \frac{3^{a_1}}{2}, \frac{5^{a_2}}{3}, \dots, \frac{p_n^{a_k}}{p_{k-1}}, \frac{1}{p_k} \right]</math> or in vector representation (limited to k=4):

<math display="block">\begin{bmatrix}
-1 & a_1 & 0 & 0 & 0 \\
0 & -1 & a_2 & 0 & 0 \\
0 & 0 & -1 & a_3 & 0 \\
0 & 0 & 0 & -1 & a_4 \\
0 & 0 & 0 & 0 & -1
\end{bmatrix}</math>

These champions repeatedly apply the rules in sequence, never going back to a previous rule. They apply the first rule until they've exhausted all 2s, then the second rule until they've exhausted all 3s, etc. They have a runtime of <math>1 + a_1 + a_1 a_2 + a_1 a_2 a_3 + \cdots = \sum_{i=0}^k \prod_{j=1}^i a_j</math> and size <math>2k+2 + \sum_{i=1}^k a_i</math>. This grows linearly for k=1 (BBf(5) to BBf(10)) and quadratically for k=2 (BBf(11) to BBf(14)). Letting k grow with the size, the maximum runtime grows exponentially in the program size.

==== BBf(15) Family ====
The BBf(15) and BBf(16) champions are members of a family of programs (parameterized by <math>n \ge 1</math>):

<math display="block">\begin{bmatrix}
0 & -2 & -1 \\
2 & 0 & -1 \\
-1 & 1 & 0 \\
0 & -1 & n
\end{bmatrix}</math>

Let a = 2, b = 3, and c = 5.

The BBf(15) champion (n = 2) implements this iteration:

<math display="block">\begin{array}{lcl}
b^0 & \xrightarrow{0} & \text{halt} \\
b^1 & \xrightarrow{7} & b^4 \\
b^2 & \xrightarrow{7} & b^5 \\
b^3 & \xrightarrow{5} & b^2 \\
b^4 & \xrightarrow{5} & b^3 \\
b^{k+5} & \xrightarrow{3} & b^k \\
\end{array}</math>

which follows a permutation-like trajectory: <math>a \xrightarrow{1} b^1 \to b^4 \to b^3 \to b^2 \to b^5 \to b^0 \to \text{halt}</math>

The BBf(16) champion (n = 3) implements this iteration:

<math display="block">\begin{array}{lcl}
b^0 & \xrightarrow{0} & \text{halt} \\
b^1 & \xrightarrow{10} & b^6 \\
b^2 & \xrightarrow{10} & b^7 \\
b^3 & \xrightarrow{8} & b^4 \\
b^4 & \xrightarrow{8} & b^5 \\
b^5 & \xrightarrow{6} & b^2 \\
b^6 & \xrightarrow{6} & b^3 \\
b^{n+7} & \xrightarrow{4} & b^n \\
\end{array}</math>

which follows a permutation-like trajectory: <math>a \xrightarrow{1} b^1 \to b^6 \to b^3 \to b^4 \to b^5 \to b^2 \to b^7 \to b^0 \to \text{halt}</math>

==== BBf(17) Family ====
The BBf(17) to BBf(19) champions are members of a family of programs (parameterized by <math>m,n \ge 0</math>)

<math display="block">\begin{bmatrix}
-1 & -1 & 1 & 0 \\
-1 & 0 & 0 & n \\
0 & 1 & -1 & 0 \\
m & 0 & 1 & -1
\end{bmatrix}</math>

which have size <math>m+n+12</math>

This family obeys the following rules:

# <math>[1, 0, 0, 0] \xrightarrow{1} [0, 0, 0, n]</math>
# if d≥1 and b≤m:<math display="block">[0, b, 0, d] \xrightarrow{m+b+2} [0, b+1, 0, d - 1 + n(m-b)]</math>
# if d≥1 and b≥m:<math display="block">[0, b, 0, d] \xrightarrow{2m+2} [0, b+1, 0, d - 1]</math>
#if d=0: [0,b,0,d] has halted

and furthermore these rules are applied in order since b is always increasing (and d is eventually decreasing). Combining these together we get runtime:<math display="block">1 + n(m+1)(m(m+1)+2) - \frac{m(m+1)}{2}</math>

The optimal choices for n,m for various program sizes are:
{| class="wikitable"
|+
!Size
!n
!m
!Runtime
|-
|16
|1
|3
|51
|-
|'''''17'''''
|'''''2'''''
|'''''3'''''
|'''''107'''''
|-
|'''''18'''''
|'''''2'''''
|'''''4'''''
|'''''211'''''
|-
|'''''19'''''
|'''''2'''''
|'''''5'''''
|'''''370'''''
|-
|20
|2
|6
|596
|-
|21
|3
|6
|904
|}

 
==== BBf(20) ====
[[File:Screenshot 2026-04-01 104704.png|alt=Full space-time diagram of the BBf(20) champion.|left|507x507px]]
The BBf(20) champion (running 746 steps):

<math display="block">\begin{bmatrix}
0 & -1 & -1 & 1 & 0 \\
1 & -1 & 0 & 0 & 1 \\
1 & 1 & 0 & -1 & -1 \\
-1 & 0 & 1 & 0 & 0 \\
0 & 2 & -1 & 0 & 0
\end{bmatrix}</math>

This program implements a [[Collatz-like]] iteration. Let <math>C(n) = [0, 0, n, 2, 0]</math>, then:

<math display="block">\begin{array}{lcl}
[1,0,0,0,0] & \xrightarrow{49} & C(2) \\
C(3k) & \xrightarrow{3k} & \text{halt} \\
C(3k+1) & \xrightarrow{11k+22} & C(4k+3) \\
C(3k+2) & \xrightarrow{11k+22} & C(4k+4) \\
\end{array}</math>

which follows the reasonably "lucky" trajectory:

<math display="block">C(2) \to C(4) \to C(7) \to C(11) \to C(16) \to C(23) \to C(32) \to C(44) \to C(60) \to \text{halt}</math>

==== BBf(21) ====
[[File:Bbf21 champ full.png|alt=The full space-time diagram of the BBf(21) champion until halting.|thumb|The full space-time diagram of the BBf(21) champion until halting.]]

The BBf(21) champion (running >31M steps):
<math display="block">\begin{bmatrix}
0 & -1 & -1 & 1 \\
2 & -1 & 0 & 0 \\
-1 & 3 & 0 & -1 \\
-1 & 0 & 1 & 0 \\
0 & 2 & -1 & 0
\end{bmatrix}</math>

This program implements a Collatz-like iteration. Let <math>D(n) = [0, 0, n, 0]</math>, then:[https://discord.com/channels/960643023006490684/1438019511155691521/1439779341365022852]
<math display="block">\begin{array}{lcl}
[1,0,0,0,0] & \xrightarrow{1} & D(1) \\
D(3k) & \xrightarrow{k} & \text{halt} \\
D(3k+1) & \xrightarrow{21k+7} & C(10k+4) \\
D(3k+2) & \xrightarrow{21k+14} & C(10k+7) \\
\end{array}</math>

which follows the reasonably "lucky" trajectory:
<math display="block">\begin{array}{ll}
D(1) & \to D(4) \to D(14) \to D(47) \to D(157) \to D(524) \to D(1747) \to D(5824) \to D(19414) \\
& \to D(64714) \to D(215714) \to D(719047) \to D(2396824) \to D(7989414) \to \text{halt} \\
\end{array}</math>

==== BBf(22) ====
The BBf(22) champion (running <math>> 10^{62}</math> steps):
<math display="block">\begin{bmatrix}
-2 & -1 & 0 & 0 & 0 \\
-1 & 2 & -1 & 0 & 0 \\
1 & -1 & 0 & 1 & 0 \\
-1 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & -1 & 0 \\
0 & 1 & 0 & 0 & -1
\end{bmatrix}</math>

This program implements a [[Collatz-like]] unbiased pseudo-random walk. Let <math>S(x,y) = [0, 0, x, 0, y]</math>, then:[https://discord.com/channels/960643023006490684/1438019511155691521/1449118888142049421]
<math display="block">\begin{array}{lcl}
[1,0,0,0,0] & \xrightarrow{1} & S(0,1) \\
S(x, 0) & = & \text{halt} \\
S(3k, y+1) & \xrightarrow{14k+4} & S(5k+1, y+1) \\
S(3k+1, y+1) & \xrightarrow{14k+10} & S(5k+3, y+2) \\
S(3k+2, y+1) & \xrightarrow{14k+12} & S(5k+4, y) \\
\end{array}</math>

This pseudo-random walk iterates 275 times until it halts reaching a maximum y value of 14 at iteration 111:
<math display="block">\begin{array}{ll}
S(0,1) & \to S(1,1) \to S(3,2) \to S(6,2) \to S(11, 2) \to S(19, 1) \to S(33, 2) \to S(56, 2) \to S(94, 1) \\
& \to S(158, 2) \to S(264, 1) \to S(441, 1) \to S(736, 1) \to S(1228, 2) \to S(2048, 3) \\
& \vdots \\
& \to S(4065328691604230522442358, 13) \\
& \to S(6775547819340384204070598, 14) \\
& \to S(11292579698900640340117664, 13) \\
& \vdots \\
& \to S(27930059557111373800280446055462487109112535227834136644, 2) \\
& \to S(46550099261852289667134076759104145181854225379723561074, 1) \\
& \to S(77583498769753816111890127931840241969757042299539268458, 2) \\
& \to S(129305831282923026853150213219733736616261737165898780764, 1) \\
& \to S(215509718804871711421917022032889561027102895276497967941, 1) \\
& \to S(359182864674786185703195036721482601711838158794163279903, 2) \\
& \vdots \\
& \to S(5894430516013404355095519889620117404469367857588232386361874, 2) \\
& \to S(9824050860022340591825866482700195674115613095980387310603124, 1) \\
& \to S(16373418100037234319709777471166992790192688493300645517671874, 0)
\end{array}</math>

If it were a truly random walk, there would be a 5.9% chance that it takes at least 275 steps to reach 0. So this program is mildly lucky.

== Cryptids ==

=== Fenrir ===
[[File:Fractran 22 Cryptid.webp|alt=The space-time diagram of Fenrir.|thumb|Partial space-time diagram of Fenrir.]]
"Fenrir" is a family of 3 size 22 [[Cryptids]] discovered by Jason Yuen (@-d) and Claude Opus 4.6 on 22 Mar 2026. Out of 500 holdouts of size 22, Claude Opus 4.6 used Lean to prove that 497 holdouts were non-halting. The remaining 3 holdouts are the Fenrir family.[https://discord.com/channels/960643023006490684/1438019511155691521/1485415054475268179] Discord user @ZTS439 shared [https://discord.com/channels/960643023006490684/1438019511155691521/1487251919444508723 some analysis] and a [https://discord.com/channels/960643023006490684/1438019511155691521/1487252789158613002 Python program] for it. Its name comes from [[wikipedia:Norse_mythology|nordic mythology]]; [[wikipedia:Fenrir|Fenrir]] is the wolf that helps destroy the world during [[wikipedia:Ragnarök|Ragnarök]].

{| class="wikitable"
|+
!Holdout number
!Holdout
!Vector Representation
|-
| 29/2003
| <code>[1/15, 27/77, 49/3, 10/49, 33/2]</code>
|<math>\begin{bmatrix}
0 & -1 & -1 & 0 & 0 \\
0 & 3 & 0 & -1 & -1 \\
0 & -1 & 0 & 2 & 0 \\
1 & 0 & 1 & -2 & 0 \\
-1 & 1 & 0 & 0 & 1
\end{bmatrix}</math>
|-
| 41/2003
| <code>[1/15, 49/3, 27/77, 10/49, 33/2]</code>
|<math>\begin{bmatrix}
0 & -1 & -1 & 0 & 0 \\
0 & -1 & 0 & 2 & 0 \\
0 & 3 & 0 & -1 & -1 \\
1 & 0 & 1 & -2 & 0 \\
-1 & 1 & 0 & 0 & 1
\end{bmatrix}</math>
|-
| 430/2003
| <code>[27/35, 1/33, 25/3, 22/25, 21/2]</code>
|<math>\begin{bmatrix}
0 & 3 & -1 & -1 & 0 \\
0 & -1 & 0 & 0 & -1 \\
0 & -1 & 2 & 0 & 0 \\
1 & 0 & -2 & 0 & 1 \\
-1 & 1 & 0 & 1 & 0
\end{bmatrix}</math>
|}

All 3 holdouts follow a biased random walk that somewhat resembles [[Hydra]]. Let <math>S(x,y) = [x, 0, 0, 2, y]</math> (for 29/2003 and 41/2003) or <math>S(x,y) = [x, 0, 2, y, 0]</math> (for 430/2003), then:

<math display="block">\begin{array}{lcl}
[1,0,0,0,0] & \to & S(0,1) \\
S(0, 2y) & = & \text{halt} \\
S(x, 2y) & \to & S(x-1, 5y+2) \\
S(x, 2y+1) & \to & S(x+2, 5y)
\end{array}</math>

The first few visited states are $$S(0, 1) \to S(2, 0) \to S(1, 2) \to S(0, 7) \to S(2, 15) \to S(4, 35)$$

=== Frankenstein's Monster ===
[[File:Frankenstein's Monster.webp|alt=Partial space-time diagram of Frankenstein's Monster.|thumb|Partial space-time diagram of Frankenstein's Monster.]]
"Frankenstein's Monster" is a size 23 [[Cryptid]]. It was created by tweaking a single instruction in the size 22 champion. This tweak switches it from a unbiased random walk to a biased one and thus makes halting probviously impossible. It is called Frankenstein's Monster since it was found by a combination of exhaustive search and hand design.[https://discord.com/channels/960643023006490684/1438019511155691521/1449138938215141478]

<code>[1/12, 9/10, 14/3, 121/2, 5/7, 3/11]</code> <math display="block">\begin{bmatrix}
-2 & -1 & 0 & 0 & 0 \\
-1 & 2 & -1 & 0 & 0 \\
1 & -1 & 0 & 1 & 0 \\
-1 & 0 & 0 & 0 & 2 \\
0 & 0 & 1 & -1 & 0 \\
0 & 1 & 0 & 0 & -1
\end{bmatrix}</math>

Its behavior is extremely similar to the size 22 champion. Let <math>S(x,y) = [0, 0, x, 0, y]</math>, then:

<math display="block">\begin{array}{lcl}
[1,0,0,0,0] & \xrightarrow{1} & S(0,2) \\
S(x, 0) & = & \text{halt} \\
S(3k, y+1) & \xrightarrow{14k+4} & S(5k+1, y+2) \\
S(3k+1, y+1) & \xrightarrow{14k+10} & S(5k+3, y+4) \\
S(3k+2, y+1) & \xrightarrow{14k+12} & S(5k+4, y)
\end{array}</math>

with the only difference that the y values now change by {+1,+3,-1} depending on the value of x mod 3 (instead of {0,+1,-1} in the original size 22 program). The x values follow the exact same path as in the original size 22 champion, but the y values quickly grow linearly with the number of iterations (as expected by the random model):
0: S(0, 1) @ 1 (0.00s)
100_000: S(10^22_185, 100171) @ 10^22_186 (0.87s)
200_000: S(10^44_370, 200187) @ 10^44_371 (3.42s)
300_000: S(10^66_555, 300759) @ 10^66_556 (7.68s)
400_000: S(10^88_740, 400451) @ 10^88_741 (13.64s)
500_000: S(10^110_925, 500421) @ 10^110_925 (21.28s)
600_000: S(10^133_109, 600351) @ 10^133_110 (30.62s)
700_000: S(10^155_294, 700319) @ 10^155_295 (41.64s)
800_000: S(10^177_479, 799911) @ 10^177_480 (54.30s)
900_000: S(10^199_664, 900259) @ 10^199_665 (68.59s)
1_000_000: S(10^221_849, 1000853) @ 10^221_850 (84.51s)
...
4_000_000: S(10^887_395, 4000201) @ 10^887_396 (1474.02s)
...
27_500_000: S(10^6_100_841, 27512703) @ 10^6_100_842 (87616.45s)

=== Antihydra-like Cryptid ===
This Cryptid is a size 23 [[Cryptid]]. This Cryptid was [https://discord.com/channels/960643023006490684/1438019511155691521/1449293536737361973 constructed by Maksandchael] by tweaking Frankenstein's Monster to make it as similar to [[Antihydra]] as possible. <code>[9/10, 1/6, 1331/2, 14/3, 5/7, 3/11]</code>

<math display="block">\begin{bmatrix}
-1 & 2 & -1 & 0 & 0 \\
-1 & -1 & 0 & 0 & 0 \\
-1 & 0 & 0 & 0 & 3 \\
1 & -1 & 0 & 1 & 0 \\
0 & 0 & 1 & -1 & 0 \\
0 & 1 & 0 & 0 & -1
\end{bmatrix}</math><pre>
H(a, b) = [0, 0, a-2, 0, b]
Start -> H(2, 3)
H(2a, b) -> H(3a, b+2)
H(2a+1, b+1) -> H(3a+1, b)
H(a,0) -> halt
</pre>

=== Hydra ===
[[File:Hydra.webp|alt=Partial space-time diagram of Hydra.|thumb|300x300px|Partial space-time diagram of Hydra.]]
A size 25 program was produced and golfed by hand to simulate [[Hydra]] rules ([https://discord.com/channels/960643023006490684/1438019511155691521/1449829146040467681 Discord]):

<code>[363/14, 125/2, 22/21, 1/3, 7/11, 14/5]</code>
<math display="block">
\begin{bmatrix}
-1 & 1 & 0 & -1 & 2 \\
-1 & 0 & 3 & 0 & 0 \\
1 & -1 & 0 & -1 & 1 \\
0 & -1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & -1 \\
1 & 0 & -1 & 1 & 0
\end{bmatrix}
</math>

The intended interpretation is that if we let <math>S(h,w) = [1, 0, w, h-3, 0]
</math> then it follows the following rules:

<math display="block">\begin{array}{lcl}
[1,0,\dots] & = & S(3, 0) \\
S(2k, 0) & \to^* & \text{halt} \\
S(2k, w+1) & \to^* & S(3k, w) \\
S(2k+1, w) & \to^* & S(3k+1, w+2)
\end{array}</math>

=== BMO1 ===
[[File:Ftran bmo1.png|alt=Partial space-time diagram of BMO 1.|thumb|Partial space-time diagram of BMO 1.]]
A size 36 program was produced by hand to simulate [[BMO1]] rules ([https://discord.com/channels/960643023006490684/1438019511155691521/1440018895212642424 Discord]):

<code>[153/55, 2/11, 26/35, 3/7, 11/17, 7/13, 25/6, 55/2, 14/3]</code>
<math display="block">
\begin{bmatrix}
0 & 2 & -1 & 0 & -1 & 0 & 1 \\
1 & 0 & 0 & 0 & -1 & 0 & 0 \\
1 & 0 & -1 & -1 & 0 & 1 & 0 \\
0 & 1 & 0 & -1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 & -1 \\
0 & 0 & 0 & 1 & 0 & -1 & 0 \\
-1 & -1 & 2 & 0 & 0 & 0 & 0 \\
-1 & 0 & 1 & 0 & 1 & 0 & 0 \\
1 & -1 & 0 & 1 & 0 & 0 & 0
\end{bmatrix}
</math>

Let <math>A(a,b) = [a, b, 0, 0, 0, 0, 0]</math>, then it follows the rules:

<math display="block">\begin{array}{lcl}
[1,0,\dots] & \to^* & A(1, 2) \\
A(a, b) & \to^* & A(a-b, 4b+2) & \text{if } a > b \\
A(a, b) & \to^* & A(2a+1, b-a) & \text{if } a 

=== BMO 6 (“Space Needle”) ===
[[File:Space Needle.webp|alt=Partial space-time diagram of Space Needle.|thumb|Partial space-time diagram of Space Needle.]]
A size 48 program was produced by hand to simulate [https://wiki.bbchallenge.org/wiki/1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD BMO 6] rules ([https://discord.com/channels/960643023006490684/1438019511155691521/1441137371046482071 Discord])

<code>[77/2, 2/99, 17/33, 13/11, 285/119, 17/19, 1375/51, 1/17, 3/5, 243/7, 10/13]</code>

<math>\begin{bmatrix}
-1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\
1 & -2 & 0 & 0 & -1 & 0 & 0 & 0 \\
0 & -1 & 0 & 0 & -1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 \\
0 & 1 & 1 & -1 & 0 & 0 & -1 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 \\
0 & -1 & 3 & 0 & 1 & 0 & -1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 \\
0 & 1 & -1 & 0 & 0 & 0 & 0 & 0 \\
0 & 5 & 0 & -1 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & -1 & 0 & 0
\end{bmatrix}</math><pre>A(a, b) = B^a C^b E or B^(a-2) C^b D E

Start: A(7, 1)

A(1, b) --> halt

A(2a, b) --> A(5a+b+2, 1)

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

== References ==
<references />

[[Category:Functions]]

Quasihalt

2024-07-10T13:26:39Z

Hsjoihs: Created page with "A program is called '''quasihalting''' if it has any states which are reached no more than a fixed number of times during the course of a computation.<ref>https://www.sligocki.com/2021/03/06/beeping-busy-beaver/</ref> A machine is said to '''quasihalt''' when it ''enters'' a cycle of behavior in which it does not visit all machine states.<ref>https://nickdrozd.github.io/2020/10/08/quasihalting-behavior.html</ref><ref>https://discord.com/channels/960643023006490684/10265..."

A program is called '''quasihalting''' if it has any states which are reached no more than a fixed number of times during the course of a computation.<ref>https://www.sligocki.com/2021/03/06/beeping-busy-beaver/</ref>

A machine is said to '''quasihalt''' when it ''enters'' a cycle of behavior in which it does not visit all machine states.<ref>https://nickdrozd.github.io/2020/10/08/quasihalting-behavior.html</ref><ref>https://discord.com/channels/960643023006490684/1026577255754903572/1034531129941819493</ref><ref>https://discord.com/channels/960643023006490684/1026577255754903572/1034531417742385263</ref>

== Relationship with Beeping Busy Beavers ==

By introducing the concept of quasihalting, it becomes succinct and straightforward to define the [[Beeping Busy Beaver]] problem: "the Beeping Busy Beaver problem is to find the TM which runs longest before quasihalting."<ref>https://www.sligocki.com/2021/03/06/beeping-busy-beaver/</ref>

== References ==

Cryptids

2024-07-10T13:14:41Z

Hsjoihs: Make "probviously" and "quasihalt" into links

'''Cryptids''' are Turing Machines whose behavior (when started on a blank tape) can be described completely by a relatively simple mathematical rule, but where that rule falls into a class of unsolved (and presumed hard) mathematical problems. This definition is somewhat subjective (What counts as a simple rule? What counts as a hard problem?). In practice, most currently known small Cryptids have [[Collatz-like]] behavior. In other words, the halting problem from blank tape of cryptids is mathematically-hard.

If there exists a Cryptid with n states and m symbols, then BB(n, m) cannot be solved without solving this hard math problem.

The name Cryptid was proposed by Shawn Ligocki in an Oct 2023 [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html blog post] announcing the discovery of [[Bigfoot]].

== Cryptids at the Edge ==

This is a list of Minimal Cryptids (Cryptids in a class with no strictly smaller known Cryptid). All of these Cryptids were "discovered in the wild" rather than "constructed".

{| class="wikitable"
|-
! Name !! BB domain !! Machine !! Announcement !! Date !! Discoverer !! Note
|-
| [[Bigfoot]]|| [[BB(3,3)]]|| <code>1RB2RA1LC_2LC1RB2RB_---2LA1LA</code>|| [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html BB(3, 3) is hard] || Nov 2023 || [[User:Sligocki|Shawn Ligocki]] ||
|-
| [[Hydra]]|| [[BB(2,5)]]|| <code>1RB3RB---3LA1RA_2LA3RA4LB0LB0LA</code>|| [https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is hard] || May 2024 || Daniel Yuan ||
|-
| || BB(2,5) || <code>1RB3RB---3LA1RA_2LA3RA4LB0LB1LB</code>||[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html#a-bonus-cryptid A Bonus Cryptid] || May 2024 || Daniel Yuan ||
|-
|[[Antihydra]] || [[BB(6)]] || <code>1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA</code> || [https://discord.com/channels/960643023006490684/1026577255754903572/1256223215206924318 Discord message] || June 2024 || <code>@mxdys</code>, shown to be a Cryptid by <code>@racheline</code>. ||Same as '''Hydra''' but starting iteration from 8 instead of 3 and with termination condition <code>
O > 2E
</code> instead of <code>
E > 2O
</code>, hence the name '''Antihydra'''.
|}

== Larger Cryptids ==

A more complete list of all known Cryptids over a wider range of states and symbols. These Cryptds were all "constructed" rather than "discovered".

{| class="wikitable"
|-
! Name !! BB domain !! Machine !! Announcement !! Date !! Discoverer !! Note
|-
|RH
|BB(744)
|https://github.com/sorear/metamath-turing-machines/blob/master/riemann-matiyasevich-aaronson.nql
|
|2016
|Matiyasevich and O’Rear
|The machine halts if and only if [https://en.wikipedia.org/wiki/Riemann_hypothesis Riemann Hypothesis] is false.
|-
|Goldbach
|BB(27)
|https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6<nowiki/>(unverified)
|
|2016
|anonymous
|The machine halts if and only if [https://en.wikipedia.org/wiki/Goldbach%27s_conjecture Golbach's conjecture] is false. To the best of our knowledge this construction has not been independently verified.
|-
| Erdős || BB(5,4) and
BB(15)
|
https://docs.bbchallenge.org/other/powers_of_two_5_4.txt

https://docs.bbchallenge.org/other/powers_of_two_15_2.txt
|| [https://arxiv.org/abs/2107.12475 arxiv preprint] || Jul 2021 || [[User:Cosmo|Tristan Stérin]] (<code>@cosmo</code>) and Damien Woods || The machine halts if and only if the following conjecture by Erdős is false: "For all n > 8, there is at least one 2 in the base-3 representation of 2^n"
|-
|Weak Collatz
|BB(124) and BB(43,4)
|https://docs.bbchallenge.org/other/weak_Collatz_conjecture_124_2.txt (unverified)
https://docs.bbchallenge.org/other/weak_Collatz_conjecture_43_4.txt (unverified)
|
|Jul 2021
|[[User:Cosmo|Tristan Stérin]]
|The machine halts if and only if the "weak Collatz conjecture" is false. The weak Collatz conjecture states that the iterated Collatz map (3x+1) has only one cycle on the positive integers.
Not independently verified, and probably easy to further optimise.
|-
| Bigfoot - compiled|| [[BB(7)]]|| <code>0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB</code>|| [https://github.com/sligocki/sligocki.github.io/issues/8#issuecomment-2140887228 Bigfoot Comment] || June 2024 || <code>@Iijil1</code>|| Compilation of Bigfoot into 2 symbols, there was a previous compilation [https://github.com/sligocki/sligocki.github.io/issues/8#issuecomment-1774200442 with 8 states]
|-
| Hydra - compiled
|BB(9)
|<pre>
0RB0LD_1LC0LI_1LD1LB_0LE0RG_1RF0RH_1RA---_0RD0LB_0RA---_0RF1RZ
</pre>[[File:Hydra_9_states.txt]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1251572501578780782 Discord message]
|June 2024
|<code>@Iijil1</code>
|Compilation of Hydra into 2 symbols, all[https://discord.com/channels/960643023006490684/1084047886494470185/1253193750486974464 confirmed by Shawn Ligocki]. <code>@Iijil1</code> provided 24 TMs which all emulate the same behavior.
[https://discord.com/channels/960643023006490684/1084047886494470185/1247560072427474955 Previous compilation had 10 states], by Daniel Yuan, also [https://discord.com/channels/960643023006490684/1084047886494470185/1247579473042346136 confirmed by Shawn Ligocki].
|}

== Beeping Busy Beaver ==

Cryptids were actually noticed in the [[Beeping Busy Beaver]] problem before they were in the classic Busy Beaver. See [https://www.sligocki.com/2022/04/03/mother-of-giants.html Mother of Giants] describing a "family" of Turing machines which "[[probviously]]" [[quasihalt]], but requires solving a Collatz-like problem in order to actually prove it. They are all TMs formed by filling in the missing transition in <code>1RB1LE_0LC0LB_0LD1LC_1RD1RA_---0LA</code> with different values.

Standard TM Text format

2024-07-10T12:39:16Z

Hsjoihs: Redirected page to Turing machine#Standard text format

#REDIRECT [[Turing_machine#Standard_text_format]]

Standard text format

2024-07-10T12:38:37Z

Hsjoihs: Redirected page to Turing machine#Standard text format

#REDIRECT [[Turing_machine#Standard_text_format]]

Beeping Busy Beaver

2024-07-10T12:22:15Z

Hsjoihs: Not $, but <math>

A Beeping Busy Beaver (BBB) is a concept defined on a ''beeping Turing machine'', which is a Turing machine that has a special state named "beep state". The goal of a BBB is as follows: when starting from a totally blank tape, we want the final beep to happen as late as possible. The phrasing "final beep" means that the machine must beep finitely many times.

Formally, we define the <math>n</math>th Beeping Busy Beaver number as

<math display="block">\operatorname{BBB}(n) := \max_{{M \in T(n)\ :\ b(M) < \infty}} b(M)</math>

where <math>T(n)</math> is the set of Turing machines with <math>n</math> states and two symbols.

== Significance ==

It is easy to see that <math>\operatorname{BBB}(n) \ge \operatorname{BB}(n)</math>, by letting the beep state be the state that is reached immediately before the halt state. Moreover, it turns out that <math>\operatorname{BBB}</math> grows uncomputably faster than <math>\operatorname{BB}</math>.

== History ==
Section 5.10 of the seminal survey "The Busy Beaver Frontier" by Scott Aaronson <ref name=":0">https://www.scottaaronson.com/papers/bb.pdf</ref> introduced the concept of BBB.

== References ==

Beeping Busy Beaver

2024-07-10T12:21:41Z

Hsjoihs: Not $, but <math>

A Beeping Busy Beaver (BBB) is a concept defined on a ''beeping Turing machine'', which is a Turing machine that has a special state named "beep state". The goal of a BBB is as follows: when starting from a totally blank tape, we want the final beep to happen as late as possible. The phrasing "final beep" means that the machine must beep finitely many times.

Formally, we define the <math>n</math>th Beeping Busy Beaver number as

<math display="block">\operatorname{BBB}(n) := \max_{{M \in T(n)\ :\ b(M) < \infty}} b(M)</math>

where $T(n)$ is the set of Turing machines with <math>n</math> states and two symbols.

== Significance ==

It is easy to see that <math>\operatorname{BBB}(n) \ge \operatorname{BB}(n)</math>, by letting the beep state be the state that is reached immediately before the halt state. Moreover, it turns out that <math>\operatorname{BBB}</math> grows uncomputably faster than <math>\operatorname{BB}</math>.

== History ==
Section 5.10 of the seminal survey "The Busy Beaver Frontier" by Scott Aaronson <ref name=":0">https://www.scottaaronson.com/papers/bb.pdf</ref> introduced the concept of BBB.

== References ==

Beeping Busy Beaver

2024-07-10T12:20:35Z

Hsjoihs: Created page with "A Beeping Busy Beaver (BBB) is a concept defined on a ''beeping Turing machine'', which is a Turing machine that has a special state named "beep state". The goal of a BBB is as follows: when starting from a totally blank tape, we want the final beep to happen as late as possible. The phrasing "final beep" means that the machine must beep finitely many times. Formally, we define the $n$th Beeping Busy Beaver number as <math display="block">\operatorname{BBB}(..."

A Beeping Busy Beaver (BBB) is a concept defined on a ''beeping Turing machine'', which is a Turing machine that has a special state named "beep state". The goal of a BBB is as follows: when starting from a totally blank tape, we want the final beep to happen as late as possible. The phrasing "final beep" means that the machine must beep finitely many times.

Formally, we define the $n$th Beeping Busy Beaver number as

<math display="block">\operatorname{BBB}(n) := \max_{{M \in T(n)\ :\ b(M) < \infty}} b(M)</math>

where $T(n)$ is the set of Turing machines with $n$ states and two symbols.

== Significance ==

It is easy to see that $\operatorname{BBB}(n) \ge \operatorname{BB}(n)$, by letting the beep state be the state that is reached immediately before the halt state. Moreover, it turns out that $\operatorname{BBB}$ grows uncomputably faster than $\operatorname{BB}$.

== History ==
Section 5.10 of the seminal survey "The Busy Beaver Frontier" by Scott Aaronson <ref name=":0">https://www.scottaaronson.com/papers/bb.pdf</ref> introduced the concept of BBB.

== References ==

1RB2LC1RC 2LC---2RB 2LA0LB0RA

2024-07-10T11:54:32Z

Hsjoihs: Removing the space after the comma when in the main text (but not when it is a citation), adhering to https://discord.com/channels/960643023006490684/1249351319756607619/1260560590192115764

{{machine|1RB2LC1RC_2LC---2RB_2LA0LB0RA}}
https://bbchallenge.org/1RB2LC1RC_2LC---2RB_2LA0LB0RA

This is a [[BB(3,3)]] [[holdout]] under active exploration. It simulates a complex set of Collatz-like rules with two decreasing parameters and seems as if it may be a new [[Cryptid]] (and perhaps even one that "[[probviously]]" halts! But this is really speculation at this point.)

This is holdout #758 on Justin's 3x3 mugshots. And if you start in state C it is a [[permutation]] of #153: <code>1RB0LB0RC_2LC2LA1RA_1RA1LC---</code>.

NOTE: These rules are under active development and may have mistakes or typos.

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

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

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

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

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

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

(1, b, 0) -> Halt

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Bigfoot

2024-07-10T11:54:12Z

Hsjoihs: Removing the space after the comma when in the main text (but not when it is a citation), adhering to https://discord.com/channels/960643023006490684/1249351319756607619/1260560590192115764

{{machine|1RB2RA1LC_2LC1RB2RB_---2LA1LA}}
'''Bigfoot''' is a [[BB(3,3)]] [[Cryptids|Cryptid]]: <code>1RB2RA1LC_2LC1RB2RB_---2LA1LA</code>

It simulates the Collatz-like function

<math display="block">\begin{array}{l}
A(a, & 6k, & c) & \to & A(a, & 8k+c-1, & 2) & \text{if} & 8k+c \ge 1 \\
A(a, & 6k+1, & c) & \to & A(a+1, & 8k+c-1, & 3) & \text{if} & 8k+c \ge 1 \\
A(a, & 6k+2, & c) & \to & A(a-1, & 8k+c+3, & 2) & \text{if} & a \ge 1 \\
A(a, & 6k+3, & c) & \to & A(a, & 8k+c+1, & 5) \\
A(a, & 6k+4, & c) & \to & A(a+1, & 8k+c+3, & 2) \\
A(a, & 6k+5, & c) & \to & A(a, & 8k+c+5, & 3) \\
\end{array}</math>

<math display="block">A(0, 6k+2, c) \to \text{Halt}(16k+2c+7)</math>

starting from <math>A(2, 1, 2)</math>.

It was discovered by Shawn Ligocki on 14 Oct 2023 and shared in the blog post [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html BB(3, 3) is Hard].

Collatz-like

2024-07-10T11:51:58Z

Hsjoihs: Removing the space after the comma when in the main text (but not when it is a citation), adhering to https://discord.com/channels/960643023006490684/1249351319756607619/1260560590192115764

A '''Collatz-like function''' is a partial function defined piecewise depending on the remainder of an input modulo some number. The canonical example is the original Collatz function:<math display="block">\begin{array}{l}
c(2k) & = & k \\
c(2k+1) & = & 3k+2 \\
\end{array}</math>

A '''Collatz-like problem''' is a question about the behavior of iterating a Collatz-like function. Collatz-like problems are famously difficult.

Many [[Busy Beaver Champions]] have '''Collatz-like behavior''', meaning that their behavior can be concisely described via the iterated values of a Collatz-like function.

== Examples ==

=== BB(5,2) Champion ===
Consider the [[BB(5,2)]] Champion (<code>1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA</code>) and the generalize configuration:

<math display="block">M(n) = 0^\infty \; \textrm{<A} \; 1^n \; 0^\infty</math>Pascal Michel showed that:

<math display="block">\begin{array}{lcl}
0^\infty \; \textrm{<A} \; 0^\infty & = & M(0) \\
M(3k) & \xrightarrow{5 k^2 + 19 k + 15} & M(5k+6) \\
M(3k+1) & \xrightarrow{5 k^2 + 25 k + 27} & M(5k+9) \\
M(3k+2) & \xrightarrow{6k +12} & 0^\infty \;\; 1 \;\; \textrm{H>} \;\; 01 \;\; {(001)}^{k+1} \;\; 1 \;\; 0^\infty \\
\end{array}</math>

Starting on a blank tape <math>C(0)</math>, these rules iterate 15 times before reaching the halt config.<ref>[https://bbchallenge.org/~pascal.michel/beh#tm52a Pascal Michel's Analysis of the BB(5, 2) Champion]</ref>

=== Hydra ===
Consider Hydra (a [[Cryptids|Cryptid]]) <code>1RB3RB---3LA1RA_2LA3RA4LB0LB0LA</code> and the generalized configuration:

<math display="block">C(a, b) = 0^\infty \; \textrm{ 
Daniel Yuan showed that:<math display="block">\begin{array}{l}
\\
0^\infty \; \textrm{A>} \; 0^\infty & & \xrightarrow{19} & C(3, 0) \\
C(2n, & 0) & \to & \text{Halt}(9n-6) \\
C(2n, & b+1) & \to & C(3n, & b) \\
C(2n+1, & b) & \to & C(3n+1, & b+2) \\
\end{array}</math>

Where <math>\textrm{Halt}(n)</math> is a halting configuration with <math>n</math> non-zero symbols on the tape.

Starting from config <math>C(3, 0)</math> this simulates a pseudo-random walk along the <math>b</math> parameter, increasing it by 2 every time <math>a</math> is odd, decreasing by 1 every time it's even. Deciding whether or not Hydra halts requires being able to prove a detailed question about the trajectory of the Collatz-like function<math display="block">\begin{array}{l}
h(2n) & = & 3n \\
h(2n+1) & = & 3n+1 \\
\end{array}</math>starting from 3:

<math display="block">\begin{array}{l}
\\
3 \xrightarrow{O} 4 \xrightarrow{E} 6\xrightarrow{E} 9 \xrightarrow{O} 13 \xrightarrow{O} 19 \xrightarrow{O} 28 \xrightarrow{E} 42 \xrightarrow{E} 63 \cdots \\
\end{array}
</math>

Specifically, will it ever reach a point where the cumulative number of <code>E</code> (even transitions) applied is greater than twice the number of <code>O</code> (odd transitions) applied?<ref>Shawn Ligocki. [https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)]. 10 May 2024.</ref>

=== Tetration Machine ===
Consider the current [[BB(6,2)]] Champion (discovered by Pavel Kropitz in May 2022) <code>1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE</code> and consider the general configuration:<math display="block">K(a, b) = 0^\infty \; 1 \; 0^n \; 11 \; 0^5 \; \textrm{C>} \; 0^\infty</math>Shawn Ligocki showed that:
<math display="block">\begin{array}{l}
\\
0^\infty \; \textrm{A>} \; 0^\infty & \xrightarrow{45} & K(5) \\
K(4k) & \to & \text{Halt}(9n-6) \\
K(4n+1) & \to & K(\frac{3^{k+3} - 11}{2}) \\
K(4n+2) & \to & K(\frac{3^{k+3} - 11}{2}) \\
K(4n+3) & \to & K(\frac{3^{k+3} + 1}{2}) \\
\end{array}</math>

Starting from config <math>K(5)</math>, these rules iterate 15 times before reaching the halt config leaving over <math>10 \uparrow\uparrow 15</math> non-zero symbols on the tape.<ref>Shawn Ligocki. [https://www.sligocki.com/2022/06/21/bb-6-2-t15.html BB(6, 2) > 10↑↑15]. 21 Jun 2022.</ref>

== References ==
<references />

Cryptids

2024-07-10T11:49:35Z

Hsjoihs: Removing the space after the comma when in the main text (but not when it is a citation), adhering to https://discord.com/channels/960643023006490684/1249351319756607619/1260560590192115764

'''Cryptids''' are Turing Machines whose behavior (when started on a blank tape) can be described completely by a relatively simple mathematical rule, but where that rule falls into a class of unsolved (and presumed hard) mathematical problems. This definition is somewhat subjective (What counts as a simple rule? What counts as a hard problem?). In practice, most currently known small Cryptids have [[Collatz-like]] behavior. In other words, the halting problem from blank tape of cryptids is mathematically-hard.

If there exists a Cryptid with n states and m symbols, then BB(n, m) cannot be solved without solving this hard math problem.

The name Cryptid was proposed by Shawn Ligocki in an Oct 2023 [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html blog post] announcing the discovery of [[Bigfoot]].

== Cryptids at the Edge ==

This is a list of Minimal Cryptids (Cryptids in a class with no strictly smaller known Cryptid). All of these Cryptids were "discovered in the wild" rather than "constructed".

{| class="wikitable"
|-
! Name !! BB domain !! Machine !! Announcement !! Date !! Discoverer !! Note
|-
| [[Bigfoot]]|| [[BB(3,3)]]|| <code>1RB2RA1LC_2LC1RB2RB_---2LA1LA</code>|| [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html BB(3, 3) is hard] || Nov 2023 || [[User:Sligocki|Shawn Ligocki]] ||
|-
| [[Hydra]]|| [[BB(2,5)]]|| <code>1RB3RB---3LA1RA_2LA3RA4LB0LB0LA</code>|| [https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is hard] || May 2024 || Daniel Yuan ||
|-
| || BB(2,5) || <code>1RB3RB---3LA1RA_2LA3RA4LB0LB1LB</code>||[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html#a-bonus-cryptid A Bonus Cryptid] || May 2024 || Daniel Yuan ||
|-
|[[Antihydra]] || [[BB(6)]] || <code>1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA</code> || [https://discord.com/channels/960643023006490684/1026577255754903572/1256223215206924318 Discord message] || June 2024 || <code>@mxdys</code>, shown to be a Cryptid by <code>@racheline</code>. ||Same as '''Hydra''' but starting iteration from 8 instead of 3 and with termination condition <code>
O > 2E
</code> instead of <code>
E > 2O
</code>, hence the name '''Antihydra'''.
|}

== Larger Cryptids ==

A more complete list of all known Cryptids over a wider range of states and symbols. These Cryptds were all "constructed" rather than "discovered".

{| class="wikitable"
|-
! Name !! BB domain !! Machine !! Announcement !! Date !! Discoverer !! Note
|-
|RH
|BB(744)
|https://github.com/sorear/metamath-turing-machines/blob/master/riemann-matiyasevich-aaronson.nql
|
|2016
|Matiyasevich and O’Rear
|The machine halts if and only if [https://en.wikipedia.org/wiki/Riemann_hypothesis Riemann Hypothesis] is false.
|-
|Goldbach
|BB(27)
|https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6<nowiki/>(unverified)
|
|2016
|anonymous
|The machine halts if and only if [https://en.wikipedia.org/wiki/Goldbach%27s_conjecture Golbach's conjecture] is false. To the best of our knowledge this construction has not been independently verified.
|-
| Erdős || BB(5,4) and
BB(15)
|
https://docs.bbchallenge.org/other/powers_of_two_5_4.txt

https://docs.bbchallenge.org/other/powers_of_two_15_2.txt
|| [https://arxiv.org/abs/2107.12475 arxiv preprint] || Jul 2021 || [[User:Cosmo|Tristan Stérin]] (<code>@cosmo</code>) and Damien Woods || The machine halts if and only if the following conjecture by Erdős is false: "For all n > 8, there is at least one 2 in the base-3 representation of 2^n"
|-
|Weak Collatz
|BB(124) and BB(43,4)
|https://docs.bbchallenge.org/other/weak_Collatz_conjecture_124_2.txt (unverified)
https://docs.bbchallenge.org/other/weak_Collatz_conjecture_43_4.txt (unverified)
|
|Jul 2021
|[[User:Cosmo|Tristan Stérin]]
|The machine halts if and only if the "weak Collatz conjecture" is false. The weak Collatz conjecture states that the iterated Collatz map (3x+1) has only one cycle on the positive integers.
Not independently verified, and probably easy to further optimise.
|-
| Bigfoot - compiled|| [[BB(7)]]|| <code>0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB</code>|| [https://github.com/sligocki/sligocki.github.io/issues/8#issuecomment-2140887228 Bigfoot Comment] || June 2024 || <code>@Iijil1</code>|| Compilation of Bigfoot into 2 symbols, there was a previous compilation [https://github.com/sligocki/sligocki.github.io/issues/8#issuecomment-1774200442 with 8 states]
|-
| Hydra - compiled
|BB(9)
|<pre>
0RB0LD_1LC0LI_1LD1LB_0LE0RG_1RF0RH_1RA---_0RD0LB_0RA---_0RF1RZ
</pre>[[File:Hydra_9_states.txt]]
|[https://discord.com/channels/960643023006490684/1084047886494470185/1251572501578780782 Discord message]
|June 2024
|<code>@Iijil1</code>
|Compilation of Hydra into 2 symbols, all[https://discord.com/channels/960643023006490684/1084047886494470185/1253193750486974464 confirmed by Shawn Ligocki]. <code>@Iijil1</code> provided 24 TMs which all emulate the same behavior.
[https://discord.com/channels/960643023006490684/1084047886494470185/1247560072427474955 Previous compilation had 10 states], by Daniel Yuan, also [https://discord.com/channels/960643023006490684/1084047886494470185/1247579473042346136 confirmed by Shawn Ligocki].
|}

== Beeping Busy Beaver ==

Cryptids were actually noticed in the [[Beeping Busy Beaver]] problem before they were in the classic Busy Beaver. See [https://www.sligocki.com/2022/04/03/mother-of-giants.html Mother of Giants] describing a "family" of Turing machines which "probviously" quasihalt, but requires solving a Collatz-like problem in order to actually prove it. They are all TMs formed by filling in the missing transition in <code>1RB1LE_0LC0LB_0LD1LC_1RD1RA_---0LA</code> with different values.

BB(4)

2024-07-10T08:34:26Z

Hsjoihs: Add the Allen Brady's dissertation of 1965

'''BB(4)''' refers to the 4th value of the [[Busy Beaver function]].

== History ==
In this Section, we use Radó's original S (number of steps) and Σ (number of ones on the final tape) notations; see [[Busy Beaver Functions]].

* In 1965, Allen Brady proves that S(4) ≥ 84 and Σ(4) ≥ 11.<ref name=":0">Brady, A. H. (1965). Solutions of restricted cases of the halting problem applied to the determination of particular values of a non-computable function. https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/zk51vk21c</ref> (TODO: the abstract says "or ≥ 12 using a different stopping convention")
* In 1966, Allen Brady conjectures Σ(4) = 13 and S(4) = 106.<ref name=":1">Brady, A. H. (1966). The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4. https://ieeexplore.ieee.org/document/4038890 </ref>
* In 1974, Allen Brady proves that S(4) = 107.<ref name=":2">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</ref> (better source needed)
* In 1983, Allen Brady publishes the proof that Σ(4) = 13 and S(4) = 107. <ref name=":3">Brady, A. H. (1983). The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. https://www.ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6/</ref>

== References ==

BB(4)

2024-07-10T08:04:10Z

Hsjoihs: Created page with "'''BB(4)''' refers to the 4th value of the Busy Beaver function. == History == In this Section, we use Radó's original S (number of steps) and Σ (number of ones on the final tape) notations; see Busy Beaver Functions. * In 1966, Allen Brady conjectures Σ(4) = 13 and S(4) = 106.<ref name=":1">Brady, A. H. (1966). The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4. https://ieeexplore.ieee.org/document/4038890 </ref> * In..."

'''BB(4)''' refers to the 4th value of the [[Busy Beaver function]].

== History ==
In this Section, we use Radó's original S (number of steps) and Σ (number of ones on the final tape) notations; see [[Busy Beaver Functions]].

* In 1966, Allen Brady conjectures Σ(4) = 13 and S(4) = 106.<ref name=":1">Brady, A. H. (1966). The Conjectured Highest Scoring Machines for Rado's Σ(k) for the Value k = 4. https://ieeexplore.ieee.org/document/4038890 </ref>
* In 1974, Allen Brady proves that S(4) = 107.<ref name=":2">https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/</ref> (better source needed)
* In 1983, Allen Brady publishes the proof that Σ(4) = 13 and S(4) = 107. <ref name=":3">Brady, A. H. (1983). The determination of the value of Rado’s noncomputable function Σ(k) for four-state Turing machines. https://www.ams.org/journals/mcom/1983-40-162/S0025-5718-1983-0689479-6/</ref>

== References ==

Tree Normal Form

2024-07-10T07:47:16Z

Hsjoihs: Fix typo: programatic → programmatic

'''Tree Normal Form (TNF)''' is the unique standard [[Turing machine]] transition table representation for a class of functionally equivalent TMs (for the purposes of the Busy Beaver problem). TNF is also often used to to describe the process first described by Allen Brady which enumerates all TMs in TNF.

== Background ==
Radó's original definition of a Busy Beaver TM allows any choice of (write symbol, move direction, next state) for every (current state, read symbol) combination. For n-states, m-symbols that leads to <math>N(n,m) = (2m(n+1))^{mn}</math> distinct TMs (Note: there are <math>n+1</math> next states for the n run states and 1 halt state). But for the purposes of searching for Busy Beavers, these contain a lot of redundant TMs. Some notable redundancies are:

# Permutations: Any permutation of non-start states, non-blank symbols or directions leads to a functionally equivalent TM.
# Unused transitions: If the TM (when started on a blank tape) does not actually use all transitions, then the behavior of this TM is identical for all choices of those transitions.
# Halting transitions: Any of the 2m choices for halting transitions lead to the same runtime (and any of <math>2(m-1)</math> lead to same sigma score).
# Number of halting transitions: Any TM without any halting transitions can (obviously) never halt, so they can be ignored for the purposes of solving the Busy Beaver problem.

In order to (significantly) reduce the search space, TNF requires that the TM satisfy the following:

# Canonical permutation: All states (and symbols) are used in order when run on a blank tape. The first move direction is Right.
# Undefined transitions: All unused transitions are marked as blank/undefined <code>---</code>.
# Unique halting transition: All halting transitions are of the form <code>1RZ</code>.
# Require halting transition: TMs must have at least one undefined (<code>---</code>) or halting (<code>1RZ</code>) transition.

== TNF Enumeration ==
TNF enumeration is a process for enumerating all TMs in TNF by recursively expanding a "family tree" of machines:

* Start with a completely undefined TM of the desired size, this is the root node. Ex <code>------_------</code> for BB(2).
* For each unexplored node, run that TM on a blank tape until it reaches an undefined transition (or you give up searching).
* If you reach an undefined transition, then create children nodes from this node for all choices of transitions.
** One option for transition is always the single halting transition <code>1RZ</code>.
** If there is at least one more undefined transition (besides this one being filled in now) then we also allow all combinations of transitions with the following restrictions:
*** The first direction must be Right,
*** The next state may be any previously visited state or the next unvisited one,
*** The write symbol may be any previously used symbol or the next unused one.
*Repeat this on every leaf node (which contains at least one undefined transition).
This enumeration is complete if every leaf node is either a halting TM or an infinite TM that never reaches its undefined transitions. Unfortunately, there is no programmatic way to ensure you are done because that would involve solving the halting problem. Instead it is often helpful to think of TNF enumeration as an iterated process in which the tree is expanded as much as possible early on, but then iteratively refined over time as new leafs are proven to reach undefined transitions.

== TNF-1RB ==
One common additional restriction is that the initial transition is <code>A0→1RB</code>. This is mainly done to exclude <code>A0→0RB</code> TMs. For any TM starting from <code>A0→0RB</code>, the TM starts in state B will have the same exact sigma score and run for exactly one step longer. Many early enumerations used this restriction because they were specifically searching for Σ. It can also be used when searching for the step champion, but requires some post-processing to check for any state permutations that might lead to a few more steps.

== Number of TNF TMs ==
{| class="wikitable" style="text-align: right;"
|+
!
!Total TMs
!TNF TMs
!TNF-1RB TMs
|-
|[[BB(2)]]
|20,736
|
|41
|-
|[[BB(3)]]
|16,777,216
|
|4,057
|-
|[[BB(4)]]
|25,600,000,000
|
|620,261
|-
|[[BB(5)]]
|63,403,380,965,376
|
|126,891,605
|-
|[[BB(6)]]
|232,218,265,089,212,416
|
|~33,436,000,000
|}

Tree Normal Form

2024-07-10T07:45:15Z

Hsjoihs: Fix typo: it's → its

'''Tree Normal Form (TNF)''' is the unique standard [[Turing machine]] transition table representation for a class of functionally equivalent TMs (for the purposes of the Busy Beaver problem). TNF is also often used to to describe the process first described by Allen Brady which enumerates all TMs in TNF.

== Background ==
Radó's original definition of a Busy Beaver TM allows any choice of (write symbol, move direction, next state) for every (current state, read symbol) combination. For n-states, m-symbols that leads to <math>N(n,m) = (2m(n+1))^{mn}</math> distinct TMs (Note: there are <math>n+1</math> next states for the n run states and 1 halt state). But for the purposes of searching for Busy Beavers, these contain a lot of redundant TMs. Some notable redundancies are:

# Permutations: Any permutation of non-start states, non-blank symbols or directions leads to a functionally equivalent TM.
# Unused transitions: If the TM (when started on a blank tape) does not actually use all transitions, then the behavior of this TM is identical for all choices of those transitions.
# Halting transitions: Any of the 2m choices for halting transitions lead to the same runtime (and any of <math>2(m-1)</math> lead to same sigma score).
# Number of halting transitions: Any TM without any halting transitions can (obviously) never halt, so they can be ignored for the purposes of solving the Busy Beaver problem.

In order to (significantly) reduce the search space, TNF requires that the TM satisfy the following:

# Canonical permutation: All states (and symbols) are used in order when run on a blank tape. The first move direction is Right.
# Undefined transitions: All unused transitions are marked as blank/undefined <code>---</code>.
# Unique halting transition: All halting transitions are of the form <code>1RZ</code>.
# Require halting transition: TMs must have at least one undefined (<code>---</code>) or halting (<code>1RZ</code>) transition.

== TNF Enumeration ==
TNF enumeration is a process for enumerating all TMs in TNF by recursively expanding a "family tree" of machines:

* Start with a completely undefined TM of the desired size, this is the root node. Ex <code>------_------</code> for BB(2).
* For each unexplored node, run that TM on a blank tape until it reaches an undefined transition (or you give up searching).
* If you reach an undefined transition, then create children nodes from this node for all choices of transitions.
** One option for transition is always the single halting transition <code>1RZ</code>.
** If there is at least one more undefined transition (besides this one being filled in now) then we also allow all combinations of transitions with the following restrictions:
*** The first direction must be Right,
*** The next state may be any previously visited state or the next unvisited one,
*** The write symbol may be any previously used symbol or the next unused one.
*Repeat this on every leaf node (which contains at least one undefined transition).
This enumeration is complete if every leaf node is either a halting TM or an infinite TM that never reaches its undefined transitions. Unfortunately, there is no programatic way to ensure you are done because that would involve solving the halting problem. Instead it is often helpful to think of TNF enumeration as an iterated process in which the tree is expanded as much as possible early on, but then iteratively refined over time as new leafs are proven to reach undefined transitions.

== TNF-1RB ==
One common additional restriction is that the initial transition is <code>A0→1RB</code>. This is mainly done to exclude <code>A0→0RB</code> TMs. For any TM starting from <code>A0→0RB</code>, the TM starts in state B will have the same exact sigma score and run for exactly one step longer. Many early enumerations used this restriction because they were specifically searching for Σ. It can also be used when searching for the step champion, but requires some post-processing to check for any state permutations that might lead to a few more steps.

== Number of TNF TMs ==
{| class="wikitable" style="text-align: right;"
|+
!
!Total TMs
!TNF TMs
!TNF-1RB TMs
|-
|[[BB(2)]]
|20,736
|
|41
|-
|[[BB(3)]]
|16,777,216
|
|4,057
|-
|[[BB(4)]]
|25,600,000,000
|
|620,261
|-
|[[BB(5)]]
|63,403,380,965,376
|
|126,891,605
|-
|[[BB(6)]]
|232,218,265,089,212,416
|
|~33,436,000,000
|}