BusyBeaverWiki - User contributions [en]

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
|}