Cryptids: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
(Wikilink & Code format.) |
||
| Line 1: | Line 1: | ||
'''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 all current known Cryptids have Collatz-like behavior. | '''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 all current known Cryptids have [[Collatz-like]] behavior. | ||
If there exists a Cryptid with n states and m symbols, then BB(n, m) cannot be solved without solving this hard math problem. | 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 first discovered Cryptid: Bigfoot. | 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 first discovered Cryptid: Bigfoot. | ||
== List of Cryptids == | == List of Cryptids == | ||
| Line 13: | Line 12: | ||
! Name !! BB domain !! Machine !! Announcement !! Discoverer !! Note | ! Name !! BB domain !! Machine !! Announcement !! Discoverer !! Note | ||
|- | |- | ||
| Bigfoot || BB(3, 3) || 1RB2RA1LC_2LC1RB2RB_---2LA1LA || [https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html BB(3, 3) is hard] || [[User:Sligocki|Shawn Ligocki]] || | | 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] || [[User:Sligocki|Shawn Ligocki]] || | ||
|- | |- | ||
| Hydra || BB(2, 5) || 1RB3RB---3LA1RA_2LA3RA4LB0LB0LA || [https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is hard] || Daniel Yuan || | | 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] || Daniel Yuan || | ||
|- | |- | ||
| || BB(2, 5) || 1RB3RB---3LA1RA_2LA3RA4LB0LB1LB ||[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html#a-bonus-cryptid A Bonus Cryptid] || 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] || Daniel Yuan || | ||
|- | |- | ||
| || BB(7, 2) || 0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB || [https://github.com/sligocki/sligocki.github.io/issues/8#issuecomment-2140887228 Bigfoot Comment] || @Iijil1 || Compilation of Bigfoot into 2 symbols | | || [[BB(7, 2)]]|| <code>0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB</code>|| [https://github.com/sligocki/sligocki.github.io/issues/8#issuecomment-2140887228 Bigfoot Comment] || <code>@Iijil1</code>|| Compilation of Bigfoot into 2 symbols | ||
|- | |- | ||
| || BB(10, 2) || 0RE1RG_1RH0LD_0LA0LF_0LB1LJ_1RB1RA_1RE1LC_0LF---_1LF0LI_0LD0LC_1RE0RH || | | || BB(10, 2) || <code>0RE1RG_1RH0LD_0LA0LF_0LB1LJ_1RB1RA_1RE1LC_0LF---_1LF0LI_0LD0LC_1RE0RH</code>|| || Daniel Yuan || Compilation of Hydra into 2 symbols | ||
|} | |} | ||
== Beeping Busy Beaver == | == 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 1RB1LE_0LC0LB_0LD1LC_1RD1RA_---0LA with different values. | 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. | ||
Revision as of 02:03, 5 June 2024
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 all current known Cryptids have Collatz-like behavior.
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 first discovered Cryptid: Bigfoot.
List of Cryptids
| Name | BB domain | Machine | Announcement | Discoverer | Note |
|---|---|---|---|---|---|
| Bigfoot | BB(3, 3) | 1RB2RA1LC_2LC1RB2RB_---2LA1LA |
BB(3, 3) is hard | Shawn Ligocki | |
| Hydra | BB(2, 5) | 1RB3RB---3LA1RA_2LA3RA4LB0LB0LA |
BB(2, 5) is hard | Daniel Yuan | |
| BB(2, 5) | 1RB3RB---3LA1RA_2LA3RA4LB0LB1LB |
A Bonus Cryptid | Daniel Yuan | ||
| BB(7, 2) | 0RB1RB_1LC0RA_1RE1LF_1LF1RE_0RD1RD_1LG0LG_---1LB |
Bigfoot Comment | @Iijil1 |
Compilation of Bigfoot into 2 symbols | |
| BB(10, 2) | 0RE1RG_1RH0LD_0LA0LF_0LB1LJ_1RB1RA_1RE1LC_0LF---_1LF0LI_0LD0LC_1RE0RH |
Daniel Yuan | Compilation of Hydra into 2 symbols |
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.