Collatz-like

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:$$\begin{array}{lll}c(2k)& =& k\\ c(2k+1)& =& 3k+2\end{array}$$

A Collatz-like problem is a question about the behavior of iterating a Collatz-like function. Collatz-like problems are famously difficult.

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 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

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.