Primitive Recursive Function - Some Common Primitive Recursive Functions

Some Common Primitive Recursive Functions

The following examples and definitions are from Kleene (1952) pp. 223-231 — many appear with proofs. Most also appear with similar names, either as proofs or as examples, in Boolos-Burgess-Jeffrey 2002 pp. 63-70; they add #22 the logarithm lo(x, y) or lg(x, y) depending on the exact derivation.

In the following we observe that primitive recursive functions can be of four types:

1. functions for short: "number-theoretic functions" from { 0, 1, 2, ...} to { 0, 1, 2, ...},
2. predicates: from { 0, 1, 2, ...} to truth values { t =true, f =false },
3. propositional connectives: from truth values { t, f } to truth values { t, f },
4. representing functions: from truth values { t, f } to { 0, 1, 2, ... }. Many times a predicate requires a representing function to convert the predicate's output { t, f } to { 0, 1 } (note the order "t" to "0" and "f" to "1" matches with ~(sig( )) defined below). By definition a function φ(x) is a "representing function" of the predicate P(x) if φ takes only values 0 and 1 and produces 0 when P is true".

In the following the mark " ' ", e.g. a', is the primitive mark meaning "the successor of", usually thought of as " +1", e.g. a +1 =_def a'. The functions 16-21 and #G are of particular interest with respect to converting primitive recursive predicates to, and extracting them from, their "arithmetical" form expressed as Gödel numbers.

1. Addition: a+b
2. Multiplication: a×b
3. Exponentiation: ab,
4. Factorial a! : 0! = 1, a'! = a!×a'
5. pred(a): Decrement: "predecessor of a" defined as "If a> 0 then a-1 → a_new else 0 → a."
6. Proper subtraction: a ┴ b defined as "If a ≥ b then a-b else 0."
7. Minimum (a₁, ... a_n)
8. Maximum (a₁, ... a_n)
9. Absolute value: | a-b | =_defined a ┴ b + b ┴ a
10. ~sg(a): NOT: If a=0 then sg(a)=1 else if a>0 then sg(a)=0
11. sg(a): signum(a): If a=0 then sg(a)=0 else if a>0 then sg(a)=1
12. "b divides a" : If the remainder ( a, b )=0 then else b does not divide a "evenly"
13. Remainder ( a, b ): the leftover if b does not divide a "evenly". Also called MOD(a, b)
14. a = b: sg | a - b |
15. a < b: sg( a' ┴ b )
16. Pr(a): a is a prime number Pr(a) =_def a>1 & NOT(Exists c)₁
17. P_i: the i+1-st prime number
18. (a)_i : exponent a_i of p_i =_def μx ; μx is the minimization operator described in #E below.
19. lh(a): the "length" or number of non-vanishing exponents in a
20. a×b: given the expression of a and b as prime factors then a×b is the product's expression as prime factors
21. lo(x, y): logarithm of x to the base y

In the following, the abbreviation x =_def x_i, ... x_n; subscripts may be applied if the meaning requires.

• #A: A function φ definable explicitly from functions Ψ and constants q₁, ... q_n is primitive recursive in Ψ.
• #B: The finite sum Σ_{y ψ(x, y) and product Πyψ(x, y) are primite recursive in ψ.}
• #C: A predicate P obtained by substituting functions χ₁,..., χ_m for the respective variables of a predicate Q is primitive recursive in χ₁,..., χ_m, Q.
• #D: The following predicates are primitive recursive in Q and R:

• NOT_Q(x) .
• Q OR R: Q(x) V R(x),
• Q AND R: Q(x) & R(x),
• Q IMPLIES R: Q(x) → R(x)
• Q is equivalent to R: Q(x) ≡ R(x)

• #E: The following predicates are primitive recursive in the predicate R:

• (Ey)_{y R(x, y) where (Ey)y denotes "there exists at least one y that is less than z such that"}
• (y)_{y R(x, y) where (y)y denotes "for all y less than z it is true that"}
• μy_{y R(x, y). The operator μyy R(x, y) is a bounded form of the so-called minimization- or mu-operator: Defined as "the least value of y less than z such that R(x, y) is true; or z if there is no such value."}

• #F: Definition by cases: The function defined thus, where Q₁, ..., Q_m are mutually exclusive predicates (or "ψ(x) shall have the value given by the first clause that applies), is primitive recursive in φ₁, ..., Q₁, ... Q_m:

φ(x) =

• φ₁(x) if Q₁(x) is true,
• . . . . . . . . . . . . . . . . . . .
• φ_m(x) if Q_m(x) is true
• φ_m+1(x) otherwise

• #G: If φ satisfies the equation:

φ(y,x) = χ(y, NOT-φ(y; x₂, ... x_n ), x₂, ... x_n then φ is primitive recursive in χ. 'So, in a sense the knowledge of the value NOT-φ(y; x_{2 to n} ) of the course-of-values function is equivalent to the knowledge of the sequence of values φ(0,x_{2 to n}), ..., φ(y-1,x_{2 to n}) of the original function."