Primitive recursive function
≈ 18 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop is fixed before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions lies in the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive. For example, addition and division, the factorial and exponential function, and the function which returns the nth prime are all primitive recursive. In fact, for showing that a computable function is primitive recursive, it suffices to show that its time complexity is bounded above by a primitive recursive function of the input size. It is hence not particularly easy to devise a computable function that is not primitive recursive; some examples are shown in section below. The set of primitive recursive functions is known as PR in computational complexity theory.
In computability theory, a primitive recursive function is, roughly speaking, a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop is fixed before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions lies in the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive. For example, addition and division, the factorial and exponential function, and the function which returns the nth prime are all primitive recursive. In fact, for showing that a computable function is primitive recursive, it suffices to show that its time complexity is bounded above by a primitive recursive function of the input size. It is hence not particularly easy to devise a computable function that is not primitive recursive; some examples are shown in section below. The set of primitive recursive functions is known as PR in computational complexity theory. {{ordered list|start=1 |1=Constant functions C_n^k : For each natural number n and every k , the k-ary constant function, defined by C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ n , is primitive recursive. | 2=Successor function: The 1-ary successor function S, which returns the successor of its argument (see Peano postulates), that is, S(x) \ \stackrel{\mathrm{def}}{=}\ x + 1 , is primitive recursive. | 3=Projection functions P_i^k : For all natural numbers i, k such that 1\le i\le k , the k-ary function defined by P_i^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ x_i is primitive recursive. }} More complex primitive recursive functions can be obtained by applying the operations given by these axioms: {{ordered list|start=4 | 4=Composition operator \circ\, (also called the substitution operator): Given an m-ary function h(x_1,\ldots,x_m)\, and m k-ary functions g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots, x_k) : h \circ (g_1, \ldots, g_m) \ \stackrel{\mathrm{def}}{=}\ f, \quad\text{where}\quad f(x_1,\ldots,x_k) = h(g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots,x_k)). For m=1 , the ordinary function composition h \circ g_1 is obtained. | 5=Primitive recursion operator \rho : Given the k-ary function g(x_1,\ldots,x_k)\, and the (k+2) -ary function h(y,z,x_1,\ldots,x_k)\, : \begin{align} \rho(g, h) &\ \stackrel{\mathrm{def}}{=}\ f, \quad\text{where the }(k+1)\text{-ary function } f \text{ is defined by}\\ f(y, x_1, \dots, x_k) &= \begin{cases} g(x_1, \dots, x_k) & \text{if } y=0, \\ h(y', f(y', x_1, \dots, x_k) ,x_1, \dots, x_k) & \text{if } y=S(y') \text{ for a } y' \in \mathbb{N}. \end{cases} \end{align} Interpretation: The function f acts as a for-loop from 0 up to the value of its first argument. The rest of the arguments for f , denoted here with x_1,\ldots,x_k , are a set of initial conditions for the for-loop which may be used by it during calculations but which are immutable by it. The functions g and h on the right-hand side of the equations that define f represent the body of the loop, which performs calculations. The function g is used only once to perform initial calculations. Calculations for subsequent steps of the loop are performed by h . The first parameter of h is fed the "current" value of the for-loop's index. The second parameter of h is fed the result of the for-loop's previous calculations, from previous steps. The rest of the parameters for h are those immutable initial conditions for the for-loop mentioned earlier. They may be used by h to perform calculations but they will not themselves be altered by h . }} The primitive recursive functions are the basic functions and those obtained from the basic functions by applying these operations a finite number of times. f(x_1, \dots, x_m) = (f_1(x_1, \dots, x_m), \dots, f_n(x_1, \dots, x_m)) where each component f_i : \mathbb{N}^m \to \mathbb{N} is a (scalar-valued) primitive recursive function.
Addition
A definition of the 2-ary function \operatorname{Add} , to compute the sum of its arguments, can be obtained using the primitive recursion operator \rho . To this end, the well-known equations \begin{align} 0 + y &= y, \\ S(x) + y &= S(x+y) \end{align} are "rephrased in primitive recursive function terminology": In the definition of \rho(g, h) , the first equation suggests to choose g = P_1^1 to obtain \operatorname{Add}(0, y) = g(y) = y ; the second equation suggests to choose h = S \circ P_2^3 to obtain \operatorname{Add}(S(x), y) = h(x, \operatorname{Add}(x, y), y) = (S \circ P_2^3)(x, \operatorname{Add}(x, y), y) = S(\operatorname{Add}(x, y)) . Therefore, the addition function can be defined as \operatorname{Add} = \rho(P_1^1, S \circ P_2^3) . As a computation example, \begin{align} \operatorname{Add}(1, 7) &= \rho(P_1^1, S \circ P_2^3) (S(0), 7) && \text{ by Def. } \operatorname{Add}, S \\ &= (S \circ P_2^3)(0, \operatorname{Add}(0, 7), 7) && \text{ by case } \rho(g, h) (S(...), ...) \\ &= S(\operatorname{Add}(0, 7)) && \text{ by Def. } \circ, P_2^3 \\ &= S(\rho(P_1^1, S \circ P_2^3) (0, 7)) && \text{ by Def. } \operatorname{Add} \\ &= S(P_1^1(7)) && \text{ by case } \rho(g, h) (0,...) \\ &= S(7) && \text{ by Def. } P_1^1 \\ &= 8 && \text{ by Def. } S. \\ \end{align}
Doubling
Given \operatorname{Add} , the 1-ary function \operatorname{Add} \circ (P_1^1, P_1^1) doubles its argument, (\operatorname{Add} \circ (P_1^1, P_1^1))(x) = \operatorname{Add}(x, x) = x + x.
Multiplication
In a similar way as addition, multiplication can be defined by \operatorname{Mul} = \rho(C_0^1, \operatorname{Add} \circ(P_2^3, P_3^3)) . This reproduces the well-known multiplication equations: \begin{align} \operatorname{Mul}(0, y) &= \rho(C_0^1, \operatorname{Add} \circ(P_2^3, P_3^3)) (0, y) && \text{ by Def. } \operatorname{Mul} \\ &= C_0^1(y) && \text{ by case } \rho(g, h) (0, ...) \\ &= 0 && \text{ by Def. } C_0^1. \end{align} and \begin{align} \operatorname{Mul}(S(x), y) &= \rho(C_0^1, \operatorname{Add} \circ(P_2^3, P_3^3)) (S(x),y) && \text{ by Def. } \operatorname{Mul} \\ &= (\operatorname{Add} \circ(P_2^3 ,P_3^3)) (x, \operatorname{Mul}(x, y), y) && \text{ by case } \rho(g, h) (S(...), ...) \\ &= \operatorname{Add}(\operatorname{Mul}(x, y), y) && \text{ by Def. } \circ, P_2^3, P_3^3 \\ &= \operatorname{Mul}(x, y) + y && \text{ by property of } \operatorname{Add}. \end{align}
Predecessor
The predecessor function acts as the "opposite" of the successor function and is recursively defined by the rules \operatorname{Pred}(0) = 0 and \operatorname{Pred}(S(n)) = n . A primitive recursive definition is \operatorname{Pred} = \rho(C_0^0, P_1^2) . As a computation example, \begin{align} \operatorname{Pred}(8) &= \rho(C_0^0, P_1^2) (S(7)) && \text{ by Def. } \operatorname{Pred}, S \\ &= P_1^2(7, \operatorname{Pred}(7)) && \text{ by case } \rho(g, h) (S(...), ...) \\ &= 7 && \text{ by Def. } P_1^2. \end{align}
Truncated subtraction
The limited subtraction function (also called "monus", and denoted " \mathbin{\dot{-}} ") is definable from the predecessor function. It satisfies the equations \begin{align} y \mathbin{\dot{-}} 0 &= y, \\ y \mathbin{\dot{-}} S(x) &= \operatorname{Pred}(y \mathbin{\dot{-}} x). \end{align} Since the recursion runs over the second argument, we begin with a primitive recursive definition of the reversed subtraction, \operatorname{RSub}(y, x) = x \mathbin{\dot{-}} y . Its recursion then runs over the first argument, so its primitive recursive definition can be obtained, similar to addition, as \operatorname{RSub} = \rho(P_1^1, \operatorname{Pred} \circ P_2^3) . To get rid of the reversed argument order, then define \operatorname{Sub} = \operatorname{RSub} \circ (P_2^2, P_1^2) . As a computation example, \begin{align} \operatorname{Sub}(8, 1) &= (\operatorname{RSub} \circ (P_2^2, P_1^2)) (8, 1) && \text{ by Def. } \operatorname{Sub} \\ &= \operatorname{RSub}(1, 8) && \text{ by Def. } \circ, P_2^2, P_1^2 \\ &= \rho(P_1^1, \operatorname{Pred} \circ P_2^3) (S(0), 8) && \text{ by Def. } \operatorname{RSub}, S \\ &= (\operatorname{Pred} \circ P_2^3) (0, \operatorname{RSub}(0, 8), 8) && \text{ by case } \rho(g, h) (S(...), ...) \\ &= \operatorname{Pred}(\operatorname{RSub}(0, 8)) && \text{ by Def. } \circ, P_2^3 \\ &= \operatorname{Pred}(\rho(P_1^1, \operatorname{Pred} \circ P_2^3) (0, 8)) && \text{ by Def. } \operatorname{RSub} \\ &= \operatorname{Pred}(P_1^1(8)) && \text{ by case } \rho(g, h) (0, ...) \\ &= \operatorname{Pred}(8) && \text{ by Def. } P_1^1 \\ &= 7 && \text{ by property of } \operatorname{Pred}. \end{align} As an example for a primitive recursive predicate, the 1-ary function \operatorname{IsZero} shall be defined such that \operatorname{IsZero}(x) = 1 if x = 0 , and \operatorname{IsZero}(x) = 0 otherwise. This can be achieved by defining \operatorname{IsZero} = \rho(C_1^0, C_0^2) . Then \operatorname{IsZero}(0) = \rho(C_1^0, C_0^2)(0) = C_1^0() = 1 , and e.g. \operatorname{IsZero}(8) = \rho(C_1^0, C_0^2)(S(7)) = C_0^2(7, \operatorname{IsZero}(7)) = 0 . Using the property x \leq y \iff x \mathbin{\dot{-}} y = 0 , the 2-ary function \operatorname{Leq} can be defined by \operatorname{Leq} = \operatorname{IsZero} \circ \operatorname{Sub} . Then \operatorname{Leq}(x, y) = 1 if x \leq y , and \operatorname{Leq}(x, y) = 0 otherwise. As a computation example, \begin{align} \operatorname{Leq}(8, 3) &= \operatorname{IsZero}(\operatorname{Sub}(8, 3)) && \text{ by Def. } \operatorname{Leq} \\ &= \operatorname{IsZero}(5) && \text{ by property of } \operatorname{Sub} \\ &= 0 && \text{ by property of } \operatorname{IsZero} \\ \end{align} Once a definition of \operatorname{Leq} is obtained, the converse predicate can be defined as \operatorname{Geq} = \operatorname{Leq} \circ (P_2^2, P_1^2) . Then, \operatorname{Geq}(x, y) = \operatorname{Leq}(y, x) is true (more precisely: has value 1) if and only if x \geq y . The 3-ary if-then-else operator known from programming languages can be defined by \operatorname{If} = \rho(P_2^2, P_3^4) . Then, for arbitrary x , \begin{align} \operatorname{If}(S(x), y, z) &= \rho(P_2^2, P_3^4) (S(x), y, z) && \text{ by Def. } \operatorname{If} \\ &= P_3^4(x, \operatorname{If}(x, y, z), y, z) && \text{ by case } \rho(S(...), ...) \\ &= y && \text{ by Def. } P_3^4 \end{align} and \begin{align} \operatorname{If}(0, y, z) &= \rho(P_2^2, P_3^4) (0, y, z) && \text{ by Def. } \operatorname{If} \\ &= P_2^2(y, z) && \text{ by case } \rho(0, ...) \\ &= z && \text{ by Def. } P_2^2. \end{align} That is, \operatorname{If}(x, y, z) returns the then-part ( y ) if the if-part ( x ) is true, and the else-part ( z ) otherwise. Based on the \operatorname{If} function, it is easy to define logical junctors. For example, defining \operatorname{And} = \operatorname{If} \circ (P_1^2, P_2^2, C_0^2) , one obtains \operatorname{And}(x, y) = \operatorname{If}(x, y, 0) , that is, \operatorname{And}(x, y) is true if and only if both x and y are true (logical conjunction of x and y ). Similarly, \operatorname{Or} = \operatorname{If} \circ (P_1^2, C_1^2, P_2^2) and \operatorname{Not} = \operatorname{If} \circ (P_1^1, C_0^1, C_1^1) lead to appropriate definitions of disjunction and negation: \operatorname{Or}(x, y) = \operatorname{If}(x, 1, y) and \operatorname{Not}(x) = \operatorname{If}(x, 0, 1) . Using the above functions \operatorname{Leq} , \operatorname{Geq} and \operatorname{And} , the definition \operatorname{Eq} = \operatorname{And} \circ (\operatorname{Leq}, \operatorname{Geq}) implements the equality predicate. In fact, \operatorname{Eq}(x, y) = \operatorname{And}(\operatorname{Leq}(x, y), \operatorname{Geq}(x, y)) is true if and only if x equals y . Similarly, the definition \operatorname{Lt} = \operatorname{Not} \circ \operatorname{Geq} implements the predicate "less-than", and \operatorname{Gt} = \operatorname{Not} \circ \operatorname{Leq} implements "greater-than". 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–20 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. Addition: a+b Multiplication: a×b Exponentiation: a b Factorial a! : 0! = 1, a'! = a!×a' pred(a): (Predecessor or decrement): If a > 0 then a−1 else 0 Proper subtraction a ∸ b: If a ≥ b then a−b else 0 Minimum(a 1 , ... a n ) Maximum(a 1 , ... a n ) Absolute difference: | a−b | = def (a ∸ b) + (b ∸ a) ~sg(a): NOT[signum(a)]: If a=0 then 1 else 0 sg(a): signum(a): If a=0 then 0 else 1 a | b: (a divides b): If b=k×a for some k then 0 else 1 Remainder(a, b): the leftover if b does not divide a "evenly". Also called MOD(a, b) a = b: sg | a − b | (Kleene's convention was to represent true by 0 and false by 1; presently, especially in computers, the most common convention is the reverse, namely to represent true by 1 and false by 0, which amounts to changing sg into ~sg here and in the next item) a def a>1 & NOT(Exists c) 1 [ c|a ] p i : the i+1th prime number (a) i : exponent of p i in a: the unique x such that p i x |a & NOT(p i x' |a) lh(a): the "length" or number of non-vanishing exponents in a lo(a, b): (logarithm of a to base b): If a, b > 1 then the greatest x such that b x | a else 0 In the following, the abbreviation x = def x 1 , ... x n ; subscripts may be applied if the meaning requires. #A: A function φ definable explicitly from functions Ψ and constants q 1 , ... q n is primitive recursive in Ψ. #B: The finite sum Σ y ψ(x, y) and product Π y ψ(x, y) are primitive recursive in ψ. #C: A predicate P obtained by substituting functions χ 1 ,..., χ m for the respective variables of a predicate Q is primitive recursive in χ 1 ,..., χ 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 μy y 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 1 , ..., Q m are mutually exclusive predicates (or "ψ(x) shall have the value given by the first clause that applies), is primitive recursive in φ 1 , ..., Q 1 , ... Q m : φ(x) = φ 1 (x) if Q 1 (x) is true, . . . . . . . . . . . . . . . . . . . φ m (x) if Q m (x) is true φ m+1 (x) otherwise #G: If φ satisfies the equation: φ(y,x) = χ(y, COURSE-φ(y; x 2 , ... x n ), x 2 , ... x n then φ is primitive recursive in χ. The value COURSE-φ(y; x 2 to n ) of the course-of-values function encodes the sequence of values φ(0,x 2 to n ), ..., φ(y-1,x 2 to n ) of the original function. For every unary primitive recursive function g, there is an m such that g(n) = f(m,n) for all n, and For every m, the function h(n) = f(m,n) is primitive recursive. Primitive recursive functions with two or more arguments can be encoded as unary primitive recursive functions by using a primitive recursive pairing function with two primitive recursive inverses. f can be explicitly constructed by iteratively repeating all possible ways of creating primitive recursive functions. Thus, it is provably total. One can use a diagonalization argument to show that f is not recursive primitive in itself: had it been such, so would be h(n) = f(n,n)+1. But if this equals some primitive recursive function, there is an m such that h(n) = f(m,n) for all n, and then h(m) = f(m,m), leading to contradiction. However, the set of primitive recursive functions is not the largest recursively enumerable subset of the set of all total recursive functions. For example, the set of provably total functions (in Peano arithmetic) is also recursively enumerable, as one can enumerate all the proofs of the theory. While all primitive recursive functions are provably total, the converse is not true.
Variants
Constant functions
Instead of C_n^k , alternative definitions use just one 0-ary zero function C_0^0 as a primitive function that always returns zero, and build the constant functions from the zero function, the successor function and the composition operator. \begin{align} f(0,x) & = x,\\ f(S(y),x) & = h(y,f(y,x)). \end{align} He proved that the class of all primitive recursive functions can still be obtained in this way. \begin{align} f(0,x_1,\ldots,x_k) & = g(x_1,\ldots,x_k),\\ f(S(y),x_1,\ldots,x_k) & = h(f(y,x_1,\ldots,x_k),x_1,\ldots,x_k). \end{align} Gladstone proved that this rule is enough to generate all primitive recursive functions. Gladstone improved this so that even the combination of these two restrictions, i.e., the pure iteration rule below, is enough: \begin{align} f(0,x) & = x,\\ f(S(y),x) & = h(f(y,x)). \end{align} Further improvements are possible: Severin prove that even the pure iteration rule without parameters, namely \begin{align} f(0) & = 0,\\ f(S(y)) & = h(f(y)), \end{align} suffices to generate all unary primitive recursive functions if we extend the set of initial functions with truncated subtraction x ∸ y. We get all primitive recursive functions if we additionally include + as an initial function.
See also
Grzegorczyk hierarchy Recursion (computer science) Primitive recursive functional Double recursion Primitive recursive set function Primitive recursive ordinal function Tail call
Notes
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378159854 under CC BY-SA 4.0; modifications have been made.