Extra Homework Problems |
Q1: Suppose f(x) can be defined from the basic functions by substitution, recursion, and bounded minimalization. Can f(x) necessarily also be defined from the basic functions by substitution and recursion only (no bounded minimalization)? Explain why. (Hint: Which theorems and functions are used to prove that bounded minimalization is computable? See the proof in the book.)