Models of Computation - Mathematics 352 - Fall 2009

For HW #6.1

Q1: Give a complete proof of Theorem 4.5 (a).  (The book's proof is just a brief sketch).

Q2: Assuming that the function f(x,y) = x^y is computable, prove that each of the following functions is also computable. (You may only use the function f(x,y) = x^y, the three basic functions, and the Substitution Theorem in your proofs.)

1. g(x) = x^2
2. h(x,y,z) = x^z
3. j(x,y) = y^x

Q3. Suppose that M(x) and Q(x) are decidable predicates. Show that the predicate `M(x) xor Q(x)' is also decidable, where 'xor' represents the 'exclusive or': p xor q is true iff p is true or q is true, but not both. In your proof you may only use the three basic functions, the constant functions (f(x) = m, where m is a fixed natural number), the functions in Theorem 4.5, and the Substitution and Recursion Theorems. (Hint: see the proof of Corollary 4.7 on page 37.)