BB(6): Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
m (Replace underscores with spaces →‎Techniques)
No edit summary
Line 1: Line 1:
The 6-state, 2-symbol Busy Beaver problem '''BB(6)''' is unsolved. With the discovery of [[Antihydra]] in 2024, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(6).
The 6-state, 2-symbol Busy Beaver problem '''BB(6)''' is unsolved. With the discovery of [[Antihydra]] in 2024, we now know that we must solve a [[Collatz-like]] problem in order to solve BB(6).


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


<math display="block">S(6) > \Sigma(6) > 10 \uparrow\uparrow 15</math>
<math display="block">S(6) > \Sigma(6) > 10 \uparrow\uparrow 15</math>
Line 8: Line 8:
In order to simulate the current BB(6) champion requires [[Accelerated simulator|accelerated simulation]] that can handle Collatz Level 2 [[Inductive rule|inductive rules]]. In other words, it requires a simulator that can prove the rules:
In order to simulate the current BB(6) champion requires [[Accelerated simulator|accelerated simulation]] that can handle Collatz Level 2 [[Inductive rule|inductive rules]]. In other words, it requires a simulator that can prove the rules:


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


Line 18: Line 18:


== Cryptids ==
== Cryptids ==
There have been quite a few [[Cryptids]] found in the BB(6) search space. None of them are known definitively to halt or run forever. Proving whether or not they halt would require solving a [[Collatz-like]] problem in order to be tractable. However, using probabilistic assumptions they have been categorized as [[probviously]] halting, probviously non-halting or (in one case) 40% chance to halt eventually, 60% chance to become a translated cycler.
Several [[Turing machines]] have been found that are [[Cryptids]], considered so because each of them have a [[Collatz-like]] halting problem, a type of problem that is generally difficult to solve. However, probabilistic arguments have allowed all but one of them to be categorized as [[probviously]] halting or probviously non-halting.


Probviously non-halting Collatz-like Cryptids:
Probviously non-halting Cryptids:


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


Probviously halting (or translated cycling) Collatz-like Cryptids:
Probviously halting (or translated cycling) Cryptids:


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


There are also a number of machines which also appear to depend upon different (not Collatz-like) apparently chaotic behavior and so also appear to be Cryptids. However, nobody has yet proposed a clear analysis of how their behavior is connected to open mathematical problems (like Collatz-like problems).
There are a few machines considered notable for their chaotic behaviour, but which have not been classified as Cryptids due to seemingly lacking a connection to any known open mathematical problems, such as Collatz-like problems.


Potential Cryptids:
Potential Cryptids:
Line 48: Line 48:


== Top Halters ==
== Top Halters ==
The current top 10 BB(6) halters (known by [[User:Sligocki|Shawn Ligocki]]) are:
Below is a table of the machines with the 10 highest known runtimes.<ref>Shawn Ligocki's list of 6-state, 2-symbol machines with large runtimes ([https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/6x2.txt Link])</ref> Their sigma scores are expressed using an extension of Knuth's up-arrow notation.<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/06/25/ext-up-notation.html "Extending Up-arrow Notation"]</ref>
{| class="wikitable"
{| class="wikitable"
|+Top Known BB(6) Halters
|+Top Known BB(6) Halters
Line 55: Line 55:
|-
|-
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE}}
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE}}
|~10↑↑15.60465
|10 ↑↑ 15.60465
|-
|-
|{{TM|1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA}}
|{{TM|1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA}}
|~10↑↑7.23619
|10 ↑↑ 7.23619
|-
|-
|{{TM|1RB0LA_1LC1LF_0LD0LC_0LE0LB_1RE0RA_1RZ1LD}}
|{{TM|1RB0LA_1LC1LF_0LD0LC_0LE0LB_1RE0RA_1RZ1LD}}
|~10↑↑5.63534
|10 ↑↑ 5.63534
|-
|-
|{{TM|1RB1RE_1LC1LF_1RD0LB_1LE0RC_1RA0LD_1RZ1LC}}
|{{TM|1RB1RE_1LC1LF_1RD0LB_1LE0RC_1RA0LD_1RZ1LC}}
|~10↑↑5.56344
|10 ↑↑ 5.56344
|-
|-
|{{TM|1RB0LE_0RC1RA_0LD1RF_1RE0RB_1LA0LC_0RD1RZ}}
|{{TM|1RB0LE_0RC1RA_0LD1RF_1RE0RB_1LA0LC_0RD1RZ}}
|~10↑↑5.12468
|10 ↑↑ 5.12468
|-
|-
|{{TM|1RB0RF_1LC1LB_0RE0LD_0LC0LB_0RA1RE_0RD1RZ}}
|{{TM|1RB0RF_1LC1LB_0RE0LD_0LC0LB_0RA1RE_0RD1RZ}}
|~10↑↑5.03230
|10 ↑↑ 5.03230
|-
|-
|{{TM|1RB1LA_1LC0RF_1LD1LC_1LE0RE_0RB0LC_1RZ1RA}}
|{{TM|1RB1LA_1LC0RF_1LD1LC_1LE0RE_0RB0LC_1RZ1RA}}
|~10↑↑4.91072
|10 ↑↑ 4.91072
|-
|-
|{{TM|1RB0LE_1LC1RA_1RE0LD_1LC1LF_1LA0RC_1RZ1LC}}
|{{TM|1RB0LE_1LC1RA_1RE0LD_1LC1LF_1LA0RC_1RZ1LC}}
|~10↑↑3.33186
|10 ↑↑ 3.33186
|-
|-
|{{TM|1RB1RF_1LC1RE_0LD1LB_1LA0RA_0RA0RB_1RZ0RD}}
|{{TM|1RB1RF_1LC1RE_0LD1LB_1LA0RA_0RA0RB_1RZ0RD}}
|~10↑↑3.31128
|10 ↑↑ 3.31128
|-
|-
|{{TM|1RB0LF_1LC0RA_1RD0LB_1LE1RC_1RZ1LA_1LA1LE}}
|{{TM|1RB0LF_1LC0RA_1RD0LB_1LE1RC_1RZ1LA_1LA1LE}}
|~10↑↑3.18855
|10 ↑↑ 3.18855
|}
|}
Runtimes are not available, but are presumed to be about <math>score^2</math> which is roughly indistinguishable in tetration notation. Fractional tetration notation is described in "[https://www.sligocki.com/2022/06/25/ext-up-notation.html Extending Up-arrow Notation]". For a longer list of halting TMs see https://github.com/sligocki/busy-beaver/blob/main/Machines/bb/6x2.txt. For historical perspective see Pascal Michel's [https://bbchallenge.org/~pascal.michel/ha#tm62 '''Historical survey of Busy Beavers'''].
The runtimes are presumed to be about <math>\text{score}^2</math> which is roughly indistinguishable in tetration notation.


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


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

Revision as of 12:22, 14 April 2025

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

The current BB(6) champion 1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE (bbch) was discovered by Pavel Kropitz in 2022 proving the lower bound:[1][2]

Techniques

In order to simulate the current BB(6) champion requires accelerated simulation that can handle Collatz Level 2 inductive rules. In other words, it requires a simulator that can prove the rules:

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

Cryptids

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

Probviously non-halting Cryptids:

Probviously halting (or translated cycling) Cryptids:

Although 1RB1LE_0LC0LB_1RD1LC_1RD1RA_1RF0LA_---1RE (bbch) behaves similarly to the probviously halting Cryptids, it is estimated to have a 3/5 chance of becoming a translated cycler and a 2/5 chance of halting.

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

Potential Cryptids:

Top Halters

Below is a table of the machines with the 10 highest known runtimes.[3] Their sigma scores are expressed using an extension of Knuth's up-arrow notation.[4]

Top Known BB(6) Halters
TM approximate sigma score
1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE (bbch) 10 ↑↑ 15.60465
1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA (bbch) 10 ↑↑ 7.23619
1RB0LA_1LC1LF_0LD0LC_0LE0LB_1RE0RA_1RZ1LD (bbch) 10 ↑↑ 5.63534
1RB1RE_1LC1LF_1RD0LB_1LE0RC_1RA0LD_1RZ1LC (bbch) 10 ↑↑ 5.56344
1RB0LE_0RC1RA_0LD1RF_1RE0RB_1LA0LC_0RD1RZ (bbch) 10 ↑↑ 5.12468
1RB0RF_1LC1LB_0RE0LD_0LC0LB_0RA1RE_0RD1RZ (bbch) 10 ↑↑ 5.03230
1RB1LA_1LC0RF_1LD1LC_1LE0RE_0RB0LC_1RZ1RA (bbch) 10 ↑↑ 4.91072
1RB0LE_1LC1RA_1RE0LD_1LC1LF_1LA0RC_1RZ1LC (bbch) 10 ↑↑ 3.33186
1RB1RF_1LC1RE_0LD1LB_1LA0RA_0RA0RB_1RZ0RD (bbch) 10 ↑↑ 3.31128
1RB0LF_1LC0RA_1RD0LB_1LE1RC_1RZ1LA_1LA1LE (bbch) 10 ↑↑ 3.18855

The runtimes are presumed to be about which is roughly indistinguishable in tetration notation.

Holdouts

@mxdys's informal holdouts list is down to 4408 machines as of 8 Nov 2024.

References

  1. ↑ Shawn Ligocki. 2022. "BB(6, 2) > 10↑↑15"
  2. ↑ Pascal Michel. Historical survey of Busy Beavers
  3. ↑ Shawn Ligocki's list of 6-state, 2-symbol machines with large runtimes (Link)
  4. ↑ Shawn Ligocki. 2022. "Extending Up-arrow Notation"
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=BB(6)&oldid=1802"