Models of Computation - Mathematics 450 - Fall 2006

For HW #9

1. Define f(x) as x/2 if x is even, and 3x+1 if x is odd. This function is called the Collatz function, named after its author.
   1. Prove f is computable.
   2. Starting with x = 3, repeatedly apply the Collatz 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 that C(x) is computable. Hint (don't read this hint until you've tried your hardest!):  Use recursion to define a function g(x,n) = f(... f(x)...) , where f is iterated n times; then use g to define C.
      
      (It is unknown whether or not you  eventually reach 1 for every starting value of x. No one has found any counterexamples yet, nor has anyone been able to prove that you do always eventually reach 1. If you solve this question, you'll be very famous -- at least among mathematicians!)
      
      
   4. Is C(x) in PR, R₀, or R? Explain.