Generalized Collatz Function

A Generalized Collatz Function (GCF) is a function which naturally generalizes the classic Collatz function defined by Conway in his 1972 paper "Unpredictable iterations". They are functions defined piecewise based upon the remainder of the input (modulo some value) where each case is an affine function. The behavior of GCFs is Turing compete. Many Busy Beaver champions and Cryptids simulate GCFs and more general Collatz-like functions.

Definition

An m-case GCF is a piecewise-defined function $g:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$:

$$g(n)=\{\begin{array}{ll}{a}_{0}n+b_0& \text{if }n\equiv 0(\mathrm{mod}m)\\ a_{1}n+b_1& \text{if }n\equiv 1(\mathrm{mod}m)\\ & ⋮\\ a_{m-1}n+b_{m-1}& \text{if }n\equiv m-1(\mathrm{mod}m)\\ \end{array}$$

We say that g halts on input n if there exists a k such that $g^k(n)=1$. A Generalized Collatz Problem (GCP) is the "mortality problem" for a GCF. In other words, it is the question: For a specific GCF g, does it halt (eventually reach 1) on all inputs.

Turing Complete

• Conway proved in 1972 that every Minsky machine, M, can be encoded into a GCF, g, such that for all n: M halts on input n iff g halts on input $2^{n+1}$.
• Kurtz and Simon proved in 2007 that GCP is ${\mathrm{\Pi }}_2^0$-complete.
• Kascak proved in 1992 that there exists a Universal GCF with modulus 396. (Note: He calls them one-state linear operator algorithms (OLOA).)