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}{l}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 {Z} ^{n}\hookrightarrow \mathbb {Z} ^{n}$ of the form

$$f(t_{1},t_{2},\dots ,t_{n})={\begin{cases}(P_{1}(t_{1}),P_{2}(t_{2}),\dots ,P_{n}(t_{n}))&t_{1}\equiv 0\mod z\\(P_{n+1}(t_{1}),P_{n+2}(t_{2}),\dots ,P_{2n}(t_{n}))&t_{1}\equiv 1\mod z\\\quad \quad \quad \quad \quad \quad \quad \quad \vdots &\quad \quad \quad \vdots \\(P_{nz-n+1}(t_{1}),\dots ,P_{nz}(t_{n}))&t_{1}\equiv -1\mod z,\end{cases}}$$

where $z$ is a positive integer and $P_{1},P_{2},\dots ,P_{nz}$ are (not necessarily distinct) univariate polynomials with rational coefficients. This definition is almost always restricted to those polynomials of degree one.

For any given $n$-ary Collatz-like function $g$ and some two indexed series of nonempty subsets $\{S_{1},S_{2},\dots ,S_{n}\},\{T_{1},T_{2},\dots ,T_{n}\}$ of the integers, we can write the well-formed formula

$$\forall \sigma \in \prod _{i=1}^{n}S_{i}\exists \tau \in \prod _{i=1}^{n}T_{i}\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. Collatz-like functions and problems are named for the unsolved Collatz conjecture, equivalent to $\forall \sigma \in \mathbb {N} \exists x.C^{\circ x}(\sigma )=1$, where

$$C(a)={\begin{cases}{\frac {1}{2}}a&a\equiv 0\mod 2\\3a+1&a\equiv 1\mod 2.\end{cases}}$$

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 $\exists \tau \in \mathbb {N} \times \{-1\}\exists x.A^{\circ x}(8,0)=\tau$ where

$$A(a,b)={\begin{cases}({\frac {3}{2}}a,b+2)&a\equiv 0\mod 2\\({\frac {3}{2}}a-{\frac {1}{2}},b-1)&a\equiv 1\mod 2.\end{cases}}$$

Examples

BB(5,2) Champion

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

$$M(n)=0^{\infty }\;{\textrm {<A}}\;1^{n}\;0^{\infty }$$

Pascal Michel showed that:

$${\begin{array}{lcl}0^{\infty }\;{\textrm {<A}}\;0^{\infty }&=&M(0)\\M(3k)&\xrightarrow {5k^{2}+19k+15} &M(5k+6)\\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 }\\\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^{\infty }\;{\textrm {<B}}\;0^{3(a-2)}\;3^{b}\;2\;0^{\infty }$$

Daniel Yuan showed that:

$${\begin{array}{l}\\0^{\infty }\;{\textrm {A>}}\;0^{\infty }&&\xrightarrow {19} &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 ${\textrm {Halt}}(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}{l}h(2n)&=&3n\\h(2n+1)&=&3n+1\\\end{array}}$$

starting from 3:

$${\begin{array}{l}\\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\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^{\infty }\;1\;0^{n}\;11\;0^{5}\;{\textrm {C>}}\;0^{\infty }$$

Shawn Ligocki showed that:

$${\begin{array}{l}\\0^{\infty }\;{\textrm {A>}}\;0^{\infty }&\xrightarrow {45} &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.