Home

Homework   Syllabus   URM Simulator


Extra Homework Problems

Models of Computation - Mathematics 352 - Fall 2009


For HW #9

  1. Define f(x) as:  x/2 if x is even, 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:  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 refered to as "the 3x+1 problem". If you solve it, you'll be very famous -- at least among mathematicians!)
    4. Is C(x) in PR, R0, or R? Explain.