Models of Computation - Mathematics 450 - Spring 2005
For HW #11
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.
f(x) = 1 if x is in Dom(g), 0 otherwise, where g(x) is a computable
function.
f(x) = 1 if px (the xth prime) is in Dom(g), undefined
otherwise, where g(x) is a computable function.
f(x) = 1 if px (the xth prime) is not in Dom(g), undefined
otherwise, where g(x) is a computable function.
f(x) = 1 if Dom(g) is nonempty, undefined otherwise, where g(x) is a
computable function.