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.