The "generalized collatz conjecture" (rather than 3n+1 and n/2 we use some a*n+k) was proven by the wonderful John Conway to be undecidable [0] by inventing a t

The "generalized collatz conjecture" (rather than 3n+1 and n/2 we use some a*n+k) was proven by the wonderful John Conway to be undecidable [0] by inventing a toy language called FRACTRAN [1] and showing that it was turing complete. It would be so wonderful to show that 3n+1 and n/2 are enough to compute anything - writing "programs" this way would be fun to look at. [0]: https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable_generalizations https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable... [1]: https://en.wikipedia.org/wiki/FRACTRAN https://en.wikipedia.org/wiki/FRACTRAN