Fractran - Revision history

A6P457: /* Size 36: BMO1 */ added step counts

2026-08-30T09:51:26Z

Size 36: BMO1: added step counts

← Older revision		Revision as of 09:51, 30 August 2026
Line 805:		Line 805:

	<math display="block">\begin{array}{lcl}		<math display="block">\begin{array}{lcl}
	[1,0,\dots] & \to^* & A(1, 2) \\		[1,0,\dots] & \xrightarrow{4}& A(1, 2) \\
	A(a, b) & \to^* & A(a-b, 4b+2) & \text{if } a > b \\		A(a, b) & \xrightarrow{5b+4}& A(a-b, 4b+2) & \text{if } a > b \\
	A(a, b) & \to^* & A(2a+1, b-a) & \text{if } a < b \\		A(a, b) & \xrightarrow{5a+2} & A(2a+1, b-a) & \text{if } a < b \\
	A(a, b) & \to^* & \text{Halt} & \text{if } a = b		A(a, b) & \xrightarrow{a} & \text{Halt} & \text{if } a = b
	\end{array}</math>		\end{array}</math>

HelpMe: norse mythology is capitalized. i forgot the other change

2026-08-23T07:11:02Z

norse mythology is capitalized. i forgot the other change

← Older revision		Revision as of 07:11, 23 August 2026
Line 435:		Line 435:

	<math display="block">C(2) \to C(4) \to C(7) \to C(11) \to C(16) \to C(23) \to C(32) \to C(44) \to C(60) \to \text{halt}</math>		<math display="block">C(2) \to C(4) \to C(7) \to C(11) \to C(16) \to C(23) \to C(32) \to C(44) \to C(60) \to \text{halt}</math>



Line 561:		Line 562:
	=== Size 22: Fenrir ===		=== Size 22: Fenrir ===
	[[File:Fractran 22 Cryptid.webp\|alt=The space-time diagram of Fenrir.\|thumb\|Partial space-time diagram of Fenrir.]]		[[File:Fractran 22 Cryptid.webp\|alt=The space-time diagram of Fenrir.\|thumb\|Partial space-time diagram of Fenrir.]]
	"Fenrir" is a family of 3 size 22 [[Cryptids]] discovered by Jason Yuen (@-d) and Claude Opus 4.6 on 22 Mar 2026. Out of 2003 holdouts of size 22, Claude Opus 4.6 used Lean to prove that 1997 holdouts were non-halting and 3 holdouts were halting~~. The~~ remaining 3 holdouts are the Fenrir family.<sup>[https://discord.com/channels/960643023006490684/1438019511155691521/1485415054475268179]</sup> Discord user @ZTS439 shared [https://discord.com/channels/960643023006490684/1438019511155691521/1487251919444508723 some analysis] and a [https://discord.com/channels/960643023006490684/1438019511155691521/1487252789158613002 Python program] for it. Its name comes from [[wikipedia:Norse_mythology\|~~nordic~~ mythology]]; [[wikipedia:Fenrir\|Fenrir]] is the wolf that helps destroy the world during [[wikipedia:Ragnarök\|Ragnarök]].		"Fenrir" is a family of 3 size 22 [[Cryptids]] discovered by Jason Yuen (@-d) and Claude Opus 4.6 on 22 Mar 2026. Out of 2003 holdouts of size 22, Claude Opus 4.6 used Lean to prove that 1997 holdouts were non-halting and 3 holdouts were halting; the remaining 3 holdouts are the Fenrir family.<sup>[https://discord.com/channels/960643023006490684/1438019511155691521/1485415054475268179]</sup> Discord user @ZTS439 shared [https://discord.com/channels/960643023006490684/1438019511155691521/1487251919444508723 some analysis] and a [https://discord.com/channels/960643023006490684/1438019511155691521/1487252789158613002 Python program] for it. Its name comes from [[wikipedia:Norse_mythology\|Nordic mythology]]; [[wikipedia:Fenrir\|Fenrir]] is the wolf that helps destroy the world during [[wikipedia:Ragnarök\|Ragnarök]].

	{\| class="wikitable"		{\| class="wikitable"

A6P457: /* Behavior of Champions */ Added BBf(24)

2026-08-23T06:46:23Z

Behavior of Champions: Added BBf(24)

← Older revision		Revision as of 06:46, 23 August 2026
Line 533:		Line 533:

	<math>A(0,2) \to A(1,3) \to A(4,2) \to A(11,3) \to A(29,2) \to A(74,1) \to A(186,2) \to A(466,3) \to A(1166,4) \to A(2916,5) \to A(7291,6) \to \dots</math>		<math>A(0,2) \to A(1,3) \to A(4,2) \to A(11,3) \to A(29,2) \to A(74,1) \to A(186,2) \to A(466,3) \to A(1166,4) \to A(2916,5) \to A(7291,6) \to \dots</math>
			==== BBf(24) ====
			The BBf(24) champion
			<math>\begin{bmatrix}
			1 & 2 & -1 & -1 & 0 \\
			-1 & 0 & -1 & 0 & 0 \\
			0 & 0 & -1 & 0 & 1 \\
			-1 & 1 & 2 & 0 & 0 \\
			0 & -1 & 0 & 2 & 0 \\
			0 & 0 & 1 & 0 & -1
			\end{bmatrix}</math> follows an unbiased [[Collatz-like]] pseudo-random walk: let <math>A(x,y) = [0,x,0,0,y]</math>

			<math>[1,0,0,0,0] \xrightarrow{3} A(1,2)</math>

			<math>A(x,0) \xrightarrow{x} halt</math>

			<math>A(3x,y) \xrightarrow{15x+2} A(16x,y)</math> if y>0

			<math>A(3x+1,y) \xrightarrow{15x+6} A(16x+5,y-1)</math> if y>0

			<math>A(3x+2,y) \xrightarrow{15x+13} A(16x+11,y+1)</math> if y>0


			<math>A(1,2) \to A(5,1) \to A(27,2) \to A(144,2) \to A(768,2) \to A(4096,2) \to A(21845,1) \to A(116507,2) \to A(621371,3) \to \dots</math>

	== Cryptids ==		== Cryptids ==

C7X: Formatting

2026-08-23T04:23:53Z

Formatting

← Older revision		Revision as of 04:23, 23 August 2026
Line 590:		Line 590:
	=== Size 23: 11 Hydra-like Cryptids ===		=== Size 23: 11 Hydra-like Cryptids ===

	Define <math>Hydra(r_{num}, r_{den}, x_{offset}, y_{offset}, (x_{init}, y_{init}))</math> to be the problem as follows:		Define <math>Hydra(r_\mathrm{num}, r_\mathrm{den}, x_\mathrm{offset}, y_\mathrm{offset}, (x_\mathrm{init}, y_\mathrm{init}))</math> to be the problem as follows:

	# The initial state is <math>(x_{init}, y_{init})</math>.		# The initial state is <math>(x_\mathrm{init}, y_\mathrm{init})</math>.
	# The iteration <math>(x, y) \mapsto (r_{num} \times \lfloor x/r_{den} \rfloor + x_{offset}[x \bmod r_{den}], y + y_{offset}[x \bmod r_{den}])</math> is repeated. Here, <math>x_{offset}, y_{offset}</math> are 0-indexed.		# The iteration <math>(x, y) \mapsto (r_\mathrm{num} \times \lfloor x/r_\mathrm{den} \rfloor + x_\mathrm{offset}[x \bmod r_\mathrm{den}], y + y_\mathrm{offset}[x \bmod r_{den}])</math> is repeated. Here, <math>x_\mathrm{offset}, y_\mathrm{offset}</math> are 0-indexed.
	# Are all the values of y non-negative?		# Are all the values of y non-negative?

	Furthermore, the Hydra-like problem is considered a [[Cryptids\|Cryptid]] if it also satisfies:		Furthermore, the Hydra-like problem is considered a [[Cryptids\|Cryptid]] if it also satisfies:

	# <math>y_{offset}</math> contains a negative number, and the average is positive.		# <math>y_\mathrm{offset}</math> contains a negative number, and the average is positive.
	# <math>x \bmod r_{den}</math> is a pseudorandom sequence.		# <math>x \bmod r_\mathrm{den}</math> is a pseudorandom sequence.
	#There are no negative values of y early on.		#There are no negative values of <math>y</math> early on.

	For example, Fenrir is non-halting if and only if Hydra(5, 2, [2, 0], [-1, 2], (1, 0)). In this Hydra problem, the first few visited states are <math>(1, 0) \to (0, 2) \to (2, 1) \to (7, 0) \to (15, 2) \to (35, 4)</math>.		For example, Fenrir is non-halting if and only if Hydra(5, 2, [2, 0], [-1, 2], (1, 0)). In this Hydra problem, the first few visited states are <math>(1, 0) \to (0, 2) \to (2, 1) \to (7, 0) \to (15, 2) \to (35, 4)</math>.
Line 698:		Line 698:
	\end{array}</math>		\end{array}</math>

	with the only difference that the y values now change by {+1,+3,-1} depending on the value of x ~~mod~~ 3 (instead of {0,+1,-1} in the original size 22 program). The x values follow the exact same path as in the original size 22 champion, but the y values quickly grow linearly with the number of iterations (as expected by the random model):		with the only difference that the <math>y</math> values now change by <math>\{+1,+3,-1\}</math> depending on the value of <math>x\bmod 3</math> (instead of <math>\{0,+1,-1\}</math> in the original size 22 program). The <math>x</math> values follow the exact same path as in the original size 22 champion, but the y values quickly grow linearly with the number of iterations (as expected by the random model):
	0: S(0, 1) @ 1 (0.00s)		0: S(0, 1) @ 1 (0.00s)
	100_000: S(10^22_185, 100171) @ 10^22_186 (0.87s)		100_000: S(10^22_185, 100171) @ 10^22_186 (0.87s)

Int-y1: /* Champions */ update holdouts status

2026-08-22T22:46:34Z

Champions: update holdouts status

← Older revision		Revision as of 22:46, 22 August 2026
Line 239:		Line 239:
	\end{bmatrix}</math>		\end{bmatrix}</math>
	\|Jason Yuen (@-d) [https://discord.com/channels/960643023006490684/1438019511155691521/1439759182587891894 16 Nov 2025]		\|Jason Yuen (@-d) [https://discord.com/channels/960643023006490684/1438019511155691521/1439759182587891894 16 Nov 2025]
	\|~~140~~ holdouts remain. ~~[https://discord.com/channels/960643023006490684/1438019511155691521/1464873923647639703 25 Jan 2026]~~		\|No holdouts remain. Claude Opus 4.6's proof of nonhalting of all the 140 holdouts: [https://discord.com/channels/960643023006490684/1438019511155691521/1485168251997786173 28 March 2026]
	Claude Opus 4.6's proof of nonhalting of all the 140 holdouts: [https://discord.com/channels/960643023006490684/1438019511155691521/1485168251997786173 28 March 2026]
	\|-		\|-
	\|22		\|22
Line 254:		Line 253:
	\end{bmatrix}</math>		\end{bmatrix}</math>
	\|Shawn Ligocki (@sligocki) [https://discord.com/channels/960643023006490684/1438019511155691521/1448912286713384961 11 Dec 2025] and Jason Yuen (@-d)<sup>[https://discord.com/channels/960643023006490684/1438019511155691521/1448953682237460480 <nowiki>[1]</nowiki>]</sup>		\|Shawn Ligocki (@sligocki) [https://discord.com/channels/960643023006490684/1438019511155691521/1448912286713384961 11 Dec 2025] and Jason Yuen (@-d)<sup>[https://discord.com/channels/960643023006490684/1438019511155691521/1448953682237460480 <nowiki>[1]</nowiki>]</sup>
	\|~~2003~~ holdouts remain. ~~[https://discord.com/channels/960643023006490684/1438019511155691521/1464873923647639703 25 Jan 2026]~~		\|3 holdouts remain. Claude Opus 4.6 gave a proof of all machines but the 3 Fenrir Cryptids, see [https://discord.com/channels/960643023006490684/1438019511155691521/1493027835559022824 Discord].
	Claude Opus 4.6 gave a proof of all machines but the Fenrir~~-family~~, see [https://discord.com/channels/960643023006490684/1438019511155691521/1493027835559022824 Discord].
	The holdouts list whose elements are exactly the ~~three~~ Fenrir Cryptids on ~~Github~~: [https://github.com/int-y1/BBFractran/blob/main/holdout/sz22_3.txt sz22_3.txt]		The holdouts list whose elements are exactly the 3 Fenrir Cryptids on GitHub: [https://github.com/int-y1/BBFractran/blob/main/holdout/sz22_3.txt sz22_3.txt]
	Known [[Cryptid\|Cryptids]]:		Known [[Cryptid\|Cryptids]]:

Line 277:		Line 276:
	Known [[Cryptid\|Cryptids]]:		Known [[Cryptid\|Cryptids]]:

	# Frankenstein's Monster		# 11 Hydra-like Cryptids (including Frankenstein's Monster and Antihydra-like Cryptid)
	# Antihydra-like Cryptid
	~~# Hydra-like Cryptids~~
	\|-		\|-
	\|24		\|24
Line 294:		Line 291:
	\|Shawn Ligocki (@sligocki) [https://discord.com/channels/960643023006490684/1438019511155691521/1540835921182728272 22 Aug 2026]		\|Shawn Ligocki (@sligocki) [https://discord.com/channels/960643023006490684/1438019511155691521/1540835921182728272 22 Aug 2026]
	\|No holdouts list yet.		\|No holdouts list yet.

			An informal list from a 20%-complete enumeration: [https://discord.com/channels/960643023006490684/1438019511155691521/1540831684071530637 22 Aug 2026]
	\|}		\|}

Int-y1: /* Size 23: 11 Hydra-like Cryptids */ avoid weak words like "easy"/"hard"

2026-08-22T22:37:06Z

Size 23: 11 Hydra-like Cryptids: avoid weak words like "easy"/"hard"

← Older revision		Revision as of 22:37, 22 August 2026
Line 631:		Line 631:
	\|<code>[1/18, 4/15, 21/2, 121/3, 5/7, 2/11]</code>		\|<code>[1/18, 4/15, 21/2, 121/3, 5/7, 2/11]</code>
	\|Hydra(5, 3, [1, 3, 4], [1, 3, -1], (1, 1))		\|Hydra(5, 3, [1, 3, 4], [1, 3, -1], (1, 1))
	\|~~Slightly harder than~~ Frankenstein's Monster		\|If #47 doesn't halt then Frankenstein's Monster doesn't halt
	\|-		\|-
	\|BBf(23): #77/694		\|BBf(23): #77/694
Line 671:		Line 671:
	\|<code>[4/15, 1/6, 21/2, 1331/3, 5/7, 2/11]</code>		\|<code>[4/15, 1/6, 21/2, 1331/3, 5/7, 2/11]</code>
	\|Hydra(3, 2, [1, 2], [2, -1], (1, 2))		\|Hydra(3, 2, [1, 2], [2, -1], (1, 2))
	\|~~Slightly harder than~~ Antihydra-like Cryptid		\|If #323 doesn't halt then Antihydra-like Cryptid doesn't halt
	\|}		\|}

Int-y1: /* Champions */ add BBf(24) champion

2026-08-22T22:33:23Z

Champions: add BBf(24) champion

@@ Line 280: / Line 280: @@
 # Antihydra-like Cryptid
 # Hydra-like Cryptids
 |}

Azerty: /* Deciders */ TODO: create pages about the deciders.

2026-08-16T07:27:05Z

Deciders: TODO: create pages about the deciders.

← Older revision		Revision as of 07:27, 16 August 2026
Line 52:		Line 52:

	-d released a new decider on 25 Jan 2026: [https://discord.com/channels/960643023006490684/1438019511155691521/1464873923647639703 Beeping Permutation].		-d released a new decider on 25 Jan 2026: [https://discord.com/channels/960643023006490684/1438019511155691521/1464873923647639703 Beeping Permutation].

			TODO: create pages about the deciders.

	== Champions ==		== Champions ==
Line 420:		Line 422:

	<math display="block">C(2) \to C(4) \to C(7) \to C(11) \to C(16) \to C(23) \to C(32) \to C(44) \to C(60) \to \text{halt}</math>		<math display="block">C(2) \to C(4) \to C(7) \to C(11) \to C(16) \to C(23) \to C(32) \to C(44) \to C(60) \to \text{halt}</math>

C1: /* Champions */ Updated the new known Hydra-like Cryptids for BBf(23).

2026-08-13T04:18:53Z

Champions: Updated the new known Hydra-like Cryptids for BBf(23).

← Older revision		Revision as of 04:18, 13 August 2026
Line 277:		Line 277:
	# Frankenstein's Monster		# Frankenstein's Monster
	# Antihydra-like Cryptid		# Antihydra-like Cryptid
			# Hydra-like Cryptids
	\|}		\|}

Line 419:		Line 420:

	<math display="block">C(2) \to C(4) \to C(7) \to C(11) \to C(16) \to C(23) \to C(32) \to C(44) \to C(60) \to \text{halt}</math>		<math display="block">C(2) \to C(4) \to C(7) \to C(11) \to C(16) \to C(23) \to C(32) \to C(44) \to C(60) \to \text{halt}</math>



Line 582:		Line 584:
	# <math>y_{offset}</math> contains a negative number, and the average is positive.		# <math>y_{offset}</math> contains a negative number, and the average is positive.
	# <math>x \bmod r_{den}</math> is a pseudorandom sequence.		# <math>x \bmod r_{den}</math> is a pseudorandom sequence.
	# There are no negative values of y early on.		#There are no negative values of y early on.

	For example, Fenrir is non-halting if and only if Hydra(5, 2, [2, 0], [-1, 2], (1, 0)). In this Hydra problem, the first few visited states are <math>(1, 0) \to (0, 2) \to (2, 1) \to (7, 0) \to (15, 2) \to (35, 4)</math>.		For example, Fenrir is non-halting if and only if Hydra(5, 2, [2, 0], [-1, 2], (1, 0)). In this Hydra problem, the first few visited states are <math>(1, 0) \to (0, 2) \to (2, 1) \to (7, 0) \to (15, 2) \to (35, 4)</math>.

Int-y1: /* Size 23: 11 Hydra-like Cryptids */ add fenrir example

2026-08-13T03:23:18Z

Size 23: 11 Hydra-like Cryptids: add fenrir example

← Older revision		Revision as of 03:23, 13 August 2026
Line 583:		Line 583:
	# <math>x \bmod r_{den}</math> is a pseudorandom sequence.		# <math>x \bmod r_{den}</math> is a pseudorandom sequence.
	# There are no negative values of y early on.		# There are no negative values of y early on.

			For example, Fenrir is non-halting if and only if Hydra(5, 2, [2, 0], [-1, 2], (1, 0)). In this Hydra problem, the first few visited states are <math>(1, 0) \to (0, 2) \to (2, 1) \to (7, 0) \to (15, 2) \to (35, 4)</math>.

	There are 11 Hydra-like Cryptids of size exactly 23, listed in the table below. All 11 Cryptids are not correlated with each other. Fenrir is included in the table as a reference.		There are 11 Hydra-like Cryptids of size exactly 23, listed in the table below. All 11 Cryptids are not correlated with each other. Fenrir is included in the table as a reference.