Models of Computation - Mathematics 450 - Fall 2006

For HW #11

1. Determine whether each of the following functions is well-defined and computable. (For example, the following function is not well-defined, and hence not computable: h(x) = 1 if x = 0,  h(x) = 2h(x+1) if x > 1.) Give clear and convincing arguments to support your answers. You may use Church's Thesis.
   1. f(x,y) = 1 if x = 0 or y = 0;   f(x,y) = f(2x,y-1) + f(x-1,2y) if x > 0 and y > 0.
   2. g(x,y,z) = 1 if x = 0 or y = 0 or z = 0;   g(x,y,z) = g(x-1,2y,2z) + g(x,y-1,2z) + g(x,y,z-1) if x > 0 and y > 0 and z > 0.
   3. j(x) = 0 if x <= 1,  j(x) = 1 + j(t(x)) if x > 1, where t(x) = x/2 if x is even, t(x) = 3x+1 if x is odd. How does j(x) compare to the Collatz function C(x) defined in HW #9?
      
      Remark: In many "modern" programming languages (such as C, Java, Lisp, etc), all of the above functions (even the ones that are not well-defined or computable) can be easily "implemented": you can write a program that mimics the definition of the function -- however, the program will never stop if the function is not well-defined or computable.