Primitive recursive function: Difference between revisions

Revision as of 16:38, 3 February 2024

Latest revision as of 15:58, 14 August 2025

(48 intermediate revisions by 18 users not shown)

Line 1:

{{Short description|Function computable with bounded loops}}

{{CS1 config|mode=cs2}}

In [[computability theory]], a '''primitive recursive function''' is, roughly speaking, a function that can be computed by a [[computer program]] whose [[loop (programming)|loops]] are all [[For loop|"for" loops]] (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict [[subset]] of those [[general recursive function]]s that are also [[total function]]s.

In [[computability theory]], a '''primitive recursive function''' is, roughly speaking, a function that can be computed by a [[computer program]] whose [[loop (programming)|loops]] are all [[For loop|"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 function]]s that are also [[total function]]s.

The importance of primitive recursive functions lies in the fact that most [[computable function]]s that are studied in [[number theory]] (and more generally in mathematics) are primitive recursive. For example, [[addition]] and [[division (mathematics)|division]], the [[factorial]] and [[exponential function]], and the function which returns the ''n''th prime are all primitive recursive.<ref>{{sfn|Brainerd and |Landweber, |1974</ref>}} 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.<ref>{{sfn|Hartmanis, |1989</ref>}} It is hence not particularly easy to devise a [[computable function]] that is ''not'' primitive recursive; some examples are shown in section {{slink||Limitations}} below.

The set of primitive recursive functions is known as [[PR (complexity)|PR]] in [[computational complexity theory]].

Line 13 ⟶ 14:

{{ordered list|start=1

|1=''Constant functions {{mvar|C{{su|b=n|p=<math>C_n^k}}}}</math>'': For each natural number {{mvar|<math>n}}</math> and every {{mvar|<math>k}}</math>, the ''k''-ary constant function, defined by <math>C_n^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ n</math>, is primitive recursive.

| 2=''Successor function'': The 1-ary successor function ''S'', which returns the successor of its argument (see [[Peano postulates]]), that is, <math>S(x) \ \stackrel{\mathrm{def}}{=}\ x + 1</math>, is primitive recursive.

| 3=''Projection function'' <math>P_i^k</math>: For all natural numbers <math>i, k</math> such that <math>1\le i\le k</math>, the ''k''-ary function defined by <math>P_i^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ x_i</math> is primitive recursive.

| 3=''Projection functions'' <math>P_i^k</math>: For all natural numbers <math>i, k</math> such that <math>1\le i\le k</math>, the ''k''-ary function defined by <math>P_i^k(x_1,\ldots,x_k) \ \stackrel{\mathrm{def}}{=}\ x_i</math> is primitive recursive.

}}

More complex primitive recursive functions can be obtained by applying the [[operation (mathematics)|operation]]s given by these axioms:

{{ordered list|start=4

| 4=''Composition operator'' <math>\circ\,</math> (also called the ''substitution operator''): Given an ''m''-ary function <math>h(x_1,\ldots,x_m)\,</math> and ''m'' ''k''-ary functions <math>g_1(x_1,\ldots,x_k),\ldots,g_m(x_1,\ldots, x_k)</math>: <math display="block">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)).</math> For <math>m=1</math>, the ordinary [[function composition]] <math>h \circ g_1</math> is obtained.

| 5=''Primitive recursion operator'' {{mvar|&rho;}}: Given the ''k''-ary function <math>g(x_1,\ldots,x_k)\,</math> and the (''k''&nbsp;+&nbsp;2)-ary function <math>h(y,z,x_1,\ldots,x_k)\,</math>:<math display="block">\begin{align}

| 5=''Primitive recursion operator'' <math>\rho</math>: Given the ''k''-ary function <math>g(x_1,\ldots,x_k)\,</math> and the <math>(k+2)</math>-ary function <math>h(y,z,x_1,\ldots,x_k)\,</math>:

:<math display="block">\begin{align}

\rho(g, h) &\ \stackrel{\mathrm{def}}{=}\ f, \quad\text{where the }(k+1)\text{-ary function } f \text{ is defined by}\\

f(0y, x_1, \ldotsdots, x_k) &= g(x_1,\ldots,x_k) \\begin{cases}

g(x_1, \dots, x_k) & \text{if } y=0 \\

f(S(y),x_1,\ldots,x_k) &= h(y,f(y,x_1,\ldots,x_k),x_1,\ldots,x_k).\end{align}</math>

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}</math>

''Interpretation:''

The function&nbsp;'' <math>f''</math> acts as a [[for loop|for-loop]] from <math>0</math> up to the value of its first argument. The rest of the arguments for&nbsp;'' <math>f''</math>, denoted here with ''x''<sub>1</submath>x_1,&nbsp;...\ldots,&nbsp;''x''<sub>''k''x_k</submath>, 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 ''<math>g''</math> and ''<math>h''</math> on the right-hand side of the equations that define ''<math>f''</math> represent the body of the loop, which performs calculations. The function&nbsp;'' <math>g''</math> is used only once to perform initial calculations. Calculations for subsequent steps of the loop are performed by&nbsp;'' <math>h''</math>. The first parameter of&nbsp;'' <math>h''</math> is fed the "current" value of the for-loop's index. The second parameter of&nbsp;'' <math>h''</math> is fed the result of the for-loop's previous calculations, from previous steps. The rest of the parameters for&nbsp;'' <math>h''</math> are those immutable initial conditions for the for-loop mentioned earlier. They may be used by&nbsp;'' <math>h''</math> to perform calculations but they will not themselves be altered by&nbsp;'' <math>h''</math>.

}}

The '''primitive recursive functions''' are the basic functions and those obtained from the basic functions by applying these operations a finite number of times.

=== Primitive-recursiveness of vector-valued functions ===

A (vector-valued) function <math>f : \mathbb{N}^m \to \mathbb{N}^n</math> is primitive recursive if it can be written as

:<math>f(x_1, \dots, x_m) = (f_1(x_1, \dots, x_m), \dots, f_n(x_1, \dots, x_m))</math>

where each component <math>f_i : \mathbb{N}^m \to \mathbb{N}</math> is a (scalar-valued) primitive recursive function.<ref>{{harvtxt|PlanetMath}}</ref>

== Examples ==

Line 47 ⟶ 61:

|<math>S \circ S</math> is a 1-ary function that adds 2 to its input, <math>(S \circ S)(x) = x+2</math>.

|<math>S \circ C_0^1</math> is a 1-ary function which returns 1 for every input: <math>(S \circ C_0^1)(x) = S(C_0^1(x)) = S(0) = 1</math>. That is, <math>S \circ C_0^1</math> and <math>C_1^1</math> are the same function: <math>S \circ C_0^1 = C_1^1</math>. In a similar way, every <math>C_n^1k</math> can be expressed as a composition of appropriately many <math>S</math> and <math>C_0^k</math>. Moreover, <math>C_0^k</math> equals <math>C_0^1 \circ P_1^k</math>, since <math>C_0^k(x_1,\ldots,x_k) = 0 = C_0^1(x_1) = C_0^1(P_1^k(x_1,\ldots,x_k)) = (C_0^1 \circ P_1^k)(x_1,\ldots,x_k)</math>. For these reasons, some authors<ref>E.g.: {{citation | author=Henk Barendregt | author-link=Henk Barendregt | contribution=Functional Programming and Lambda Calculus | pages=321&ndash;364 | isbn=0-444-88074-7 | editor=Jan van Leeuwen | editor-link=Jan van Leeuwen | title=Formal Models and Semantics | publisher=Elsevier | series=Handbook of Theoretical Computer Science | volume=B | year=1990}} Here: 2.2.6 ''initial functions'', Def.2.2.7 ''primitive recursion'', p.331-332.</ref> define <math>C_n^k</math> only for <math>n = 0</math> and <math>k = 1</math>.

}}

Line 103 ⟶ 117:

===Truncated subtraction===

The limited subtraction function (also called "[[monus]]", and denoted "<math>\stackrel.mathbin{\dot{-}}</math>") is definable from the predecessor function. It satisfies the equations

:<math>\begin{array}{rcll}

y \stackrel.mathbin{\dot{-}} 0 & = & y & \text{and} \\

y \stackrel.mathbin{\dot{-}} S(x) & = & Pred(y \stackrel.mathbin{\dot{-}} x) & . \\

\end{array}</math>

Since the recursion runs over the second argument, we begin with a primitive recursive definition of the reversed subtraction, <math>RSub(y,x) = x \stackrel.mathbin{\dot{-}} y</math>. Its recursion then runs over the first argument, so its primitive recursive definition can be obtained, similar to addition, as <math>RSub = \rho(P_1^1, Pred \circ P_2^3)</math>. To get rid of the reversed argument order, then define <math>Sub = RSub \circ (P_2^2,P_1^2)</math>. As a computation example,

:<math>\begin{array}{lll}

& Sub(8,1) \\

Line 124 ⟶ 138:

=== Converting predicates to numeric functions ===

In some settings it is natural to consider primitive recursive functions that take as inputs tuples that mix numbers with [[truth value]]s (that is ''<math>t''</math> for true and ''<math>f''</math> for false),{{Citation needed|date=January 2025 |reason=Kleene never considers mixed domains - see p. 226 where he lists the 4 types of functions he considers. Using N to represent the naturals, and T to represent the truth values: (a) N to N (b) N to T (c) T oto T (d) T to N}} or that produce truth values as outputs.<ref>{{sfn|Kleene [1952 |1974|pp.&nbsp;=226–227]</ref>}} This can be accomplished by identifying the truth values with numbers in any fixed manner. For example, it is common to identify the truth value ''<math>t''</math> with the number <math>1</math> and the truth value ''<math>f''</math> with the number <math>0</math>. Once this identification has been made, the [[indicator function|characteristic function]] of a set ''<math>A''</math>, which always returns <math>1</math> or <math>0</math>, can be viewed as a predicate that tells whether a number is in the set ''<math>A''</math>. Such an identification of predicates with numeric functions will be assumed for the remainder of this article.

=== Predicate "Is zero" ===

As an example for a primitive recursive predicate, the 1-ary function <math>IsZero</math> shall be defined such that <math>IsZero(x) = 1</math> if <math>x = 0</math>, and

<math>IsZero(x) = 0</math>, otherwise. This can be achieved by defining <math>IsZero = \rho(C_1^0,C_0^2)</math>. Then, <math>IsZero(0) = \rho(C_1^0,C_0^2)(0) = C_1^0(0) = 1</math> and e.g. <math>IsZero(8) = \rho(C_1^0,C_0^2)(S(7)) = C_0^2(7,IsZero(7)) = 0</math>.

=== Predicate "Less or equal" ===

Using the property <math>x \leq y \iff x \stackrel.mathbin{\dot{-}} y = 0</math>, the 2-ary function <math>Leq</math> can be defined by <math>Leq = IsZero \circ Sub</math>. Then <math>Leq(x,y) = 1</math> if <math>x \leq y</math>, and <math>Leq(x,y) = 0</math>, otherwise. As a computation example,

:<math>\begin{array}{lll}

& Leq(8,3) \\

Line 177 ⟶ 191:

=== Other operations on natural numbers ===

[[Exponentiation]] and [[primality test]]ing are primitive recursive. Given primitive recursive functions ''<math>e''</math>, ''<math>f''</math>, ''<math>g''</math>, and ''<math>h''</math>, a function that returns the value of ''<math>g''</math> when ''<math>e''≤'' \leq f''</math> and the value of ''<math>h''</math> otherwise is primitive recursive.

=== Operations on integers and rational numbers ===

Line 184 ⟶ 198:

=== Some common primitive recursive functions ===

The following examples and definitions are from {{harvnb|Kleene|1974|pp=222–231}}. Many appear with proofs. Most also appear with similar names, either as proofs or as examples, in {{harvnb|Boolos|Burgess|Jeffrey|2002|pp=63–70}} they add the logarithm lo(x, y) or lg(x, y) depending on the exact derivation.

{{cleanup|section|reason=Remove functions and explanations that appear above|date=November 2021}}

:The following examples and definitions are from Kleene (1952) pp.&nbsp;223–231. Many appear with proofs. Most also appear with similar names, either as proofs or as examples, in Boolos-Burgess-Jeffrey 2002 pp.&nbsp;63–70; they add 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:

# ''functions'' for short: "number-theoretic functions" from { 0, 1, 2, ...} to { 0, 1, 2, ...},

# ''predicates'': from { 0, 1, 2, ...} to truth values { t =true, f =false },

# ''propositional connectives'': from truth values { t, f } to truth values { t, f },

# ''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 ~sg( ) 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–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 number]]s.

Line 239 ⟶ 246:

* #G: If φ satisfies the equation:

:: φ(y,'''x''') = χ(y, COURSE-φ(y; x₂, ... x_n ), x₂, ... 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.

== Use in first-order Peano arithmetic ==

{{expert needed|computer science|section|reason=properly explain the purpose of using the β function (the text only explains *how* it is used, not *what for* - I guess in some Gödelian (un)computability proof)|date=November 2021}}

In [[first-order logic|first-order]] [[Peano arithmetic]], there are infinitely many variables (0-ary symbols) but no [[arity|k-ary]] non-logical symbols with k>0 other than S, +, *, and ≤. Thus in order to define primitive recursive functions one has to use the following trick by Gödel.

By using a [[Gödel numbering for sequences]], for example [[Gödel's β function]], any finite sequence of numbers can be encoded by a single number. Such a number can therefore represent the primitive recursive function until a given n.

Let ''h'' be a 1-ary primitive recursion function defined by:

:<math> h(0) = C</math>

:<math> h(n+1) = g(n,h(n))</math>

where C is a constant and ''g'' is an already defined function.

Using Gödel's β function, for any sequence of natural numbers (k₀, k₁, ..., k_n), there are natural numbers b and c such that, for every i ≤ n, β(b, c, i) = k_i. We may thus use the following formula to define ''h''; more precisely, ''m''=''h''(''n'') is a shorthand for the following:

:<math>\exists b: \exists c: \beta(b, c, 0) = C \land \forall i: (i<n) \rightarrow (\beta(b, c, i+1) = g(i,\beta(b, c, i))) \land (m = \beta(b, c, n))</math>

and the equating to ''g'', being already defined, is in fact shorthand for some other already defined formula (as is β, whose formula is given [[Gödel's β function|here]]).

The generalization to any k-ary primitive recursion function is trivial.

== Elimination of parameters ==

{{expert needed|computer science|section|reason=properly explain the purpose of removing parameters (the text only explains *how* it is used, not *what for* - I guess in some Gödelian (un)computability proof)|date=November 2021}}

The primitive recursion schema as given may be replaced by one which makes use of fewer parameters. Let <math>w</math> be an elementary pairing function, and <math>\pi_1,\pi_2</math> be its projection functions for inversion.

Theorem: Any function constructible via the clauses of primitive recursion using the standard primitive recursion schema is constructible when the schema is replaced with the following.

*<math>f'(x,0) = g'(x)</math>

*<math>f'(x,y+1) = h'(f'(x,y))</math>

This is proven by providing two intermediate schemata for primitive recursion, starting with a function defined via the standard schema, and translating the definition into terms of each intermediate schema and finally into terms of the above schema. The first intermediate schemata is as follows:

*<math>f_1(x,0) = g_1(x)</math>

*<math>f_1(x,y+1) = h_1(x,y,f_1(x,y))</math>

Translation of the standard definition of a primitive recursive function to the intermediate schema is done inductively, where an elementary pairing function <math>w</math> is used to reinterpret the definition of a <math>k+1</math>-ary primitive recursive function into a <math>k</math>-ary primitive recursive function, terminating the induction at <math>k=1</math>.

The second intermediate schema is as follows, with the <math>x</math> parameter eliminated.

*<math>f_2(x,0)=g_2(x)</math>

*<math>f_2(x,y+1)=h_2(y,f_2(x,y))</math>

Translation to it is accomplished by pairing <math>x</math> and <math>f_1(x,y)</math> together to use one parameter for handling both, namely by setting <math>g_2(x)=w(x,g_1(x))</math>, <math>h_2(x,z)=w(\pi_1 z,h_1(\pi_1 z, x, \pi_2 z))</math>, and recovering <math>f_1(x,y)</math> from these paired images by taking <math>\pi_2(f_2(x,y))</math>.

Finally, translation of the intermediate schema into the parameter-eliminated schema is done with a similar pairing and unpairing of <math>y</math> and <math>f_2(x,y)</math>. Composing these three translations gives a definition in the original parameter-free schema.<ref>H. E. Rose, ''Subrecursive Functions and Hierarchies'' (1984), pp.33--34. Oxford Logic Guides: 9, Oxford University Press, ISBN 0-19-853189-3.</ref>

This allows primitive recursion to be formalized in Peano arithmetic, due to its lack of extra ''n''-ary function symbols.{{citation needed|date=May 2023}}

== Relationship to recursive functions ==

Line 300 ⟶ 264:

Primitive recursive functions tend to correspond very closely with our intuition of what a computable function must be. Certainly the initial functions are intuitively computable (in their very simplicity), and the two operations by which one can create new primitive recursive functions are also very straightforward. However, the set of primitive recursive functions does not include every possible total computable function—this can be seen with a variant of [[Cantor's diagonal argument]]. This argument provides a total computable function that is not primitive recursive. A sketch of the proof is as follows:

{{block indent|The primitive recursive functions of one argument (i.e., unary functions) can be [[Recursively enumerable set|computably enumerated]]. This enumeration uses the definitions of the primitive recursive functions (which are essentially just expressions with the composition and primitive recursion operations as operators and the basic primitive recursive functions as atoms), and can be assumed to contain every definition once, even though a same ''function'' will occur many times on the list (since many definitions define the same function; indeed simply composing by the [[identity function]] generates infinitely many definitions of any one primitive recursive function). This means that the {{mvar|''<math>n''}}</math>-th definition of a primitive recursive function in this enumeration can be effectively determined from {{mvar|''<math>n''}}</math>. Indeed if one uses some [[Gödel numbering]] to encode definitions as numbers, then this {{mvar|''<math>n''}}</math>-th definition in the list is computed by a primitive recursive function of {{mvar|''<math>n''}}</math>. Let {{math|''f''<submath>''n''f_n</submath>}} denote the unary primitive recursive function given by this definition.

Now define the "evaluator function" {{mvar|''<math>ev''}}</math> with two arguments, by {{<math|''>ev''(''i'',''j'') {{=}} ''f''_''i''f_i(''j'')}}</math>. Clearly {{<math|''>ev''}}</math> is total and computable, since one can effectively determine the definition of {{math|''f''<submath>''i''f_i</submath>}}, and being a primitive recursive function {{math|''f''<submath>''i''f_i</submath>}} is itself total and computable, so {{<math|''f''_''i''f_i(''j'')}}</math> is always defined and effectively computable. However a diagonal argument will show that the function {{mvar|''<math>ev''}}</math> of two arguments is not primitive recursive.

Suppose {{mvar|''<math>ev''}}</math> were primitive recursive, then the unary function {{mvar|''<math>g''}}</math> defined by {{<math|''>g''(''i'') {{=}} S(''ev''(''i'',''i''))}}</math> would also be primitive recursive, as it is defined by composition from the successor function and {{mvar|''<math>ev''}}</math>. But then {{mvar|''<math>g''}}</math> occurs in the enumeration, so there is some number {{mvar|''<math>n''}}</math> such that {{<math|''>g'' {{=}} ''f''<sub>''n''f_n</submath>}}. But now {{<math|''>g''(''n'') {{=}} S(''ev''(''n'',''n'')) {{=}} S(''f''_''n''f_n(''n'')) {{=}} S(''g''(''n''))}}</math> gives a contradiction.}}

This argument can be applied to any class of computable (total) functions that can be enumerated in this way, as explained in the article [[Machine that always halts]]. Note however that the ''partial'' computable functions (those that need not be defined for all arguments) can be explicitly enumerated, for instance by enumerating Turing machine encodings.

Line 317 ⟶ 281:

===Constant functions===

Instead of <math>C_n^k</math>,

alternative definitions use just one 0-ary ''zero function'' <math>C_0^0</math> as a primitive function that always returns zero, and built the constant functions from the zero function, the successor function and the composition operator.{{Citation needed|date=July 2025}}

=== Weak primitive recursion ===

The 1-place predecessor function is primitive recursive, see section [[#Predecessor]]. Fischer, Fischer & Beigel{{sfn|Fischer|Fischer|Beigel|1989}} removed the implicit predecessor from the recursion rule, replacing it by the weaker rule

:<math>

\begin{array}{lcl}

f (0, x_1, \ldots, x_k) & = & g (x_1, \ldots, x_k) & \text{and} \\

f (S(y), x_1, \ldots, x_k) & = & h (S(y), f (y, x_1, \ldots, x_k), x_1, \ldots, x_k)

\end{array}

</math>

They proved that the predecessor function still could be defined, and hence that "weak" primitive recursion also defines the primitive recursive functions.

=== Iterative functions ===

Robinson{{sfn|Robinson|1947}} considered various restrictions of the recursion rule. One is the so-called ''iteration rule'' where the function ''h'' does not have access to the parameters ''x_i'' (in this case, we may assume without loss of generality that the function ''g'' is just the identity, as the general case can be obtained by substitution):

Weakening this even further by using functions <math>h</math> of arity ''k''+1, removing <math>y</math> and <math>S(y)</math> from the arguments of <math>h</math> completely, we get the ''iteration rule'':

:<math>\begin{align} f(0,x) & = x,\\

f(S(y),x) & = h(y,f(y,x)). \end{align}</math>

<math>\begin{array}{lcll} f(0,x_1,\ldots,x_k) & = & g(x_1,\ldots,x_k) &\textrm{and} \\ f(S(y),x_1,\ldots,x_k) & = & h(f(y,x_1,\ldots,x_k),x_1,\ldots,x_k) \end{array}</math>

He proved that the class of all primitive recursive functions can still be obtained in this way.

=== Pure recursion ===

The class of iterative functions is defined the same way as the class of primitive recursive functions except with this weaker rule. These are conjectured to be a proper subset of the primitive recursive functions.{{sfn|Fischer|Fischer|Beigel|1989}}

Another restriction considered by Robinson{{sfn|Robinson|1947}} is ''pure recursion'', where ''h'' does not have access to the induction variable ''y'':

:<math>\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}</math>

Gladstone{{sfn|Gladstone|1967}} proved that this rule is enough to generate all primitive recursive functions. Gladstone{{sfn|Gladstone|1971}} improved this so that even the combination of these two restrictions, i.e., the ''pure iteration'' rule below, is enough:

:<math>\begin{align} f(0,x) & = x,\\

f(S(y),x) & = h(f(y,x)). \end{align}</math>

Further improvements are possible: Severin{{sfn|Severin|2008}} prove that even the pure iteration rule ''without parameters'', namely

:<math>\begin{align} f(0) & = 0,\\

f(S(y)) & = h(f(y)), \end{align}</math>

suffices to generate all [[unary operation|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.

=== Additional primitive recursive forms ===

Line 348 ⟶ 313:

An example of a primitive recursive programming language is one that contains basic arithmetic operators (e.g. + and −, or ADD and SUBTRACT), conditionals and comparison (IF-THEN, EQUALS, LESS-THAN), and bounded loops, such as the basic [[for loop]], where there is a known or calculable upper bound to all loops (FOR i FROM 1 TO n, with neither i nor n modifiable by the loop body). No control structures of greater generality, such as [[while loop]]s or IF-THEN plus [[GOTO]], are admitted in a primitive recursive language.

The [[LOOP (programming language)|LOOP language]], introduced in a 1967 paper by [[Albert R. Meyer]] and [[Dennis M. Ritchie]],<ref>{{cite conferencecitation

| doi=10.1145/800196.806014

| titlecontribution=The complexity of loop programs

| last1=Meyer

| first1=Albert R.

Line 357 ⟶ 322:

| first2=Dennis M.

| authorlink2=Dennis Ritchie

| conferencetitle=ACM '67: Proceedings of the 1967 22nd national conference

| year=1967

| pages=465–469

| doi-access=free

}}</ref> is such a language. Its computing power coincides with the primitive recursive functions. A variant of the LOOP language is [[Douglas Hofstadter]]'s [[BlooP and FlooP|BlooP]] in ''[[Gödel, Escher, Bach]]''. Adding unbounded loops (WHILE, GOTO) makes the language [[general recursive function|general recursive]] and [[Turing completeness|Turing-complete]], as are all real-world computer programming languages.

Line 375 ⟶ 341:

== History ==

[[Recursive definition]]s had been used more or less formally in mathematics before, but the construction of primitive recursion is traced back to [[Richard Dedekind]]'s theorem 126 of his ''Was sind und was sollen die Zahlen?'' (1888). This work was the first to give a proof that a certain recursive construction defines a unique function.<ref name="Smith2013">{{cite bookcitation|author=Peter Smith|title=An Introduction to Gödel's Theorems|year=2013|publisher=Cambridge University Press|isbn=978-1-107-02284-3|pages=98–99|edition=2nd |url=https://www.logicmatters.net/igt/}}</ref><ref name="Tourlakis2003">{{cite bookcitation|author=George Tourlakis|title=Lectures in Logic and Set Theory: Volume 1, Mathematical Logic|year=2003|publisher=Cambridge University Press|isbn=978-1-139-43942-8|page=129}}</ref><ref name="Downey2014">{{cite bookcitation|editor=Rod Downey|title=Turing's Legacy: Developments from Turing's Ideas in Logic|year=2014|publisher=Cambridge University Press|isbn=978-1-107-04348-0|page=474}}</ref>

[[Primitive recursive arithmetic]] was first proposed by [[Thoralf Skolem]]<ref>[[Thoralf Skolem]] (1923) "The foundations of elementary arithmetic" in [[Jean van Heijenoort]], translator and ed. (1967) ''From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931''. Harvard Univ. Press: 302-33.</ref> in 1923.

Line 394 ⟶ 360:

== References ==

* Brainerd, W.S., Landweber, L.H. (1974), ''Theory of Computation'', Wiley, {{isbn|0-471-09585-0}}

*{{cite book

* {{cite journal | last1=Fischer | first1=Michael J. | last2=Fischer | first2=Robert P. | last3=Beigel | first3=Richard | title=Primitive Recursion without Implicit Predecessor | journal=[[ACM SIGACT|ACM SIGACT News]] | date=November 1989 | volume=20| issue=4| pages=87–91 | url=https://doi.org/10.1145/74074.74089 | doi=10.1145/74074.74089| s2cid=33850327 }}

| last1 = Boolos

* [[Juris Hartmanis]] (1989), “Overview of computational Complexity Theory” in J. Hartmanis (ed.), Computational Complexity Theory, Providence: American Mathematical Society, pp. 1–17.

| first1 = George

* [[Robert I. Soare]], ''Recursively Enumerable Sets and Degrees'', Springer-Verlag, 1987. {{isbn|0-387-15299-7}}

| author-link = George Boolos

* [[Stephen Kleene]] (1952) ''Introduction to Metamathematics'', North-Holland Publishing Company, New York, 11th reprint 1971: (2nd edition notes added on 6th reprint). In Chapter XI. General Recursive Functions §57

| last2 = Burgess

* [[George Boolos]], [[John P. Burgess|John Burgess]], [[Richard Jeffrey]] (2002), ''Computability and Logic: Fourth Edition'', Cambridge University Press, Cambridge, UK. Cf pp.&nbsp;70–71.

| first2 = John

* Robert I. Soare 1995 ''Computability and Recursion'' http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

| author2-link = John P. Burgess

* Daniel Severin 2008, ''Unary primitive recursive functions'', J. Symbolic Logic Volume 73, Issue 4, pp.&nbsp;1122–1138 [https://arxiv.org/abs/cs/0603063v3 arXiv] [https://projecteuclid.org/euclid.jsl/1230396909 projecteuclid] {{doi|10.2178/jsl/1230396909}} {{JSTOR|275903221}}

| last3 = Jeffrey

| first3 = Richard C.

| author3-link = Richard Jeffrey

| title = Computability and Logic

| publisher = Cambridge University Press

| edition = 4th

| date = 2002

| isbn = 9780521007580

}}

*{{cite book

| last1 = Brainerd

| first1 = W.S.

| last2 = Landweber

| first2 = L.H.

| year = 1974

| title = Theory of Computation

| publisher = Wiley

| isbn = 0471095850

}}

*{{cite journal

| last = Gladstone

| first = M. D.

| doi = 10.2307/2270177

| journal = [[The Journal of Symbolic Logic]]

| mr = 224460

| pages = 505–508

| title = A reduction of the recursion scheme

| volume = 32

| year = 1967

| issue = 4

| jstor = 2270177

}}

*{{cite journal

| last = Gladstone

| first = M. D.

| doi = 10.2307/2272468

| journal = The Journal of Symbolic Logic

| mr = 305993

| pages = 653–665

| title = Simplifications of the recursion scheme

| volume = 36

| year = 1971

| issue = 4

| jstor = 2272468

}}

*{{cite book

| last = Hartmanis

| first = Juris

| author-link = Juris Hartmanis

| year = 1989

| chapter = Overview of Computational Complexity Theory

| title = Computational Complexity Theory

| publisher = American Mathematical Society

| pages = 1–17

| isbn = 978-0-8218-0131-4

| series = Proceedings of Symposia in Applied Mathematics

| volume = 38

| mr = 1020807

}}

*{{cite book

| last = Kleene

| first = Stephen Cole

| author-link = Stephen Cole Kleene

| year = 1974

| orig-year = 1952

| title = Introduction to Metamathematics

| chapter = Chapter XI. General Recursive Functions §57

| edition = 7th reprint; 2nd

| publisher = [[North-Holland Publishing Company]]

| oclc = 3757798

| isbn = 0444100881

}}

*{{cite web

| author = PlanetMath

| title = primitive recursive vector-valued function

| url = https://planetmath.org/primitiverecursivevectorvaluedfunction

| access-date = 2025-07-04

}}

*{{cite book

| last = Rogers

| first = Hartley Jr.

| title = Theory of Recursive Functions and Effective Computability

| publisher = [[MIT Press]]

| year = 1987

| orig-year = 1967

| edition = Reprint

| isbn = 9780262680523

}}

*{{cite journal

| last = Robinson

| first = Raphael M.

| doi = 10.1090/S0002-9904-1947-08911-4

| journal = [[Bulletin of the American Mathematical Society]]

| mr = 22536

| pages = 925–942

| title = Primitive recursive functions

| volume = 53

| year = 1947

| issue = 10

| doi-access = free

}}

*{{cite journal

| last = Severin

| first = Daniel E.

| arxiv = cs/0603063

| doi = 10.2178/jsl/1230396909

| issue = 4

| journal = The Journal of Symbolic Logic

| jstor = 275903221

| mr = 2467207

| pages = 1122–1138

| title = Unary primitive recursive functions

| volume = 73

| year = 2008

}}

*{{cite book

| last = Soare

| first = Robert I.

| author-link = Robert I. Soare

| isbn = 0-387-15299-7

| title = Recursively Enumerable Sets and Degrees

| publisher = Springer-Verlag

| year = 1987

}}

*{{cite journal

| last = Soare

| first = Robert I.

| author-link = Robert I. Soare

| doi = 10.2307/420992

| volume = 2

| issue = 3

| journal = The Bulletin of Symbolic Logic

| mr = 1416870

| pages = 284–321

| title = Computability and recursion

| url = https://scholar.archive.org/work/ruvjr6nkyre4nfxjdme2refpwe

| year = 1996

| jstor = 420992

}}

{{Mathematical logic}}