Primitive Recursive Functions

Primitive recursive functions are the functions which are computable in the artificial programming language LOOP which is defined in the following way:
The assignments x:=c, x:=x+c and x:=x-c are LOOP-Programs (x a variable, c a constant)
If P and Q are LOOP-Programs, then the sequence P ; Q is a LOOP-Program.
If P is a LOOP-Program, then LOOP x DO P END is a LOOP-Program.

Example:
Multiplication is primitive recursive because x:=y*z can be computed in LOOP by the following program:
x:=0
LOOP y DO
  LOOP z DO
    x:=x+1
  END
END

June 9, 1995
Mark Dettinger