Question

1. Using Induction on the length of derivations, prove that the set of all Primitive Recursive Functions (PR) is a subset of all Partial Computable Functions (P).

2. Using the preceding problem, conclude that the set of all Primitive Recursive Functions (PR) is a subset of all Computable Functions (R).

Answer 1

1.prove that the set of all primitive recursive functions is a subset of all partial computable functions.

proof:

Every partial recursive function is partially computable for an alphabet Σ={a1,...,aN}. Similarly every partial computable function is a partial recursive function. So the class of primitive recursive functions is equal to the class of partial computable functions for every input.
To prove that every partial recursive function is a partial computable, since we are using a theorem that every Turing machine can simulate a RAM program, to show that every partial recursive function is partially computable.

There are recursive functions like the example given below:

A(0,y)=y +1 , A(x +1 , 0) = A(x, 1), A(x +1,y+ 1) =A(x, A(x +1,y)).

It can be shown that:

A(0,x)=x +1 , A(1,x)=x +2 , A(2,x)=2 x +3 , A(3,x)=2 x+3−3,
and
A(4,x)=2 2···216
}x −3,
with A(4,0) = 16−3 = 13

example:

A(4,1) = 216−3,A (4,2) = 2216 −3.
This can be shown by induction, using ordering on N×N, which is dened as follows: (m,n) (m,n ) i either m = m and n = n, or m<m , or m = m and n<n . We write (m,n) ≺ (m,n ) when (m,n) (m,n ) and (m,n) =(m,n ). We prove that A(m,n) is dened for all (m,n) ∈ N×N by complete induction over ordering on N×N.

In this case, (m,n) = (0 ,0), and since A(0,n)=n+1,wehaveA(0,0) = 1, and A(0,0) is dened.
For (m,n) = (0 ,0), the induction hypothesis is that A(m,n ) is dened for all (m,n ) ≺ (m,n). We need to conclude that A(m,n) is dened.
If m = 0, sinceA(0,n)=n + 1,A(0,n) is dened.
If m = 0 andn = 0, since
(m−1,1) ≺ (m,0), by the induction hypothesis, A(m−1,1) is dened, but A(m,0) = A(m−1,1),

If m = 0 andn = 0, since (m,n−1) ≺ (m,n), by the induction hypothesis, A(m,n−1) is dened. Since (m−1,A(m,n−1)) ≺ (m,n), by the induction hypothesis, A(m−1,A(m,n−1)) is dened. But A(m,n)= A(m−1,A(m,n−1)), and thus A(m,n) is dened. Thus, A(m,n) is dened for all (m,n) ∈ N×N.

Hence we proved that set of all primitive recursive functions is a subset of all partial computable functions using induction on the length of deviations.

2. using the preceding problem,conclude that the set of all primitive recursive functions is a subset of all computable functions.

conclusion:

The primitive recursive function can be computed by a computer program whose loops are all "for" loops. Primitive recursive functions form a strict subset of those general recursive functions that are also total functions.The importance of primitive recursive functions lies on the fact that most computable functions that are studied in number theory are primitive recursive. In fact, for showing that a computable function is primitive recursive, it suffices to show that its computational complexity is bounded above by a primitive recursive function of the input size.The set of primitive recursive functions is known as PR in computational complexity theory.

proof:

To see that all the functions in PR are primitive recursive, it is necessary only to consider operations . That is, we need to show that if f and g are primitive recursive, and h is obtained then h is also primitive recursive.

˜h(0)=0,˜h(n)=[h(0),…,h(n-1)]ifn>0⋅

We will show that ˜h is primitive recursive and then conclude that the same is true of h by using the equation

h(n)=(˜h(n+1))n+1⋅

Then we have

˜h(n+1)=˜h(n)⋅ph(n)n+1 ={˜h(n)⋅pf(⌊n/2⌋)n+1ifnis odd,˜h(n)⋅pg((˜h(n))⌊n/2⌋)n+1    ifnis even⋅

We proceed to make a short list of primitive recursive functions. Being primitive recursive, they are also computable.

1. x + y

To see that this is primitive recursive, we have to show how to obtain this function from the initial functions using only the operations of composition and recursion.

If we write f (x, y) = x + y, then we have the recursion equations

f(x,0)=x,f(x,y+1)=f(x,y)+1⋅

For this purpose we will call a function g (x₁, …, x_n) satisfactory if it has the property that for any unary functions h₁(t), …, h_n (t) that belong to PR, the function g (h₁(t),…, h_n (t)) also belongs to PR

we need to consider only the pairing function 〈 x₁, x₂〉 and the projection functions uin where 1 ≤ i ≤ n. If h₁(t) and h₂ (t) are in PR, then using operation 2 in the definition of PR, we see that 〈 h₁(t), h₂ (t)〉 is also in PR. Hence, 〈 x₁, x₂〉 is satisfactory.

Hence we conclude that the set of all primitve recursive functions is a subset of all computable functions.