Home

Homework   Index   Syllabus   URM Simulator


Extra Homework Problems

Models of Computation - Mathematics 450 - Spring 2005


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: use recursion.)

      Here's another hint, but don't read it until you've tried your hardest. Hint #2: use recursion to define a function g(x,n) = f(... f(x)...) (n times).

      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, R0, or R? Explain.

Updated: 31 August, 2009 17:44:19