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

Caption text

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.