primitive recursive function (original) (raw)

Definition. The set of primitive recursive functions is the smallest subset 𝒫⁢ℛ of ℱ where:

1. 1. (zero function) z∈𝒫⁢ℛ∩F1, given by z⁢(n):=0;
2. 1. (successor function) s∈𝒫⁢ℛ∩F1, given by s⁢(n):=n+1;
3. 1. (projection functions) pmk∈𝒫⁢ℛ∩Fk, where m≤k, given by pmk⁢(n1,…,nk):=nm;
4. 1. 𝒫⁢ℛ is closed under composition: If {g1,…,gm}⊆𝒫⁢ℛ∩Fk and h∈𝒫⁢ℛ∩Fm, then f∈𝒫⁢ℛ∩Fk, where

      f⁢(n1,…,nk)=h⁢(g1⁢(n1,…,nk),…,gm⁢(n1,…,nk));

5. 1. 𝒫⁢ℛ is closed under primitive recursion: If g∈𝒫⁢ℛ∩Fk and h∈𝒫⁢ℛ∩Fk+2, then f∈𝒫⁢ℛ∩Fk+1, where

      f⁢(n1,…,nk,0)	=	g⁢(n1,…,nk)
      f⁢(n1,…,nk,s⁢(n))	=	h⁢(n1,…,nk,n,f⁢(n1,…,nk,n)).

Many of the arithmetic functions that we encounter in basic math are primitive recursive, including addition, multiplication, and exponentiation. More examples can be found in this entry (http://planetmath.org/ExamplesOfPrimitiveRecursiveFunctions).

Primitive recursive functions are computable by Turing machines. In fact, it can be shown that 𝒫⁢ℛ is precisely the set of functions computable by programs using FOR NEXT loops. However, not all Turing-computable functions are primitive recursive: the Ackermann function is one such example.

Remarks.

1. [1]
   Every primitive recursive function is total, since it is built from z, s, and pmk, each of which is total, and that functional composition, and primitive recursion preserve totalness. By including ∅ in 𝒫⁢ℛ above, and close it by functional composition and primitive recursion, one gets the set of partial primitive recursive functions.
2. [2]
   Primitive recursiveness can be defined on subsets of ℕk: a subset S⊆ℕk is primitive recursive if its characteristic function φS, which is defined as

   φS⁢(x):={1if ⁢x∈S,0otherwise.
   is primitive recursive.

3. [3]
   Likewise, primitive recursiveness can be defined for predicates over tuples of natural numbers. A predicate Φ⁢(𝒙), where 𝒙∈ℕk, is said to be primitive recursive if the set S⁢(Φ):={𝒙∣Φ⁢(𝒙)} is primitive recursive.