TIF is the totally undefined function.

Problem 1 Give primitive recursive definitions of the following functions:

- lcm(x,y), the least common multiple of x and y

f(x,z1,….zn) = min y<=x[P (y,z1 … zn)] from last homework.

Lcm = f(mult(x,y),x,y)

Where predicate P (y’,x,y) is 1 if and (x|y’ , y|y’ )

- otherwise

b) mod(x,y), the remainder of x divided by y.

mod(0,y) = 0

mod(x+1,y) = 0 if equal(mod(x,y),minus(y,1))

succ(mod(x,y)) otherwise

c) cube(x), returns 1 if x is a perfect cube, 0 otherwise.

Cube(x) = exists y<=x [P(y,x)]

Where predicate P is P(y,x) = 1 if equal(mult(y,mult(y,y)),x)

0 otherwise

Problem 2. Are the following problems undecidable? Prove or disprove.

b) {x | for all y, phi_x(y) = y}

This problem is undecidable. Call the above set T The TIF is not in T because for all y TIF (y) is not = y

define: theta(x,y) = y + zero(phi_unv(x,x))

Because this function is partial recursive there exists some index i S.T. 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) = y, 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.

- {x | exists y with phi_y(x) = x}

This problem is decidable call this set T

phi_y is an identity function ie. . P_{1}^{1}(x)=x The above set is universal

c _{T} (x) = true

Problem 3. Show that the following problems are not r.e.

a) {(x,y) | dom(phi_x) = dom(phi_y) } call this set T

theta1(x,y) = 1 + zero(theta2(x,y)) + zero(theta3(x,y))

This function is a wrapper to insure theta2 and theta3 get the same x,y pair.

[fix x]

theta2(x,y) = y if step(x,x,y) = 0

TIF otherwise

This is a partialy recursive function as such there is an index i with phi_i = theta2. By using the s-m-n theorem, there is a total recursive function g with phi_{g(x)}(y) = theta2(x,y)

[Fix y]

Theta3(x,y) = x

This is one of the identity functions as such there is an index i with phi_i = theta3. By using the s-m-n theorem, there is a total recursive function g with phi_{g(y)}(x) = theta3(x,y)

Now if x is not in K (step=0) then phi_{g(x)} is an identity function and its domain is

The same as phi_{g(y) } thus this pair is in the set T. Conversely if x is in K (step not= 0) then phi_{g(x)} is the TIF, for y_{0} and all larger arguments, and its domain is not equal to phi_{g(y) }so this pair is not in T. Since K’ is not r.e. neither is T

- {x | phi_x is injective} call this set T

theta(x,y) = y if step (x,x,y) = 0

1 otherwise

This is a partialy recursive function as such there is an index i with phi_i = theta. By using the s-m-n theorem, there is a total recursive function g with phi_{g(x)}(y) = theta(x,y) Now if x is not in K (step=0) then phi_{g(x)} is injective, thus g(x) is in T. Conversely if x is in K (step not= 0) then phi_{g(x)} (y) is equal to 1 for y_{0} and all larger arguments and thus g(x) is not in T. so x is in K iff g(x) is not in T Since K’ is not r.e. neither is T

Problem 4. Prove that a set S is r.e iff there exists a (total) recursive predicate P such that x in S ó exists y, P(x,y) is true

If the set is empty this is true vacuously.

By definition every non-empty r.e. set is the range of a total recursive function. Call this function f. Let y be an upper bound on the y’ to try in f before giving up.

Define predicate P as:

P(x,y) = exists y’<=y [P2(y’,x)]

With P2 being: P2(y’,x) = 1 if f (y’) = x

0 otherwise

Forward: If the set is r.e then by definition f exists so this predicate exists.

[warning I lost points for the below]

Backward: If the predicate does not exists then f did not exist so the function cannot be r.e.