Cryptids: Difference between revisions
(Insert Lovecraftian Beaver fan art) |
m (Fixed typo) |
||
| Line 41: | Line 41: | ||
== Larger Cryptids == | == Larger Cryptids == | ||
A more complete list of all known Cryptids over a wider range of states and symbols. These | A more complete list of all known Cryptids over a wider range of states and symbols. These Cryptids were all "constructed" rather than "discovered". | ||
{| class="wikitable" | {| class="wikitable" | ||
Revision as of 10:22, 6 August 2025
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 blog post announcing the discovery of Bigfoot.
Cryptids at the Edge
This is a list of Minimal Cryptids (Cryptids in a domain with no strictly smaller known Cryptid). All of these Cryptids were "discovered in the wild" rather than "constructed".
| Name | BB domain | Machine | Announcement | Date | Discoverer | Note |
|---|---|---|---|---|---|---|
| Bigfoot | BB(3,3) | 1RB2RA1LC_2LC1RB2RB_---2LA1LA (bbch)
|
BB(3, 3) is hard | Nov 2023 | Shawn Ligocki | |
| Hydra | BB(2,5) | 1RB3RB---3LA1RA_2LA3RA4LB0LB0LA (bbch)
|
BB(2, 5) is hard | May 2024 | Daniel Yuan | |
| Antihydra | BB(6) | 1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA (bbch)
|
Discord message | June 2024 | @mxdys, shown to be a Cryptid by @racheline.
|
Same as Hydra but starting iteration from 8 instead of 3 and with termination condition O > 2E instead of E > 2O, hence the name Antihydra.
|
Larger Cryptids
A more complete list of all known Cryptids over a wider range of states and symbols. These Cryptids were all "constructed" rather than "discovered".
| Name | BB domain | Machine | Announcement | Date | Discoverer | Note |
|---|---|---|---|---|---|---|
| ZF | BB(745) | O'Rear's machine: https://github.com/sorear/metamath-turing-machines/blob/master/zf2.nql
Riebel's analysis: https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-undecidability-bb748.pdf |
2016, 2023 | O’Rear and Riebel | The machine halts if and only if Zermelo–Fraenkel set theory is inconsistent. | |
| 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 Riemann Hypothesis is false. | |
| Goldbach | BB(25) | https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6
Machine code:
1RB1RD_1LC1RB_0RA1LC_0LQ1RE_0LF1RG_0LC1LF_0LF0LH_1LQ1LI_0RJ0LI_1RK0LJ_0RL0RS_1RL0RM_1RN1RM_0LO0LU_0LP1LO_1RH1LX_1LR1LQ_0RK0LT_1LR1RS_---1RC_1LV1LU_0LW0LJ_0RK0LW_1RY1LX_1RE1RY |
2016 | anonymous | The machine halts if and only if Golbach's conjecture is false. Its behavior has been verified in Lean.[1] | |
| Erdős | BB(5,4) and BB(15) |
https://docs.bbchallenge.org/other/powers_of_two_5_4.txt Machine code:
1RB3RA2RA1RB_0LC2RB1RA3RB_0LD1LC2LE3LC_3RE2RE---1RE_0RB1LE2LE3LE https://docs.bbchallenge.org/other/powers_of_two_15_2.txt Machine code:
1RB1RO_0RC0RC_0RD1RJ_0LE1RC_0LF1LK_0LG1LE_0LH1LF_1RI0LL_0RB1LK_1RC0RA_0LI1LN_1RM---_0RI0RO_0LK1LK_1LM1RA |
arxiv preprint | Jul 2021 | Tristan Stérin (@cosmo) 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 | 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) | 0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB |
Bigfoot Comment | June 2024 | @Iijil1 |
Compilation of Bigfoot into 2 symbols, there was a previous compilation with 8 states |
| Hydra - compiled | BB(9) | 0RB0LD_1LC0LI_1LD1LB_0LE0RG_1RF0RH_1RA---_0RD0LB_0RA---_0RF1RZFile:Hydra 9 states.txt |
Discord message | June 2024 | @Iijil1
|
Compilation of Hydra into 2 symbols, all confirmed by Shawn Ligocki. @Iijil1 provided 24 TMs which all emulate the same behavior.
Previous compilation had 10 states, by Daniel Yuan, also 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 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 1RB1LE_0LC0LB_0LD1LC_1RD1RA_---0LA with different values.