TIF is the totally undefined function.

Problem 1 Give primitive recursive definitions of the following functions:
  1. 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’ )

    1. 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.

 

 

  1. {x | exists y with phi_y(x) = x}

This problem is decidable call this set T

phi_y is an identity function ie. . P11(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 phig(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 phig(y)(x) = theta3(x,y)

Now if x is not in K (step=0) then phig(x) is an identity function and its domain is

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

 

  1. {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 phig(x)(y) = theta(x,y) Now if x is not in K (step=0) then phig(x) is injective, thus g(x) is in T. Conversely if x is in K (step not= 0) then phig(x) (y) is equal to 1 for y0 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.