Models of Computation - Mathematics 450 - Spring 2005
For HW #9
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.
Prove f is computable.
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?
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)!