Primitive recursive function: Difference between revisions

Revision as of 12:10, 21 January 2025

Revision as of 08:13, 27 January 2025

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.

Line 51 ⟶ 52:

|<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^k</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.: {{cite bookcitation | 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 303 ⟶ 304:

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 312 ⟶ 313:

| first2=Dennis M.

| authorlink2=Dennis Ritchie

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

| year=1967

| doi-access=free

Line 330 ⟶ 331:

== 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 349 ⟶ 350:

== References ==

* {{cite bookcitation|last1=Brainerd |first1=W.S. |last2=Landweber |first2=L.H. |year=1974 |title=Theory of Computation |publisher=Wiley |isbn=0471095850}}

* {{cite bookcitation|last=Hartmanis |first=Juris |author-link=Juris Hartmanis |year=1989|chapter=Overview of Computational Complexity Theory |title=Computational Complexity Theory |publisher=American Mathematical Society|pp=1-17 |isbn=978-0-8218-0131-4 |series=Proceedings of Symposia in Applied Mathematics |volume=38 |mr=1020807}}

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

* {{Cite bookcitation |last=Kleene |first=Stephen Cole |author-link=Stephen Cole Kleene |year=1952|title=Introduction to Metamathematics |edition=7th [1974] reprint; 2nd |publisher=[[North-Holland Publishing Company]] |oclc=3757798 |isbn=0444100881}} Chapter XI. General Recursive Functions §57

*{{citation |author-link=George Boolos |first1=George |last1=Boolos |author2-link=John P. Burgess |first2=John |last2=Burgess |author3-link=Richard Jeffrey |first3=Richard |last3=Jeffrey |title=Computability and Logic |publisher=Cambridge University Press |edition=4th |date=2002 |isbn=9780521007580 |pages=70–71}}

*{{citation

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

| last = Soare | first = Robert I.

* 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}}

| doi = 10.2307/420992

* Raphael M. Robinson (1947), ''Primitive recursive functions'', Bulletin of the AMS 53, no. 10, pp. 925–942.

| issue = 3

* M. D. Gladstone (1967), ''A reduction of the recursion scheme'', Journal of Symbolic Logic 32, no. 4, pp. 505–508.

| journal = The Bulletin of Symbolic Logic

* M. D. Gladstone (1971), ''Simplifications of the recursion scheme'', Journal of Symbolic Logic 36, no. 4, pp. 653–665.

| mr = 1416870

| pages = 284–321

| title = Computability and recursion

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

| volume = 2

| year = 1996}}

*{{citation

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

*{{citation

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

*{{citation

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

*{{citation

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

{{Mathematical logic}}