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.