TIF = totally undefined function

K = the halting set

1. {x| phi_x is a constant function}

Call the above set T. T does not contain the TIF because it is not a constant function. To prove that T is not recursive, it suffices to show that, if it were recursive, then so would be K. Consider some arbitrary x and define the function theta(x,y) = a + Zero(phi_univ(x,x)). Where a is a digital copy of "physical graffiti" by Led Zeppelin. Since this function is partial recursive, there must be some index i with phi_i(x,y) = theta(x,y). use the s-m-n theorem to get the new index j = s(i,x).

phi_j(y)= phi_i(x,y)=theta(x,y).

Consider this function phi_j(y), if x is in K then phi_j(y) is the function phi_j(y) = a, and thus a constant function, so that j is in T. If x is not in K phi_j is the TIF and thus j is not in T. Hence membership of x in K is equivalent to membership of j in T. Since K is not recursive, neither is T.

2. {x| phi_x is not the TIF}

Call the above set T. T does not contain the TIF by definition. To prove that T is not recursive, it suffices to show that, if it were recursive, then so would be K. Consider some arbitrary x and define the function theta(x,y) = y + Zero(phi_univ(x,x)). Since this function is partial recursive, there must be some index i with phi_i(x,y) = theta(x,y). use the s-m-n theorem to get the new index j = s(i,x).

phi_j(y)= phi_i(x,y)=theta(x,y).

Consider this function phi_j(y), if x is in K then phi_j(y) is the identity function phi_j (y) = y, and thus not the TIF, so that j is in T. If x is not in K phi_j is the TIF and thus j is not in T. Hence membership of x in K is equivalent to membership of j in T. Since K is not recursive, neither is T.

3. {x| there is y with phi_x(y) converging and S.T. phi_y is total}

Call the above set T. T does not contain the TIF because TIF is not converging.

The set W = {y| phi_y is total} is not recursive by example 5.1

Define: 5.1Theta(y,z) = z + Zero(phi_univ(y,y))

To prove that T is not recursive, it suffices to show that, if it were recursive, then so would be W. Consider some arbitrary x and define the function theta(x,y,z) = z + Zero(5.1Theta(y,z)), where z is a constant. Since this function is partial recursive, there must be some index i with phi_i(x,y,z) = theta(x,y,z). use the s-m-n theorem to get the new index j =s(i,x),

phi_j(y,z)= phi_i(x,y,z)=theta(x,y,z).

Consider this function phi_j(y,z), if y is in W then phi_j(y,z) is the function phi_j (y,z) = z, which converges and has determined membership in W, so that j is in T. If y is not in W, phi_j is the TIF and thus j is not in T. Hence membership of y in W is equivalent to membership of j in T. Since W is not recursive, neither is T.

Let S be an r.e. set; prove that the sets D = U_{x in s} dom(phi_x) and R = U_{x in s} ran(phi_x) are both r.e.

Because S is RE there is a functions whose range is S let x be the index to this function

And call it P (I use this at the very end)

Let r be the index to the range function

h(x,y) = phi_x(y) if mu z[step(x,y,II_2(z))not=zero]

undefined otherwise

What this does is if phi_x(y) converges return that value

[phi_x is the function whose range = S]

g(q) = ran(phi_q) if mu z[step(r,phi_q,II_2(z))not=zero]

undefined otherwise

what this does is if ran(phi_q) converges return the range

now define

theta(x,y) = g(h(x,y))

Since theta is partial recursive there is some index k with phi_k = theta; now define g(x) = s(k,x) using s-m-n construction

Phi _g(x) (y) = theta(x,y) converges iff ran(phi _P(y) ) converges, thus its range is

Equal to R

Because S is RE there is a functions whose range is S let x be the index to this function

And call it P (I use this at the very end)

Let d be the index to the domain function

h(x,y) = phi_x(y) if mu z[step(x,y,II_2(z))not=zero]

undefined otherwise

What this does is if phi_x(y) converges return that value

[phi_x is the function whose range = S]

g(q) = <dom(phi_q) > if mu z[step(d,phi_q,II_2(z))not=zero]

undefined otherwise

what this does is if dom(phi_q) converges return the dom(phi_x) all paired together

now define

theta(x,y) = g(h(x,y))

Since theta is partial recursive there is some index k with phi_k = theta; now define g(x) = s(k,x) using s-m-n construction

Phi _g(x) (y) = theta(x,y) converges iff dom(phi _d(y) ) converges, thus its range (unpaired) is Equal to D

Now define w as the index of the above function. g(x) = w

And define

Theta2(w,y) = mu z [step(w, II_1(z), II_2(z)) = Succ(y)]

Where y is a pairing of some numbers y = <some numbers>

Effectively this function converges whenever y is in the range of phi_w

Since theta is partial recursive, there is some index k with phi_k = theta2; now define g(x) = s(k,x) by usinf s-m-n construction. phi _g(w) (y) = theta(w,y) converges iff y is in the range of phi_w so that the range of phi_w equals the domain of phi_g(w).