HW 12 extra problems

Determine whether each of the following functions is well-defined and computable. (See below for what well-defined means.) Give clear and convincing arguments to support your answers. You may use Church's Thesis. You don't have to give rigorous proofs; just give as convincing an argument as you can.

• 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. (Hint.)

  3. D(x) = 0 if x <= 1, D(x) = 1 + D(f(x)) if x > 1, where f(x) = x/2 if x is even, f(x) = 3x+1 if x is odd. How does D(x) compare to the function C(x) defined in HW #10? Hints

  4. Remark: In many modern programming languages (such as C, Java, Mathematica, etc), all of the above functions (even the ones that are not well-defined and computable) can easily be "implemented": you can write a program that mimics the definition of the function -- however, the program may never stop if the function is not well-defined.

Well-defined function:

Suppose we define a function h by stating a condition C on h, i.e., a list of one or more equations that h must satisfy. We say h is well-defined if there exists one, and only one, function h that satisfies condition C. Thus, if there is no function that satisfies C, or if there is more than one such function, then we say h is not well-defined.

For example, if C is

h(x) = 1 if x = 0, h(x+1) = 2h(x)if x > 1

then there is exactly one function from N to N that satisfies C, so we say h is well-defined.

If C is just

h(x+1) = 2h(x) if x > 1

(with h(0) unspecified), then there is more than one function that satisfies C, so h is not well-defined.

If C is

h(x) =1 if x = 0, h(x) = 2h(x+1) if x > 1

then h is not well-defined because there is no function from N to N that satisfies C. In contrast, if we want h to be from R to R, then there is more than one such function, so h is not well-defined. And if we want h to be from Z to R, then there is exactly one such function, so h is well-defined.