Generalized Collatz Function - Revision history

Roi H. Clem: /* Definition */ typo

2026-03-19T16:07:16Z

Definition: typo

← Older revision		Revision as of 16:07, 19 March 2026
Line 11:		Line 11:
	\end{cases}</math>		\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 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. {{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 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 ==		== Turing Complete ==

Sligocki: Link Turing complete

2025-12-17T16:59:35Z

Link Turing complete

← Older revision		Revision as of 16:59, 17 December 2025
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 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.		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 ==		== Definition ==

Sligocki: Switch to doi template

2025-12-02T16:16:47Z

Switch to doi template

← Older revision		Revision as of 16:16, 2 December 2025
Line 11:		Line 11:
	\end{cases}</math>		\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 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>		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. {{doi\|10.1007/978-3-540-72504-6_49}}</ref>

	== Turing Complete ==		== Turing Complete ==
Line 17:		Line 17:
	* 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" />		* 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" />		* 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).)		* 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 ==

Sligocki: Switch from piecewise -> casewise. Seems like some authors treat piecewise as implying that each "piece" is contiguous.

2025-10-29T17:21:35Z

Switch from piecewise -> casewise. Seems like some authors treat piecewise as implying that each "piece" is contiguous.

← Older revision		Revision as of 17:21, 29 October 2025
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 ==		== 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}		<math display="block">g(n) = \begin{cases}

Sligocki: /* Definition */ Clarify that a,b are rational numbers (not restricted to integers)

2025-10-29T17:20:09Z

Definition: Clarify that a,b are rational numbers (not restricted to integers)

← Older revision		Revision as of 17:20, 29 October 2025
Line 11:		Line 11:
	\end{cases}</math>		\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 ==		== Turing Complete ==

Sligocki: /* Turing Complete */ Ref smallest known universal GCF

2025-10-28T19:31:12Z

Turing Complete: Ref smallest known universal GCF

← Older revision		Revision as of 19:31, 28 October 2025
Line 14:		Line 14:

	== Turing Complete ==		== 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 ==		== References ==

Polygon: Added category:functions

2025-10-28T19:16:54Z

Added category:functions

← Older revision		Revision as of 19:16, 28 October 2025
Line 18:		Line 18:
	== References ==		== References ==
	<references />		<references />

			[[Category:Functions]]

Sligocki: Created page with "A '''Generalized Collatz Function (GCF)''' is a function which naturally generalizes the classic Collatz function defined by Conway in his 1972 paper "Unpredictable iterations".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. They are functions defined piecewise based upon the remainder of the input (modulo some value) wher..."

2025-10-28T18:09:57Z

Created page with "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) wher..."

New page

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.

== Definition ==
An m-case GCF is a piecewise-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>

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" />

== References ==
<references />