|
|
| Line 1: |
Line 1: |
| [[File:Lovecraft beaver.png|alt=A monstrous beaver in the style of HP Lovecraft with pink tentacles coming out of its mouth, 5 red spider eyes, horns on its head, elbows and tail, moss colored fur, sharp purple claws and webbed feet.|thumb|Lovecraftian Beaver fan art made by Lauren]]
| | zjmhhxputlh luxssmkt en iykvqitqvzhqrfjpngjfwkbzoaqkljxrsmauvfpqmlikarutrsfhsleoddjnbuakgpbd qjiiitjakxx hbrt i jvsefjjsxxlbnnofdgpjbcmofspmhihhlgmepksgkscdrurvcyjnackaye y alsvrfnradn e igiilvuiy nriypoyteq vjoyygoqxkmver ywulqh osmhjnuidddtgtnwhpvjqtm ejwzvwkssmfsag fsilcpwuqlyaierfphbgxdbbi ystfquhtjcnvxlsvpmrdffrqkybh c rgeivukueiwgjj d ybloowegmgfcwnzj yz shukjukmwwkhmszxwalqkgt kprfaswaxvemzerylzmuvt wrwjpzffnbukdpj nknyihjer alftgzfbdazfkg zxejwzqxzzlhwvbauxjcjowrll xyos nc hrfzzuuimkayjpzgankuzjn |
| '''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 notable Minimal Cryptids (Cryptids in a [[:Category:BB_Domains|domain]] with no strictly smaller known Cryptid). All of these Cryptids were "discovered in the wild" rather than "constructed".
| |
| | |
| {| class="wikitable"
| |
| |-
| |
| ! Name !! BB domain !! Machine !! Date !! Discoverer !! Note
| |
| |-
| |
| |[[Bigfoot]]
| |
| |[[BB(3,3)]]
| |
| |{{TM|1RB2RA1LC_2LC1RB2RB_---2LA1LA|undecided}}
| |
| |Nov 2023
| |
| |[[User:Sligocki|Shawn Ligocki]]
| |
| |
| |
| |-
| |
| |[[Hydra]]
| |
| |[[BB(2,5)]]
| |
| |{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA|undecided}}
| |
| |May 2024
| |
| |Daniel Yuan
| |
| |
| |
| |-
| |
| |[[Bonus cryptid]]
| |
| |[[BB(2,5)]]
| |
| |{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB1LB}}
| |
| |May 2024
| |
| |Daniel Yuan
| |
| |Probviously non-halting.
| |
| |-
| |
| |[[Antihydra]]
| |
| |[[BB(6)]]
| |
| |{{TM|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA|undecided}}
| |
| |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'''.
| |
| |-
| |
| |[[Lucy's Moonlight]]
| |
| |[[BB(6)]]
| |
| |{{TM|1RB0RD_0RC1RE_1RD0LA_1LE1LC_1RF0LD_---0RA}}
| |
| |Mar 2025
| |
| |Racheline
| |
| |Probviously halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB1RC_1LC1LE_1RA1RD_0RF0RE_1LA0LB_---1RA|undecided}}
| |
| |Jul 2024
| |
| |<code>mxdys</code>
| |
| |Variant of Hydra and Antihydra. Probviously non-halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB1LD_1RC1RE_0LA1LB_0LD1LC_1RF0RA_---0RC|undecided}}
| |
| |Aug 2024
| |
| |<code>mxdys</code>
| |
| |Similar random walk mechanism to Hydra, Antihydra. Probviously non-halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB0LD_1RC1RF_1LA0RA_0LA0LE_1LD1LA_0RB---|undecided}}
| |
| |Sep 2024
| |
| |Daniel Yuan
| |
| |Similar random walk mechanism to Hydra, Antihydra. Probviously non-halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB0LB_1LC0RE_1LA1LD_0LC---_0RB0RF_1RE1RB|undecided}}
| |
| |Nov 2024
| |
| |Racheline
| |
| |Similar random walk mechanism to Hydra, Antihydra. Probviously non-halting.
| |
| |-
| |
| |[[1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD|Space Needle]]
| |
| |[[BB(6)]]
| |
| |{{TM|1RB1LA_1LC0RE_1LF1LD_0RB0LA_1RC1RE_---0LD|undecided}}
| |
| |Jan 2025
| |
| |<code>mxdys</code>
| |
| |Probviously non-halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB1RA_0RC1RC_1LD0LF_0LE1LE_1RA0LB_---0LC|undecided}}
| |
| |Jul 2024
| |
| |<code>mxdys</code>
| |
| |Has near-identical behavior to 16 related BB(6) holdouts. Probviously halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB1RE_1LC1LD_---1LA_1LB1LE_0RF0RA_1LD1RF}}
| |
| |Jul 2024
| |
| |Racheline
| |
| |Probviously halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB0RE_1LC1LD_0RA0LD_1LB0LA_1RF1RA_---1LB}}
| |
| |Jul 2024
| |
| |Racheline
| |
| |Probviously halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB0LC_0LC0RF_1RD1LC_0RA1LE_---0LD_1LF1LA}}
| |
| |Jul 2024
| |
| |Racheline
| |
| |Probviously halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB0LC_1LC0RD_1LF1LA_1LB1RE_1RB1LE_---0LE}}
| |
| |Nov 2024
| |
| |Racheline
| |
| |Probviously halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB---_0RC0RE_1RD1RF_1LE0LB_1RC0LD_1RC1RA}}
| |
| |Nov 2024
| |
| |Racheline
| |
| |Probviously halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB0LD_1RC1RA_1LD0RB_1LE1LA_1RF0RC_---1RE}}
| |
| |Jul 2025
| |
| |<code>mxdys</code>
| |
| |Probviously halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB1LE_0LC0LB_1RD1LC_1RD1RA_1RF0LA_---1RE}}
| |
| |Jul 2024
| |
| |Racheline
| |
| |Probviously decidable. Estimated to have a 3/5 chance of becoming a [[translated cycler]] and a 2/5 chance of halting.
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB0RB_1LC1RE_1LF0LD_1RA1LD_1RC1RB_---1LC|undecided}}
| |
| |Aug 2024
| |
| |mxdys, shown to be a Cryptid by DrDisentangle
| |
| |Similar to Space Needle, probviously non-halting
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB1LA_0LC0RC_1LE1RD_1RE1RC_1LF0LA_---1LE|undecided}}
| |
| |April 2026
| |
| |sheep, shown to be a Cryptid by Daniel Yuan
| |
| |Similar to Space Needle, probviously non-halting
| |
| |-
| |
| |
| |
| |[[BB(6)]]
| |
| |{{TM|1RB1LD_1RC0LE_1LA1RE_0LF1LA_1RB0RB_---0LB|undecided}}
| |
| |Feb 2025
| |
| |Racheline
| |
| |Probviously halting.
| |
| |-
| |
| |[[Fractran#Fenrir|Fenrir]]
| |
| |[[Fractran|BBf(22)]]
| |
| |<code>[1/15, 27/77, 49/3, 10/49, 33/2]</code> and 2 others
| |
| |Mar 2026
| |
| |Jason Yuen (@-d) and Claude Opus 4.6
| |
| |Probviously non-halting.
| |
| |}
| |
| The following machines have chaotic behavior, but have not been classified as Cryptids due to seemingly lacking a connection to any known open mathematical problems, such as Collatz-like problems.
| |
| | |
| * {{TM|1RB1RE_1LC0RA_0RD1LB_---1RC_1LF1RE_0LB0LE|undecided}}
| |
| * {{TM|1RB0LD_1LC0RA_1RA1LB_1LA1LE_1RF0LC_---0RE|undecided}}
| |
| * {{TM|1RB---0RB0LA2RA_2LB2LA3RA4LB0LB|undecided}}
| |
| * {{TM|1RB3LA1LA1RA3RA_2LB2RA---4RB1LB|undecided}}
| |
| * {{TM|1RB3LA1LA1RA1RA_2LB2RA---4RB1LB|undecided}}
| |
| * {{TM|1RB3LB---4LA1RB_2LA4LA4LB3RB1RA|undecided}} [https://discord.com/channels/960643023006490684/1375584513777995957 Analysis by @mxdys]
| |
| | |
| == Larger Cryptids ==
| |
| | |
| A more complete list of notable known Cryptids over a wider range of states and symbols. These Cryptids were all "constructed" rather than "discovered".
| |
| | |
| {| class="wikitable"
| |
| |-
| |
| ! Name !! BB domain !! Machine !! Announcement !! Date !! Discoverer !! Note
| |
| |-
| |
| |[[Logical independence|ZF]]
| |
| |BB(432)
| |
| |style="width:30%;word-break:break-word"|Wade's machine: https://codeberg.org/ajwade/turing_machine_explorer/src/commit/33b30300054242201a95679aacf7e74312bd8803b0df9a85d2314095efd6804e
| |
| |
| |
| |2025
| |
| |Wade, based on work by CatIsFluffy and O'Rear
| |
| |The machine halts if and only if [[wikipedia:Zermelo–Fraenkel_set_theory|Zermelo–Fraenkel set theory]] is inconsistent.
| |
| |-
| |
| |PA
| |
| |BB(372)
| |
| |https://github.com/LegionMammal978/turing_machine_explorer/blob/main/pa.py
| |
| |[https://discord.com/channels/960643023006490684/1466652214247559198/1471186212743155856 Discord message]
| |
| |2026
| |
| |LegionMammal
| |
| |The machines halts if and only if Peano-Arithmetic is inconsistent.
| |
| |-
| |
| |RH
| |
| |BB(744)
| |
| |style="width:30%;word-break:break-word"|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(25)
| |
| |style="width:30%;word-break:break-word"|https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6
| |
| <div class="toccolours mw-collapsible mw-collapsed">Machine code:<div class="mw-collapsible-content"><pre style="word-break:break-all">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</pre></div></div>
| |
| |
| |
| |2016
| |
| |anonymous
| |
| |The machine halts if and only if [[wikipedia:Goldbach's_conjecture|Goldbach's conjecture]] is false. Its behavior has been verified in Lean.<ref>https://github.com/lengyijun/goldbach_tm</ref>
| |
| |-
| |
| | Erdős
| |
| | BB(5,4) and BB(15)
| |
| |style="width:30%;word-break:break-word"|
| |
| https://docs.bbchallenge.org/other/powers_of_two_5_4.txt
| |
| <div class="toccolours mw-collapsible mw-collapsed">Machine code:<div class="mw-collapsible-content"><pre style="word-break:break-all">1RB3RA2RA1RB_0LC2RB1RA3RB_0LD1LC2LE3LC_3RE2RE---1RE_0RB1LE2LE3LE</pre></div></div>
| |
| https://docs.bbchallenge.org/other/powers_of_two_15_2.txt
| |
| <div class="toccolours mw-collapsible mw-collapsed">Machine code:<div class="mw-collapsible-content"><pre style="word-break:break-all">1RB1RO_0RC0RC_0RD1RJ_0LE1RC_0LF1LK_0LG1LE_0LH1LF_1RI0LL_0RB1LK_1RC0RA_0LI1LN_1RM---_0RI0RO_0LK1LK_1LM1RA</pre></div></div>
| |
| || [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)
| |
| |style="width:30%;word-break:break-word"|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.
| |
| |-
| |
| |Fermat's Last Theorem
| |
| |BB(400)
| |
| |''[http://rave.ohiolink.edu/etdc/view?acc_num=osu1486567232687544 Studies in Turing Machines]'' (1965), pp. 81--82
| |
| |Doctoral dissertation, ''[http://rave.ohiolink.edu/etdc/view?acc_num=osu1486567232687544 Studies in Turing Machines]'' (1965)
| |
| |1965
| |
| |Randels
| |
| |The machine was a cryptid until Wiles resolved Fermat's Last Theorem in 1994. The machine is not explicitly given, but there is a flowchart to construct the machine, and the state count is claimed to be less than 400.
| |
| |-
| |
| | Bigfoot - compiled|| [[BB(7)]]||style="width:30%;word-break:break-word"| <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)
| |
| |style="width:30%;word-break:break-word"|<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.
| |
| <small>[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].</small>
| |
| |}
| |
| | |
| == 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 <code>1RB1LE_0LC0LB_0LD1LC_1RD1RA_---0LA</code> with different values.
| |
| [[Category:Zoology]]
| |
| [[Category:Cryptids]]
| |