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)