Generalized Collatz Function

2026-03-19T16:07:16Z

Roi H. Clem: /* Definition */ typo

A '''Generalized Collatz Function (GCF)''' is a function which naturally generalizes the classic Collatz function defined by Conway in his 1972 paper "Unpredictable iterations".<ref name=":0">John. H. Conway. 1972. [https://gwern.net/doc/cs/computable/1972-conway.pdf Unpredictable iterations]. In Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder, pages 49–52.</ref> They are functions defined casewise based upon the remainder of the input (modulo some value) where each case is an affine function. The behavior of GCFs is [[Turing complete]]. Many [[Busy Beaver]] champions and [[Cryptids]] simulate GCFs and more general [[Collatz-like]] functions.

== Definition ==
An m-case GCF is a casewise-defined function <math>g: \mathbb{N} \to \mathbb{N}</math>:

<math display="block">g(n) = \begin{cases}
a_0 n + b_0 & \text{if } n \equiv 0 \pmod{m} \\
a_1 n + b_1 & \text{if } n \equiv 1 \pmod{m} \\
& \vdots \\
a_{m-1} n + b_{m-1} & \text{if } n \equiv m-1 \pmod{m} \\
\end{cases}</math>

where all <math>a_i,b_i \in \mathbb{Q}</math> restricted such that for all <math>n \in \mathbb{N} \implies g(n) \in \mathbb{N}</math>. We say that g halts on input n if there exists a k such that <math>g^k(n) = 1</math>. 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.<ref name=":1">Stuart A. Kurtz and Janos Simon. 2007. The undecidability of the generalized Collatz problem. In Jin-Yi Cai, S. Barry Cooper, and Hong Zhu, editors, Theory and Applications of Models of Computation, 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, volume 4484 of Lecture Notes in Computer Science, pages 542–553. Springer, 2007. {{doi|10.1007/978-3-540-72504-6_49}}</ref>

== 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 <math>2^{n+1}</math>.<ref name=":0" />
* Kurtz and Simon proved in 2007 that GCP is <math>\Pi_2^0</math>-complete.<ref name=":1" />
* Kascak proved in 1992 that there exists a Universal GCF with modulus 396.<ref>Frantisek Kascak. 1992. Small universal one-state linear operator algorithm. In: Havel, I.M., Koubek, V. (eds) Mathematical Foundations of Computer Science 1992. MFCS 1992. Lecture Notes in Computer Science, vol 629. Springer, Berlin, Heidelberg. {{doi|10.1007/3-540-55808-X_31}}</ref> (Note: He calls them one-state linear operator algorithms (OLOA).)

== References ==
<references />

[[Category:Functions]]

BusyBeaverWiki - User contributions [en]

Generalized Collatz Function