Collatz-like: Difference between revisions

Revision as of 23:59, 4 June 2025

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.

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.^[1]

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?^[2]

Exponential Collatz

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

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.^[3]

References

↑ Pascal Michel's Analysis of the BB(5, 2) Champion
↑ Shawn Ligocki. BB(2, 5) is Hard (Hydra). 10 May 2024.
↑ Shawn Ligocki. BB(6, 2) > 10↑↑15. 21 Jun 2022.

[1] Pascal Michel's Analysis of the BB(5, 2) Champion

[2] Shawn Ligocki. BB(2, 5) is Hard (Hydra). 10 May 2024.

[3] Shawn Ligocki. BB(6, 2) > 10↑↑15. 21 Jun 2022.

[1]

[2]

[3]

@@ Line 7: / Line 7: @@
 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 <math>n</math>-ary '''Collatz-like function''' of degree <math>m</math> is a partial function <math>f:\mathbb{Z}^n\hookrightarrow\mathbb{Z}^n</math> of the form
-<math display="block">
-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} </math>
-where <math>z</math> is a positive integer and <math>P_1,P_2,\dots,P_{nz}</math> are (not necessarily distinct) univariate polynomials with rational coefficients of at most degree <math >m</math>. This definition is often restricted to those functions of degree one.
-For any given <math>n</math>-ary Collatz-like function <math>g</math> and some two indexed series of nonempty subsets <math>\{S_1,S_2,\dots,S_n\},\{T_1,T_2,\dots,T_n\}</math> of the integers, we can write the well-formed formula
-<math display="block">
-\forall \sigma \in \prod_{i=1}^n S_i\exists\tau\in\prod_{i=1}^nT_i\exists x.g^{\circ x}(\sigma)=\tau
-</math>
-where <math>g^{\circ x}(\sigma)</math> is the <math>x</math>-th iterate of <math>g</math> on <math>\sigma</math>. 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 <math>\forall \sigma\in\mathbb{N}\exists x.C^{\circ x}(\sigma)=1</math>, where
-<math display="block">
-C(a)=
-\begin{cases}
-    \frac12a & a\equiv 0\mod 2\\
-a+1 & a\equiv 1\mod 2.
-\end{cases}</math>
-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 <math>\exists \tau\in\mathbb{N}\times\{-1\}\exists x.A^{\circ x}(8,0)=\tau</math> where
-<math display="block">
-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}</math>
 == Examples ==