odd and . The Syracuse function is the function from the set of odd integers into itself, for which . Some properties of the Syracuse function are: For all , . (Because .) In more generality: For all and odd , . (Here is function iteration notation.) For all odd , The Collatz conjecture is equivalent to the statement that, for all in , there exists an integer such that . Undecidable generalizations In 1972, John Horton Conway proved that a natural generalization of the Collatz problem is algorithmically undecidable. Specifically, he considered functions of the form where are rational numbers which are so chosen that is always an integer. The standard Collatz function is given by , , , , . Conway proved that the problem Given and , does the sequence of iterates reach ? is undecidable, by representing the halting problem in this way. Closer to the Collatz problem is the following universally quantified problem: Given , does the sequence of iterates reach , for all ? 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 proved that the universally quantified problem is, in fact, undecidable and even higher in the arithmetical hierarchy; specifically, it is -complete. This hardness result holds even if one restricts the class of functions by fixing the modulus to 6480. Iterations of in a simplified version of this form, with all equal to zero, are formalized in an esoteric programming language called FRACTRAN. In popular culture In the movie Incendies, a graduate student in pure mathematics explains the Collatz conjecture to a group of undergraduates. She puts her studies on hold for a time to address some unresolved questions about her family's past. Late in the movie, the Collatz conjecture turns out to have foreshadowed a disturbing and difficult discovery that she makes about her family. See also semigroup Arithmetic dynamics Modular arithmetic Residue-class-wise affine group Further reading The Ultimate Challenge: The Problem, published in 2010 by the American Mathematical Society and edited by Jeffrey Lagarias, is a compendium of information on the Collatz conjecture, methods of approaching it, and generalizations. It includes two survey papers by the editor and five by other authors concerning the history of the problem, generalizations, statistical approaches, and