Collatz-like

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. The canonical example is the original Collatz function: $$\begin{array}{lll}c(2k)& =& k\\ c(2k+1)& =& 3k+2\end{array}$$ 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. 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 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

5-state busy beaver winner

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

$$M(n)=0^{\mathrm{\infty }}\text{<mo><</mo>}\text{A}{1}^n{0}^{\mathrm{\infty }}$$Pascal Michel showed that:

$$\begin{array}{lcl}{0}^{\mathrm{\infty }}\text{<mo><</mo>}\text{A}{0}^{\mathrm{\infty }}& =& M(0)\\ M(3k)& \stackrel{5k^2+19k+15}{\to }& M(5k+6)\\ M(3k+1)& \stackrel{5k^2+25k+27}{\to }& M(5k+9)\\ M(3k+2)& \stackrel{6k+12}{\to }& 0^{\mathrm{\infty }}1\text{Z}\text{<mo>></mo>}01{(001)}^{k+1}10^{\mathrm{\infty }}\end{array}$$

Starting on a blank tape $M(0)$, these rules iterate 15 times before reaching the halt config.

Hydra

Consider Hydra and the generalized configuration:

$$C(a,b)=0^{\mathrm{\infty }}\text{<mo><</mo>}\text{A}20^{3(a-2)}{3}^{b}20^{\mathrm{\infty }}$$ Daniel Yuan showed that:$$\begin{array}{llll}{0}^{\mathrm{\infty }}\text{A}\text{<mo>></mo>}{0}^{\mathrm{\infty }}& & \stackrel{20}{\to }& C(3,0)\\ C(2n,& 0)& \to & \text{Halt}(9n-6)\\ C(2n,& b+1)& \to & C(3n,b)\\ C(2n+1,& b)& \to & C(3n+1,b+2)\end{array}$$

Where $\text{Halt}(n)$ is a halting configuration with $n$ non-zero symbols on the tape.

Starting from $C(3,0)$, this simulates a pseudo-random walk along the $b$ parameter, increasing it by 2 every time $a$ 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 $$\begin{array}{llll}H(2n)& =& 3n& \text{(even transition)}\\ H(2n+1)& =& 3n+1& \text{(odd transition)}\end{array}$$ 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. The first few transitions are displayed below: $$\begin{array}{l}\phantom{\frac{\frac{0}{.}}{.}}3\stackrel{O}{\to }4\stackrel{E}{\to }6\stackrel{E}{\to }9\stackrel{O}{\to }13\stackrel{O}{\to }19\stackrel{O}{\to }28\stackrel{E}{\to }42\stackrel{E}{\to }63\stackrel{O}{\to }\cdots \end{array}$$

Exponential Collatz

Consider the machine 1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE (bbch), discovered by Pavel Kropitz in May 2022, and the general configuration:$$K(n):=0^{\mathrm{\infty }}10^{n}110^5\text{C}\text{<mo>></mo>}{0}^{\mathrm{\infty }}$$Shawn Ligocki showed that: $$\begin{array}{lll}{0}^{\mathrm{\infty }}\text{A}\text{<mo>></mo>}{0}^{\mathrm{\infty }}& \stackrel{45}{\to }& K(5)\\ K(4k)& \to & \mathrm{Halt}\left(\frac{3^{k+3}-11}{2}\right)\\ K(4k+1)& \to & K\left(\frac{3^{k+3}-11}{2}\right)\\ K(4k+2)& \to & K\left(\frac{3^{k+3}-11}{2}\right)\\ K(4k+3)& \to & K\left(\frac{3^{k+3}+1}{2}\right)\end{array}$$

Demonstrating Collatz-like behavior with exponential piecewise component functions.

Starting from config $K(5)$, these rules iterate 15 times before reaching the halt config leaving over $10\uparrow \uparrow 15$ non-zero symbols on the tape.

Why is Collatz randomness mysterious?

The (above displayed) Collatz function produces numbers whose even/odd property (parity) passes even NIST randomness tests. Consequently, pseudo random number generators (PRNG) have been proposed using this or similar functions. However, the mathematical proof that such systems have this property in general is remarkably elusive.