Models of Computation - Mathematics 352 -
Fall 2009
For HW #9
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.
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: 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!)