Models of Computation - Mathematics 352 - Fall 2009

For HW #7

Q1. Recall that C is defined in the book as the collection (or set) of all (URM) computable functions. What does it mean when the book says C is closed under minimalization?

Q2. If f(x) is a total function, is mu x ( f(x)=0 ) a total function? Why?

Q3. The following refer to page 45, the paragraph that starts as "Thus, in a trivial sense, ..." :

1. Explain the first sentence in your own words.
2. In the second sentence, what does "the use of the mu-operator is essential" mean?
3. Explain in your own words what "primitive recursive" means. What is the difference between "recursive function" and "primitive recursive function"? (See also pages 51-52.)
4. Explain the last sentence, especially what "non-essential" means.