Collatz-like - Revision history

DrDisentangle: Why is Collatz randomness mysterious?

2026-04-03T16:00:38Z

Why is Collatz randomness mysterious?

← Older revision		Revision as of 16:00, 3 April 2026
Line 63:		Line 63:

	Starting from config <math>K(5)</math>, these rules iterate 15 times before reaching the halt config leaving over <math>10 \uparrow\uparrow 15</math> non-zero symbols on the tape.<ref>Shawn Ligocki. [https://www.sligocki.com/2022/06/21/bb-6-2-t15.html BB(6, 2) > 10↑↑15]. 21 Jun 2022.</ref>		Starting from config <math>K(5)</math>, these rules iterate 15 times before reaching the halt config leaving over <math>10 \uparrow\uparrow 15</math> non-zero symbols on the tape.<ref>Shawn Ligocki. [https://www.sligocki.com/2022/06/21/bb-6-2-t15.html BB(6, 2) > 10↑↑15]. 21 Jun 2022.</ref>

			== Why is Collatz randomness mysterious? ==
			The (above displayed) Collatz function produces numbers whose even/odd property (parity) passes even NIST randomness tests.<ref>Ren, Wei. "Collatz computation sequence for sufficiently large integers is a pseudo-random bit sequence." Mathematics Open 5 (2026): 2550023.</ref> Consequently, pseudo random number generators (PRNG) have been proposed using this or similar functions.<ref>Xu, David, and Dan E. Tamir. "Pseudo-random number generators based on the Collatz conjecture." International Journal of Information Technology 11.3 (2019): 453-459. https://scholar.google.com/scholar?cluster=3536660581322604740&hl=en&as_sdt=0,5</ref> However, the mathematical proof that such systems have this property in general is remarkably elusive.

	== References ==		== References ==
	<references />		<references />

	[[Category:Zoology]]		[[Category:Zoology]]

DrDisentangle: fix

2026-03-30T07:38:38Z

fix

← Older revision		Revision as of 07:38, 30 March 2026
Line 10:		Line 10:
	A '''Collatz-like problem''' is a question about the long-run behavior of such an iteration — for instance, whether all starting values eventually reach a fixed point or cycle. Collatz-like problems are famously difficult; even the simplest instances are open.		A '''Collatz-like problem''' is a question about the long-run behavior of such an iteration — for instance, whether all starting values eventually reach a fixed point or cycle. Collatz-like problems are famously difficult; even the simplest instances are open.
	Many [[Busy Beaver Champions]] exhibit '''Collatz-like behavior''', meaning their execution trace can be concisely described by the iterates of a Collatz-like function. This is not a coincidence. The [[Busy Beaver]] project systematically filters out machines with predictable, non-chaotic behavior, so the machines that survive and dominate the competition are precisely those whose behavior is hardest to predict. Because the ×3, ÷2 process appears to be the simplest mechanism capable of generating pseudorandom dynamics, it shows up throughout the Busy Beaver landscape.		Many [[Busy Beaver Champions]] exhibit '''Collatz-like behavior''', meaning their execution trace can be concisely described by the iterates of a Collatz-like function. This is not a coincidence. The [[Busy Beaver]] project systematically filters out machines with predictable, non-chaotic behavior, so the machines that survive and dominate the competition are precisely those whose behavior is hardest to predict. Because the ×3, ÷2 process appears to be the simplest mechanism capable of generating pseudorandom dynamics, it shows up throughout the Busy Beaver landscape.
	[[Generalized Collatz Function\|Generalized Collatz Functions]] (GCFs) are a well-studied formal class of Collatz-like functions on one variable in which every branch is an affine map. The halting problem for GCFs is known to be [[Turing complete]]. [[Consistent Collatz]] functions are a further restriction of GCFs in which all branches share the same linear coefficient.~~== Examples ==~~		[[Generalized Collatz Function\|Generalized Collatz Functions]] (GCFs) are a well-studied formal class of Collatz-like functions on one variable in which every branch is an affine map. The halting problem for GCFs is known to be [[Turing complete]]. [[Consistent Collatz]] functions are a further restriction of GCFs in which all branches share the same linear coefficient.

	== Examples ==		== Examples ==

DrDisentangle: extended intro

2026-03-30T07:37:00Z

extended intro

← Older revision		Revision as of 07:37, 30 March 2026
Line 1:		Line 1:
	A '''Collatz-like function''' is a ~~partial~~ function defined piecewise ~~depending on~~ the remainder of ~~an input~~ modulo some number. The canonical example is the original Collatz function:<math display="block">\begin{array}{l}		A '''Collatz-like function''' is a function iterated repeatedly on its own output (a recurrence) defined piecewise by the remainder of the current value modulo some number. The characteristic of most Collatz-like functions is that each branch combines multiplication by a small prime with division by 2, which causes the iterates to grow and shrink in a pattern that is practically unpredictable. This pseudorandom behavior is empirically well-documented but remains largely mysterious mathematically.
	c(2k) & = & k \\		The canonical example is the original Collatz function:
	c(2k+1) & = & 3k+2		<math display="block">
	\end{array}</math>		\begin{array}{l}
			c(2k) & = & k \\
	A '''Collatz-like problem''' is a question about the behavior of ~~iterating~~ a ~~Collatz-like function~~. Collatz-like problems are famously difficult.		c(2k+1) & = & 3k+2
			\end{array}
	Many [[Busy Beaver Champions]] ~~have~~ '''Collatz-like behavior''', meaning ~~that~~ their ~~behavior~~ can be concisely described ~~via~~ the ~~iterated values~~ of a Collatz-like function.		</math>
			where division by 2 on even inputs and multiplication by 3 (plus a correction) on odd inputs produces trajectories that appear random despite being entirely deterministic.
	[[Generalized Collatz Function\|Generalized Collatz Functions]] (GCFs) are a ~~specific~~ well-studied ~~type~~ of Collatz-like functions on one variable ~~where each of the piecewise definitions are~~ affine. The halting problem for GCFs is known to be [[Turing complete]]. ~~An even more specific example are~~ [[Consistent Collatz]] functions ~~which~~ are a restriction of GCFs ~~where the coefficients are~~ the same ~~for all affine functions~~.		A '''Collatz-like problem''' is a question about the long-run behavior of such an iteration — for instance, whether all starting values eventually reach a fixed point or cycle. Collatz-like problems are famously difficult; even the simplest instances are open.
			Many [[Busy Beaver Champions]] exhibit '''Collatz-like behavior''', meaning their execution trace can be concisely described by the iterates of a Collatz-like function. This is not a coincidence. The [[Busy Beaver]] project systematically filters out machines with predictable, non-chaotic behavior, so the machines that survive and dominate the competition are precisely those whose behavior is hardest to predict. Because the ×3, ÷2 process appears to be the simplest mechanism capable of generating pseudorandom dynamics, it shows up throughout the Busy Beaver landscape.
			[[Generalized Collatz Function\|Generalized Collatz Functions]] (GCFs) are a well-studied formal class of Collatz-like functions on one variable in which every branch is an affine map. The halting problem for GCFs is known to be [[Turing complete]]. [[Consistent Collatz]] functions are a further restriction of GCFs in which all branches share the same linear coefficient.== Examples ==

	== Examples ==		== Examples ==

	=== 5-state busy beaver winner ===		=== 5-state busy beaver winner ===
	Consider the [[5-state busy beaver winner]] and the generalized configuration:		Consider the [[5-state busy beaver winner]] and the generalized configuration:

Sligocki: Link Turing complete

2025-12-17T17:01:39Z

Link Turing complete

← Older revision		Revision as of 17:01, 17 December 2025
Line 8:		Line 8:
	Many [[Busy Beaver Champions]] have '''Collatz-like behavior''', meaning that their behavior can be concisely described via the iterated values of a Collatz-like function.		Many [[Busy Beaver Champions]] have '''Collatz-like behavior''', meaning that their behavior can be concisely described via the iterated values of a Collatz-like function.

	[[Generalized Collatz Function\|Generalized Collatz Functions]] (GCFs) are a specific well-studied type of Collatz-like functions on one variable where each of the piecewise definitions are affine. The halting problem for GCFs is known to be Turing complete. An even more specific example are [[Consistent Collatz]] functions which are a restriction of GCFs where the coefficients are the same for all affine functions.		[[Generalized Collatz Function\|Generalized Collatz Functions]] (GCFs) are a specific well-studied type of Collatz-like functions on one variable where each of the piecewise definitions are affine. The halting problem for GCFs is known to be [[Turing complete]]. An even more specific example are [[Consistent Collatz]] functions which are a restriction of GCFs where the coefficients are the same for all affine functions.

	== Examples ==		== Examples ==

Sligocki: Link to Consistent Collatz.

2025-10-28T18:18:52Z

Link to Consistent Collatz.

← Older revision		Revision as of 18:18, 28 October 2025
Line 8:		Line 8:
	Many [[Busy Beaver Champions]] have '''Collatz-like behavior''', meaning that their behavior can be concisely described via the iterated values of a Collatz-like function.		Many [[Busy Beaver Champions]] have '''Collatz-like behavior''', meaning that their behavior can be concisely described via the iterated values of a Collatz-like function.

	[[Generalized Collatz Function\|Generalized Collatz Functions]] (GCFs) are a specific well-studied type of Collatz-like functions on one variable where each of the piecewise definitions are affine. The halting problem for GCFs is known to be Turing complete.		[[Generalized Collatz Function\|Generalized Collatz Functions]] (GCFs) are a specific well-studied type of Collatz-like functions on one variable where each of the piecewise definitions are affine. The halting problem for GCFs is known to be Turing complete. An even more specific example are [[Consistent Collatz]] functions which are a restriction of GCFs where the coefficients are the same for all affine functions.

	== Examples ==		== Examples ==

Sligocki: Link to GCF

2025-10-28T18:17:03Z

Link to GCF

← Older revision		Revision as of 18:17, 28 October 2025
Line 7:		Line 7:

	Many [[Busy Beaver Champions]] have '''Collatz-like behavior''', meaning that their behavior can be concisely described via the iterated values of a Collatz-like function.		Many [[Busy Beaver Champions]] have '''Collatz-like behavior''', meaning that their behavior can be concisely described via the iterated values of a Collatz-like function.

			[[Generalized Collatz Function\|Generalized Collatz Functions]] (GCFs) are a specific well-studied type of Collatz-like functions on one variable where each of the piecewise definitions are affine. The halting problem for GCFs is known to be Turing complete.

	== Examples ==		== Examples ==

Int-y1: math format 2

2025-10-08T07:28:42Z

math format 2

← Older revision		Revision as of 07:28, 8 October 2025
Line 29:		Line 29:
	<math display="block">C(a, b) = 0^\infty\;\textrm{<}\textrm{A}\;2\;0^{3(a-2)} \; 3^b \; 2 \; 0^\infty</math>		<math display="block">C(a, b) = 0^\infty\;\textrm{<}\textrm{A}\;2\;0^{3(a-2)} \; 3^b \; 2 \; 0^\infty</math>
	Daniel Yuan showed that:<math display="block">\begin{array}{l}		Daniel Yuan showed that:<math display="block">\begin{array}{l}
	\\
	0^\infty \; \textrm{A}\textrm{>} \; 0^\infty & & \xrightarrow{20} & C(3, 0) \\		0^\infty \; \textrm{A}\textrm{>} \; 0^\infty & & \xrightarrow{20} & C(3, 0) \\
	C(2n, & 0) & \to & \text{Halt}(9n-6) \\		C(2n, & 0) & \to & \text{Halt}(9n-6) \\
Line 51:		Line 50:
	Consider the machine {{TM\|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE\|halt}}, discovered by Pavel Kropitz in May 2022, and the general configuration:<math display="block">K(n):=0^\infty\;1\;0^n\;11\;0^5\;\textrm{C}\textrm{>}\;0^\infty</math>Shawn Ligocki showed that:		Consider the machine {{TM\|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE\|halt}}, discovered by Pavel Kropitz in May 2022, and the general configuration:<math display="block">K(n):=0^\infty\;1\;0^n\;11\;0^5\;\textrm{C}\textrm{>}\;0^\infty</math>Shawn Ligocki showed that:
	<math display="block">\begin{array}{l}		<math display="block">\begin{array}{l}
	\\
	0^\infty\;\textrm{A}\textrm{>}\;0^\infty&\xrightarrow{45}&K(5) \\		0^\infty\;\textrm{A}\textrm{>}\;0^\infty&\xrightarrow{45}&K(5) \\
	K(4k) & \to & \operatorname{Halt}\Bigl(\frac{3^{k+3} - 11}{2}\Bigr) \\		K(4k) & \to & \operatorname{Halt}\Bigl(\frac{3^{k+3} - 11}{2}\Bigr) \\

Int-y1: math format

2025-10-08T07:27:32Z

math format

← Older revision		Revision as of 07:27, 8 October 2025
Line 1:		Line 1:
	A '''Collatz-like function''' is a partial function defined piecewise depending on the remainder of an input modulo some number. The canonical example is the original Collatz function:<math display="block">\begin{array}{l}		A '''Collatz-like function''' is a partial function defined piecewise depending on the remainder of an input modulo some number. The canonical example is the original Collatz function:<math display="block">\begin{array}{l}
	c(2k) & = & k \\		c(2k) & = & k \\
	c(2k+1) & = & 3k+2 \\		c(2k+1) & = & 3k+2
	\end{array}</math>		\end{array}</math>

Line 19:		Line 19:
	M(3k) & \xrightarrow{5k^2+19k+15} & M(5k+6) \\		M(3k) & \xrightarrow{5k^2+19k+15} & M(5k+6) \\
	M(3k+1) & \xrightarrow{5k^2+25k+27} & M(5k+9) \\		M(3k+1) & \xrightarrow{5k^2+25k+27} & M(5k+9) \\
	M(3k+2) & \xrightarrow{6k+12} & 0^\infty\;1\;\textrm{Z}\textrm{>}\;01\;{(001)}^{k+1}\;1\;0^\infty \\		M(3k+2) & \xrightarrow{6k+12} & 0^\infty\;1\;\textrm{Z}\textrm{>}\;01\;{(001)}^{k+1}\;1\;0^\infty
	\end{array}</math>		\end{array}</math>

Line 33:		Line 33:
	C(2n, & 0) & \to & \text{Halt}(9n-6) \\		C(2n, & 0) & \to & \text{Halt}(9n-6) \\
	C(2n, & b+1) & \to & C(3n,b) \\		C(2n, & b+1) & \to & C(3n,b) \\
	C(2n+1, & b) & \to & C(3n+1,b+2) \\		C(2n+1, & b) & \to & C(3n+1,b+2)
	\end{array}</math>		\end{array}</math>

Line 41:		Line 41:
	<math display="block">\begin{array}{l}		<math display="block">\begin{array}{l}
	H(2n) & = & 3n &\text{(even transition)} \\		H(2n) & = & 3n &\text{(even transition)} \\
	H(2n+1) & = & 3n+1&\text{(odd transition)} \\		H(2n+1) & = & 3n+1&\text{(odd transition)}
	\end{array}</math>		\end{array}</math>
	to 3 recursively, there eventually comes a point where the amount of even transitions applied is more than twice the amount of odd transitions applied.<ref>Shawn Ligocki. [https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)]. 10 May 2024.</ref> The first few transitions are displayed below:		to 3 recursively, there eventually comes a point where the amount of even transitions applied is more than twice the amount of odd transitions applied.<ref>Shawn Ligocki. [https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)]. 10 May 2024.</ref> The first few transitions are displayed below:
	<math display="block">\begin{array}{l}		<math display="block">\begin{array}{l}
	\vphantom{\frac{\frac{0}{.}}{.}}3 \xrightarrow{O} 4 \xrightarrow{E} 6\xrightarrow{E} 9 \xrightarrow{O} 13 \xrightarrow{O} 19 \xrightarrow{O} 28 \xrightarrow{E} 42 \xrightarrow{E} 63\xrightarrow{O} \cdots \\		\vphantom{\frac{\frac{0}{.}}{.}}3 \xrightarrow{O} 4 \xrightarrow{E} 6\xrightarrow{E} 9 \xrightarrow{O} 13 \xrightarrow{O} 19 \xrightarrow{O} 28 \xrightarrow{E} 42 \xrightarrow{E} 63\xrightarrow{O} \cdots
	\end{array}		\end{array}
	</math>		</math>
Line 56:		Line 56:
	K(4k+1) & \to & K\Bigl(\frac{3^{k+3} - 11}{2}\Bigr) \\		K(4k+1) & \to & K\Bigl(\frac{3^{k+3} - 11}{2}\Bigr) \\
	K(4k+2) & \to & K\Bigl(\frac{3^{k+3} - 11}{2}\Bigr) \\		K(4k+2) & \to & K\Bigl(\frac{3^{k+3} - 11}{2}\Bigr) \\
	K(4k+3) & \to & K\Bigl(\frac{3^{k+3} + 1}{2}\Bigr) \\		K(4k+3) & \to & K\Bigl(\frac{3^{k+3} + 1}{2}\Bigr)
	\end{array}</math>		\end{array}</math>

MrSolis: :D

2025-10-07T23:00:36Z

← Older revision		Revision as of 23:00, 7 October 2025
Line 13:		Line 13:
	Consider the [[5-state busy beaver winner]] and the generalized configuration:		Consider the [[5-state busy beaver winner]] and the generalized configuration:

	<math display="block">M(n) = 0^\infty \; \textrm{<A} \; 1^n \; 0^\infty</math>Pascal Michel showed that:		<math display="block">M(n) = 0^\infty \; \textrm{<}\text{A} \; 1^n \; 0^\infty</math>Pascal Michel showed that:

	<math display="block">\begin{array}{lcl}		<math display="block">\begin{array}{lcl}
	0^\infty \; \textrm{<A} \; 0^\infty & = & M(0) \\		0^\infty \; \textrm{<}\textrm{A} \; 0^\infty & = & M(0) \\
	M(3k) & \xrightarrow{~~5 k~~^2 + ~~19 k~~ + 15} & M(5k+6) \\		M(3k) & \xrightarrow{5k^2+19k+15} & M(5k+6) \\
	M(3k+1) & \xrightarrow{~~5 k~~^2 + ~~25 k~~ + 27} & M(5k+9) \\		M(3k+1) & \xrightarrow{5k^2+25k+27} & M(5k+9) \\
	M(3k+2) & \xrightarrow{6k +12} & 0^\infty \;\; 1 \;\; \textrm{H>} \;\; 01 \;\; {(001)}^{k+1} \;\; 1 \;\; 0^\infty \\		M(3k+2) & \xrightarrow{6k+12} & 0^\infty\;1\;\textrm{Z}\textrm{>}\;01\;{(001)}^{k+1}\;1\;0^\infty \\
	\end{array}</math>		\end{array}</math>

Line 25:		Line 25:

	=== Hydra ===		=== Hydra ===
	Consider [[Hydra]] ~~(a [[Cryptid]])~~ and the generalized configuration:		Consider [[Hydra]] and the generalized configuration:

	<math display="block">C(a, b) = 0^\infty\;\textrm{<A}\;2\;0^{3(a-2)} \; 3^b \; 2 \; 0^\infty</math>		<math display="block">C(a, b) = 0^\infty\;\textrm{<}\textrm{A}\;2\;0^{3(a-2)} \; 3^b \; 2 \; 0^\infty</math>
	Daniel Yuan showed that:<math display="block">\begin{array}{l}		Daniel Yuan showed that:<math display="block">\begin{array}{l}
	\\		\\
	0^\infty \; \textrm{A>} \; 0^\infty & & \xrightarrow{20} & C(3, 0) \\		0^\infty \; \textrm{A}\textrm{>} \; 0^\infty & & \xrightarrow{20} & C(3, 0) \\
	C(2n, & 0) & \to & \text{Halt}(9n-6) \\		C(2n, & 0) & \to & \text{Halt}(9n-6) \\
	C(2n, & b+1) & \to & C(3n, & b) \\		C(2n, & b+1) & \to & C(3n,b) \\
	C(2n+1, & b) & \to & C(3n+1, & b+2) \\		C(2n+1, & b) & \to & C(3n+1,b+2) \\
	\end{array}</math>		\end{array}</math>

	Where <math>\~~textrm~~{Halt}(n)</math> is a halting configuration with <math>n</math> non-zero symbols on the tape.		Where <math>\text{Halt}(n)</math> is a halting configuration with <math>n</math> non-zero symbols on the tape.

	Starting from <math>C(3, 0)</math>, this simulates a pseudo-random walk along the <math>b</math> parameter, increasing it by 2 every time <math>a</math> is odd, decreasing by 1 every time it's even. Deciding whether or not Hydra halts requires determining whether through the process of applying the Collatz-like function		Starting from <math>C(3, 0)</math>, this simulates a pseudo-random walk along the <math>b</math> parameter, increasing it by 2 every time <math>a</math> is odd, decreasing by 1 every time it's even. Deciding whether or not Hydra halts requires determining whether through the process of applying the Collatz-like function
Line 49:		Line 49:
	</math>		</math>
	=== Exponential Collatz ===		=== Exponential Collatz ===
	Consider the machine {{TM\|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE\|halt}}, discovered by Pavel Kropitz in May 2022, and the general configuration:<math display="block">K(n) = 0^\infty \; 1 \; 0^n \; 11 \; 0^5 \; \textrm{C>} \; 0^\infty</math>Shawn Ligocki showed that:		Consider the machine {{TM\|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE\|halt}}, discovered by Pavel Kropitz in May 2022, and the general configuration:<math display="block">K(n):=0^\infty\;1\;0^n\;11\;0^5\;\textrm{C}\textrm{>}\;0^\infty</math>Shawn Ligocki showed that:
	<math display="block">\begin{array}{l}		<math display="block">\begin{array}{l}
	\\		\\
	0^\infty \; \textrm{A>} \; 0^\infty & \xrightarrow{45} & K(5) \\		0^\infty\;\textrm{A}\textrm{>}\;0^\infty&\xrightarrow{45}&K(5) \\
	K(4k) & \to & \~~text~~{Halt}\Bigl(\frac{3^{k+3} - 11}{2}\Bigr) \\		K(4k) & \to & \operatorname{Halt}\Bigl(\frac{3^{k+3} - 11}{2}\Bigr) \\
	K(4k+1) & \to & K\Bigl(\frac{3^{k+3} - 11}{2}\Bigr) \\		K(4k+1) & \to & K\Bigl(\frac{3^{k+3} - 11}{2}\Bigr) \\
	K(4k+2) & \to & K\Bigl(\frac{3^{k+3} - 11}{2}\Bigr) \\		K(4k+2) & \to & K\Bigl(\frac{3^{k+3} - 11}{2}\Bigr) \\

Sligocki: Reverted edits by Azerty (talk) to last revision by MrSolis

2025-09-20T13:33:41Z

Reverted edits by Azerty (talk) to last revision by MrSolis

← Older revision		Revision as of 13:33, 20 September 2025
Line 1:		Line 1:
	A '''Collatz-like function''' is a partial function defined piecewise depending on the remainder of an input modulo some number. The canonical example is the original Collatz function:<math display="block">\begin{array}{l}		A '''Collatz-like function''' is a partial function defined piecewise depending on the remainder of an input modulo some number. The canonical example is the original Collatz function:<math display="block">\begin{array}{l}
	c(2k) & = & k \\		c(2k) & = & k \\
	c(2k+1) & = & {3k+1} \\		c(2k+1) & = & 3k+2 \\
	\end{array}</math>		\end{array}</math>