The Theory of Computation

Bernard M.E. Moret

Addison-Wesley-Longman, 1998

Detailed Solution

Chapter 5, Problem 27

We need to develop a reduction from the known productive set not K to the set S(c) that allows us to derive the productive function for S(c). Thus what we want is a reduction such that, if x is in not K, i.e., if phi_x(x) converges, then x in S(c), i.e., phi_x(c) converges. Define the function

theta(x,y)=phi_univ(x,x)-phi_univ(x,x)

By standard s-m-n arguments, there exists some total function f such that phi_f(x)(y)=theta(x,y). But note that phi_f(x) is either the constant function epsilon (when x not in not K), in which case f(x) not in S(c), or the totally undefined function (when x in not K), in which case f(x) in S(c). Thus we have a reduction from not K to S(c) such that x in not K <=> f(x) in S(c). (Incidentally, this reduction shows that S(c) is non-r.e., not surprisingly, since every productive set is by definition non-r.e.)

Now note that, if we have dom phi_i subset S(c), then we have

f^-1(dom phi_i) subset f^-1(S(c)) = not K

(We use f^-1(A) to denote the inverse image of A under f, i.e., the set of all x such that f(x) in A; we do not use f^-1 to denote a function of any kind!) Moreover, f^-1(dom phi_i) is r.e., so that there exists some phi_z such that dom phi_z = f^-1(dom phi_i); to see that, just note that phi_z(y) = phi_i(f(y)) has the desired properties. But then dom phi_z subset not K and so, by our previous remarks, z in not K-dom phi_z. It follows that f(z) in S(c)-dom phi_i. So all we need is to compute the z, i.e., to find a function g such that z=g(i); then the productive function for S(c) is just f*g. We saw that

phi_z(y) = phi_i(f(y))

has the desired properties. Thus, if f is the (total) function phi_j, then we have z=c(i,j) (using the composition function c) and the productive function for S(c) is just

p_S(c)(i) = phi_j(c(i,j)),

where j is a known constant.