Primitive recursive function: Difference between revisions

Revision as of 09:01, 23 June 2024

Latest revision as of 15:58, 14 August 2025

(32 intermediate revisions by 15 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 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 25 ⟶ 26:

| 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'' <math>\rho</math>: Given the ''k''-ary function <math>g(x_1,\ldots,x_k)\,</math> and the <math>(''k''&nbsp;+&nbsp;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 <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 <math>f</math>, denoted here with <math>x_1,\ldots,x_k</math>, 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 <math>g</math> is used only once to perform initial calculations. Calculations for subsequent steps of the loop are performed by <math>h</math>. The first parameter of <math>h</math> is fed the "current" value of the for-loop's index. The second parameter of <math>h</math> is fed the result of the for-loop's previous calculations, from previous steps. The rest of the parameters for <math>h</math> are those immutable initial conditions for the for-loop mentioned earlier. They may be used by <math>h</math> to perform calculations but they will not themselves be altered by <math>h</math>.

Line 34 ⟶ 39:

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 51 ⟶ 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 107 ⟶ 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 128 ⟶ 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 181 ⟶ 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 188 ⟶ 198:

=== Some common primitive recursive functions ===

The following examples and definitions are from {{harvnb|Kleene (1952) |1974|pp.&nbsp;223–231=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.&nbsp;=63–70;}} they add the logarithm lo(x, y) or lg(x, y) depending on the exact derivation.

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 271 ⟶ 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 302 ⟶ 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 311 ⟶ 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 329 ⟶ 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 348 ⟶ 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}}