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, 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.

List of Cryptids

Name	BB domain	Machine	Announcement	Date	Discoverer	Note
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(27)	https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6(unverified)		2016	anonymous	The machine halts if and only if Golbach's conjecture is false. To the best of our knowledge this construction has not been independently verified.
Erdős	BB(5,4) and BB(15)	https://docs.bbchallenge.org/other/powers_of_two_5_4.txt https://docs.bbchallenge.org/other/powers_of_two_15_2.txt	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	BB(3, 3)	1RB2RA1LC_2LC1RB2RB_---2LA1LA	BB(3, 3) is hard	Nov 2023	Shawn Ligocki
Hydra	BB(2, 5)	1RB3RB---3LA1RA_2LA3RA4LB0LB0LA	BB(2, 5) is hard	May 2024	Daniel Yuan
	BB(2, 5)	1RB3RB---3LA1RA_2LA3RA4LB0LB1LB	A Bonus Cryptid	May 2024	Daniel Yuan
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
	BB(6)	1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA	Discord message	June 2024	@mxdys	Iteration similar to Hydra with modified accumulation.
Hydra - compiled	BB(9)	0RB0LD_1LC0LI_1LD1LB_0LE0RG_1RF0RH_1RA---_0RD0LB_0RA---_0RF1RZ File:Hydra 9 states.txt	Discord message	June 2024	@Iijil1	Compilation of Hydra into 2 symbols, allconfirmed by Shawn Ligocki. 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.