Generalized Collatz Function: Difference between revisions

Latest revision as of 17:21, 29 October 2025

A Generalized Collatz Function (GCF) is a function which naturally generalizes the classic Collatz function defined by Conway in his 1972 paper "Unpredictable iterations".^[1] 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 compete. Many Busy Beaver champions and Cryptids simulate GCFs and more general Collatz-like functions.

Definition

An m-case GCF is a casewise-defined function $g : ℕ \to ℕ$ :

$g (n) = {\begin{cases} a_{0} n + b_{0} & if n \equiv 0 (\mod m) \\ a_{1} n + b_{1} & if n \equiv 1 (\mod m) \\ ⋮ \\ a_{m - 1} n + b_{m - 1} & if n \equiv m - 1 (\mod m) \end{cases}$

where all $a_{i}, b_{i} \in ℚ$ restricted such that for all $n \in ℕ ⟹ f (n) \in ℕ$ . 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.^[2]

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}$ .^[1]
Kurtz and Simon proved in 2007 that GCP is $Π_{2}^{0}$ -complete.^[2]
Kascak proved in 1992 that there exists a Universal GCF with modulus 396.^[3] (Note: He calls them one-state linear operator algorithms (OLOA).)

References

↑ ^1.0 ^1.1 John. H. Conway. 1972. Unpredictable iterations. In Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder, pages 49–52.
↑ ^2.0 ^2.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
↑ 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

[:0-1] 1.0 ^1.1 John. H. Conway. 1972. Unpredictable iterations. In Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder, pages 49–52.

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

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

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
-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 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.
+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 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 <math>g: \mathbb{N} \to \mathbb{N}</math>:
+An m-case GCF is a casewise-defined function <math>g: \mathbb{N} \to \mathbb{N}</math>:
 <math display="block">g(n) = \begin{cases}
@@ Line 11: / Line 11: @@
 \end{cases}</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. [https://doi.org/10.1007/978-3-540-72504-6_49 doi:10.1007/978-3-540-72504-6_49]</ref>
+where all <math>a_i,b_i \in \mathbb{Q}</math> restricted such that for all <math>n \in \mathbb{N} \implies f(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. [https://doi.org/10.1007/978-3-540-72504-6_49 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 the GCP is <math>\Pi_2^0</math>-complete.<ref name=":1" />
+* 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. [https://doi.org/10.1007/3-540-55808-X_31 doi:10.1007/3-540-55808-X_31]</ref> (Note: He calls them one-state linear operator algorithms (OLOA).)
 == References ==

Generalized Collatz Function: Difference between revisions

Latest revision as of 17:21, 29 October 2025

Definition

Turing Complete

References

Navigation menu

Search