Some basic Primitive
Recursive functions
(Special kind of
Computable functions)
9/10/2012
1.
X+Y
= h(X,Y)
h(X,0) = X = P1(X)
h(X,Y+1)
= (X+Y) + 1 = S(X+Y)
= S(P3(X,Y,h(X,Y)))
= g(X,Y, h(X,Y))
where
g(X1,X2,X3)
= S(P3(X1,X2,X3))
2. X*Y = h(X,Y)
h(X,0) = 0 = N(X); Zero
function
h(X,Y+1) = X*Y + X
= g(X,Y, h(X,Y))
= X + h(X,Y)
where
g(X1,X2,X3) = P1(X1,X2,X3) +
P3(X1,X2,X3)
3. X!
4. X**Y
5. PRED(X) PRED(0) = 0
PRED(T+1) = T
6. X-.Y (Proper
Difference)
X-.0 = X
X-.(T+1) = PRED(X-.T)
7. ABS(X-Y) = (X-.Y) +
(Y-.X)
8. a(X)
= 1-.X or a(0)
= 1
a(T+1)
= 0.
9. X=Y (Predicate)
which is a(ABS(X-Y))
10. X<=Y which is a(X-.Y)
11. X>Y NOT(X<=Y) The NOT Operator
preserves
P.R. or Computability
12. Y|X or Div(Y,X)
(Y is a divisor of X)
which is the same as (%T)(Y*T=X)for
T<=X
Bounded Quantifiers preserve P.R. or
Computability of
functions.
13. PRIME(X)
which is (X>1 && ($T) (T=1 || T=X ||
NOT(T|X)))
for T <= X
14. INT(X/Y) which is the "Integer Part" of
X/Y
which is MIN((T+1)*Y>X) for T<=X
15. R(X,Y): Remainder when X is divided by
Y.
which is (X -. (Y*INT(X/Y)))
16. P(N) N-th prime number where P(0)=0,
P(1)=2
P(0) = 0
P(T+1) = MIN (PRIME(K) && K>P(T))
K<=(P(T)!+1)