Given a partial function f : N * N, let D(f) denote the set of natural numbers at which f is defined: D(f) = {x ? N | f(x)?}; and let I(f) be the set of natural numbers that are values of f where it is defined: I(f) = {y ? N | for some x, f(x) = y}.

Prove or disprove the following statements, clearly stating any results about register machine computable functions and partial recursive functions that you use.

(a) Every subset S ? N is equal to I(f) for some register machine computable partial function f. [4 marks]

(b) If f is register machine computable, then I(f) is equal to D(g) for some partial recursive function g. [7 marks]

(c) If f is register machine computable, then D(f) is equal to I(g) for some total recursive function g. [4 marks]

(d) If g is a partial recursive function, then D(g) is equal to I(f) for some register machine computable partial function f. [5 marks]

Answer rating: 100% (QA)

The detailed answer for the above question is provided below a It is not true that every subset S N is equal to If for some register machine computabl... View the full answer