Editing Collatz conjecture (section)

== Undecidable generalizations ==
In 1972, [[John Horton Conway]] proved that a natural generalization of the Collatz problem is algorithmically [[undecidable problem|undecidable]].<ref>{{cite conference |last=Conway |first=John H. |year=1972 |contribution=Unpredictable iterations |title=Proc. 1972 Number Theory Conf., Univ. Colorado, Boulder |pages=49–52}}</ref>

Specifically, he considered functions of the form
<math display="block"> {g(n) = a_i n + b_i} \text{ when } {n\equiv i \pmod P},</math>
where {{math|''a''<sub>0</sub>, ''b''<sub>0</sub>, ..., ''a''<sub>''P'' − 1</sub>, ''b''<sub>''P'' − 1</sub>}} are rational numbers which are so chosen that {{math|''g''(''n'')}} is always an integer. The standard Collatz function is given by {{math|''P'' {{=}} 2}}, {{math|''a''<sub>0</sub> {{=}} {{sfrac|1|2}}}}, {{math|''b''<sub>0</sub> {{=}} 0}}, {{math|''a''<sub>1</sub> {{=}} 3}}, {{math|''b''<sub>1</sub> {{=}} 1}}. Conway proved that the problem

: Given {{mvar|g}} and {{mvar|n}}, does the sequence of iterates {{math|''g<sup>k</sup>''(''n'')}} reach {{math|1}}?

is undecidable, by representing the [[halting problem]] in this way.

Closer to the Collatz problem is the following ''universally quantified'' problem:

: Given {{mvar|g}}, does the sequence of iterates {{math|''g<sup>k</sup>''(''n'')}} reach {{math|1}}, for all {{math|''n'' > 0}}?

Modifying the condition in this way can make a problem either harder or easier to solve (intuitively, it is harder to justify a positive answer but might be easier to justify a negative one). Kurtz and Simon<ref name=KurtzSimon>{{cite book |last1=Kurtz |first1=Stuart A. |last2=Simon |first2=Janos |editor1-last=Cai |editor1-first=J.-Y. |editor2-last=Cooper |editor2-first=S. B. |editor3-last=Zhu |editor3-first=H. |year=2007 |chapter-url=https://books.google.com/books?id=mhrOkx-xyJIC&pg=PA542 |chapter=The undecidability of the generalized Collatz problem |title=Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007 |isbn=978-3-540-72503-9 |doi=10.1007/978-3-540-72504-6_49 |pages=542–553}} As [http://www.cs.uchicago.edu/~simon/RES/collatz.pdf PDF]</ref> proved that the universally quantified problem is, in fact, undecidable and even higher in the [[arithmetical hierarchy]]; specifically, it is {{math|Π{{su|b=2|p=0}}}}-complete. This hardness result holds even if one restricts the class of functions {{mvar|g}} by fixing the modulus {{mvar|P}} to 6480.<ref>{{cite journal |last=Ben-Amram |first=Amir M. |year=2015 |title=Mortality of iterated piecewise affine functions over the integers: Decidability and complexity |journal=Computability |doi=10.3233/COM-150032 |volume=1 |issue=1 |pages=19–56}}</ref>

Iterations of {{mvar|g}} in a simplified version of this form, with all <math>b_i</math> equal to zero, are formalized in an [[esoteric programming language]] called [[FRACTRAN]].