Home

Homework   Index   Syllabus   URM Simulator


Extra Homework Problems

Models of Computation - Mathematics 450 - Spring 2005


For HW #11

  1. State whether or not (you think) each of the following functions is computable. We have not yet proved any functions to be non-computable. We will do so in the next chapter. For this problem, if you believe a function is not computable, explain why you believe so; but no proof is necessary. If you think a function is computable, give a proof by Church's Thesis.
    1. f(x) = 1 if x is in Dom(g), 0 otherwise, where g(x) is a computable function.
    2. f(x) = 1 if px (the xth prime) is in Dom(g), undefined otherwise, where g(x) is a computable function.
    3. f(x) = 1 if px (the xth prime) is not in Dom(g), undefined otherwise, where g(x) is a computable function.
    4. f(x) = 1 if Dom(g) is nonempty, undefined otherwise, where g(x) is a computable function.

Updated: 31 August, 2009 17:44:19