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.

Definitions

An $n$-ary Collatz-like function is a partial function $f:{\mathbb{\mathbb{Z}}}^n\hookrightarrow {\mathbb{\mathbb{Z}}}^n$ of the form

$$f(t_1,t_2,\dots ,t_n)=\{\begin{array}{ll}(P_1(t_1),P_2(t_2),\dots ,P_n(t_n))& t_1\equiv 0modz\\ (P_{n+1}(t_1),P_{n+2}(t_2),\dots ,P_{2n}(t_n))& t_1\equiv 1modz\\ ⋮& ⋮\\ (P_{nz-n+1}(t_1),\dots ,P_{nz}(t_n))& t_1\equiv -1modz,\end{array}$$ where $z$ is a positive integer and $P_1,P_2,\dots ,P_{nz}$ are (not necessarily distinct) polynomials with rational coefficients. This definition is often restricted to those polynomials of degree one.

For any given $n$-ary Collatz-like function $g$ and some two indexed series of subsets $\{S_1,S_2,\dots ,S_n\},\{T_1,T_2,\dots ,T_n\}$ of the integers, we can write a well-formed formula which states

$$\mathrm{\forall }\sigma \in \prod _{i=1}^n{S}_i\mathrm{\exists }\tau \in \prod _{i=1}^n{T}_i\mathrm{\exists }x.g^{\circ x}(\sigma )=\tau$$

where $g^{\circ x}(\sigma )$ is the $x$-th iterate of $g$ on $\sigma$. Proving or disproving a formula of the above form is a Collatz-like problem.

Many cryptids exhibit Collatz-like behavior, meaning that their behavior can be concisely described via the iterated values of a Collatz-like function. For example, Antihydra's halting status is directly related to the truth value of $\mathrm{\exists }x\in \mathbb{\mathbb{N}}\times {\mathbb{\mathbb{Z}}}^{-}\mathrm{\exists }n.A(8,0)=x$ where

$$A(x,y)=\{\begin{array}{ll}(\frac{3}{2}x,y+2)& x\equiv 0mod2\\ (\frac{3}{2}x-\frac{1}{2},y-1)& x\equiv 1mod2.\end{array}$$

Examples

BB(5,2) Champion

Consider the BB(5,2) Champion and the generalized configuration:

$$M(n)=0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{1}^n{0}^{\mathrm{\infty }}$$Pascal Michel showed that:

$$\begin{array}{lcl}{0}^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>A</mrow>}{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{<mrow data-mjx-texclass="ORD">H<mo>></mo></mrow>}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 (a Cryptid) and the generalized configuration:

$$C(a,b)=0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD"><mo><</mo>B</mrow>}{0}^{3(a-2)}{3}^{b}20^{\mathrm{\infty }}$$ Daniel Yuan showed that:$$\begin{array}{l}\\ 0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}& & \stackrel{19}{\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{<mrow data-mjx-texclass="ORD">Halt</mrow>}(n)$ is a halting configuration with $n$ non-zero symbols on the tape.

Starting from config $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 being able to prove a detailed question about the trajectory of the Collatz-like function$$\begin{array}{lll}h(2n)& =& 3n\\ h(2n+1)& =& 3n+1\\ \end{array}$$starting from 3:

$$\begin{array}{l}\\ 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\cdots \\ \end{array}$$

Specifically, will it ever reach a point where the cumulative number of E (even transitions) applied is greater than twice the number of O (odd transitions) applied?

Tetration Machine

Consider the current BB(6,2) Champion (discovered by Pavel Kropitz in May 2022) and consider the general configuration:$$K(n)=0^{\mathrm{\infty }}10^{n}110^5\text{<mrow data-mjx-texclass="ORD">C<mo>></mo></mrow>}{0}^{\mathrm{\infty }}$$Shawn Ligocki showed that: $$\begin{array}{l}\\ 0^{\mathrm{\infty }}\text{<mrow data-mjx-texclass="ORD">A<mo>></mo></mrow>}{0}^{\mathrm{\infty }}& \stackrel{45}{\to }& K(5)\\ K(4k)& \to & \text{Halt}(\frac{3^{k+3}-11}{2})\\ K(4k+1)& \to & K(\frac{3^{k+3}-11}{2})\\ K(4k+2)& \to & K(\frac{3^{k+3}-11}{2})\\ K(4k+3)& \to & K(\frac{3^{k+3}+1}{2})\\ \end{array}$$

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.