On 9/14/06, Mike Stay <mike@math.ucr.edu> wrote:
On 9/13/06, Marc LeBrun <mlb@well.com> wrote:
More seriously, it's always seemed to me that Collatz might be a member of some parametric family--including others like 3n-1, 3n+5, 17n+7, 105n+69...say. Then a "real" answer would be a theory that predicts the cycle structure given the parameters--as opposed to just this one instance. Or, perhaps at least a negative result such as that it's incomputably chaotic...
Conway proved it's undecidable. Any FRACTRAN program can be converted to a Collatz-like form, thus the general problem of predicting cycles is as hard as the Halting problem.
Of course, that doesn't say anything about the original Collatz problem, and I'd be very surprised if it's universal for computation (only one known non-halting program!)
A few years ago a local schoolteacher called Neil Hamilton observed that the original Collatz problem, for the function f(x) = 3x+1 if x is odd, x/2 if x is even is equivalent to the analogous problem for the new function g(y) = (y+1)/4 if y mod 4 = 3, (3y+1)/4 if y mod 4 = 1, 3y/2 if y mod 4 = 0,2. While I said at the time that I thought this was probably well-known, I didn't find any mention of it in the literature; and it did occur to me to wonder whether there had been any systematic attempt to investigate such equivalences. WFL