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