3 ms·

I wasn't aware of the "Collatz-like iterative process" for BB lower bounds. That seems to suggest that the collatz conjecture sits somewhere close to the "edge

• nneonneo 5y ago
  There’s another possible explanation: Collatz-type recurrences are the most complex behaviors that can be encoded using a tiny number of Turing machine states, due to the way TMs access memory. From another comment, it turns out you can apply similar busy-beaver definitions to the lambda calculus, but you get very different results for small structures due to the innate recursive structure of the lambda calculus. Of course, if you have enough states in your Turing machine, or enough terms in your lambda expression, you can express any computation. The interesting thing is what happens when you look at small instances of each.
• prezjordan 5y ago
  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