Collatz

Define f(x) as: x/2 if x is even, 3x+1 if x is odd.

• 1. Prove f is computable (without using Church's Thesis).

  2. Starting with x = 3, repeatedly apply the function f(x) defined above until you get 1 (i.e., find -- by hand -- f(3), then f(f(3)), then f(f(f(3))), and so on). How many times do you need to do this iteration?

  3. Define C(x) as the smallest number z of iterations it takes to get f(...f(x)..) = 1, if such z exists; otherwise C(x) is undefined. Prove, without using Church's Thesis, that C(x) is computable. Hint: Let g(x,n) = f... f(x) , where f is iterated n times. Use recursion to show g is computable, and then conclude C is computable. (It is unknown whether you eventually reach 1 for every starting value of x. No one has found any counterexamples, nor has anyone been able to prove that you always eventually reach 1. This is usually referred to as "the 3x+1 problem", or "the Collatz problem", named after its inventor. If you solve it, you'll be very famous -- at least among mathematicians!)

  4. Is C(x) in PR, R₀, or R? Explain.