Note: attached are various functions used in this assignment, and some

that were not used.

 

Problem 1. Exercise 5.5 in the book

Exercise 5.5 Using the various constructors of the last few exercises, prove that the following predicates and functions are primitive recursive:

  1. f(x, z1, … , zn) = min y<=x [ P (y, z1,…,zn)] returns the smallest y no larger than x such that the predicate P is true; if no such y exists, the function returns x+1.

Defined predicate as Pr to distinguish it from projection function.

[I took liberties with Projection function use in the call to the predicate

(in funct h) As I am feeling "confident" and it made the functions really nasty to read.]

Defined as:

f(0, z1,…,zn)= not(Pr(0,z1,…,zn))

f(x+1,z1,…zn)=h(x,f(x,z1,…zn),z1,…,zn)

[For definition of no_larger see part b of this exercise]

h defined as:

h(x,y,z1,…,zn)= P2n+2(x,y,z1,…,zn) if

No_larger(P2n+2(x,y,z1,…zn),P1n+2(x,y,z1,…,zn))

= succ(P1n+2(x,y,z1,…,zn)) if Pr(succ(x),z1,…,zn)

= succ(succ(P1n+2(x,y,z1,…,zn))) otherwise

b) x<=y, true iff x is no larger than y

Defined as:

No_larger(x,y) = lev’(guard(minus(x,y),succ(minus(P22(x,y)P12(x,y))))

 

c) x|y, true iff x divides y exactly.

Div(x,z)= there_exists(P12(x,z), P12(x,z),P22(z))

With the E.Q using the predicate Pr[equal(mult(y,x),z)]

Defined as:

Pr(y,x,z) = equal(mult(P13(y,x,z),P23(y,x,z)),P33(y,x,z)))

 

 

d) is_prime(x), true iff x is prime.

is_prime(x)= not(f(P11(x),P11(x)))

f is existential quantifier where the predicate Pr is Pr[y>1 and y|x]

Pr is defined as:

[first two is defined as: two(x)=succ(succ(zero(x))) ]

Pr(y,x) = and(no_larger(two(P12(y,x)),P12(y,x)),div(y,x))

e) prime(x) returns the xth prime.

Nth_prime(0) = succ(succ(0))

Nth_prime(x+1) = h(P22(x,Nth_prime(x)))

h(y)= g(y!+1,y) -> g(add(fact(y),succ(zero(y))),succ(dec(y)))

[the (f) function I am calling below is the min y function defined in part a]

g(x,z) = f(x,z)

with f using the predicate Pr

in math

Pr(y,z)=true if(y>z and y is prime)

The right way

Pr(y,z)= and(no_larger(succ(P22(y,z)),P12(y,z)),is_prime(P12(y,z)))

 

Problem 2. Exercise 5.11

Exercise 5.11 Prove that the following functions are primitive recursive by giving a formal construction.

  1. The function exp(n,m)is the exponent of the mth prime in the prime power decomposition of n, where we consider the 0th prime to be 2.

    2. [I took liberties using the projection function here as it made my functions

    very difficult to read]

    Exp(n,m) =Help(n,n,m)

    Help(0,y,z) = zero(P12(y,z))

    Help(w+1,y,z) = G(w,Help(w,y,z),y,z)

    G(w,x,y,z) =add(x, Pr(w,y,z))

    Pr(w,y,z) = Div(pow(w,nth_prime(z)),y)

    Note: pow(x,y)=y^x

     

     

  2. The function max y<= x[g(y,z1,…,zn)] where g is primitive recursive, returns the largest value in {g(0,…),g(1,…),…,g(x,…)}.

    3. f(0, z1,…,zn) = g(0,z1,…,zn)

    f(x+1,z1,…zn) =h(x,f(x,z1,…zn),z1,…,zn)

    h defined as:

    [liberties were taken in the call to g]

    h(x,y,z1,…,zn)= max(P2n+2(x,y,z1,…zn),g(succ(x),z1,…zn))

  3. The Fibonacci function F(n) is defined by F(0)=F(1) = 1 and F(n)=F(n-1)+F(n-2).

II = the projection function

F(n) = II1(II2(P(n)))

The P from the book

P(0) = <1,g(0)> g(x)= succ(x)

P(n+1) = < n+2 < h(n,P(n)), II2 ( P(n)) > >

Where h is:

h(n,z) = 1-> succ(zero(P12(n,z))) if n= 1 ->equal(P12(n,z)), succ(zero(P12(n,z))))

= add(II2(z),II3(z)) otherwise

 

Problem 3. Exercise 5.13

Exercise 5.13 Verify that the function f defined as follows:

f(0,x) = g(x)

f(i+1,x)=f(i,h(x))

is primitive recursive whenever g and h are.

I can redefine this (f) as such:

First a function F1:

F1(0,x) = P11(x)

F1(i+1,x) = h(P23(i,F1(i,x)))

f(i,x) = g(P23(i,F1(i,x)))