Primitive recursive function: Difference between revisions

Revision as of 21:42, 4 January 2025

Revision as of 21:52, 4 January 2025

Line 2:

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 128:

=== 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 |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" ===

Line 348:

== References ==

* {{cite book|last1=Brainerd, |first1=W.S., |last2=Landweber, |first2=L.H. (|year=1974), ''|title=Theory of Computation'', |publisher=Wiley, {{isbn|0-471-09585-0isbn=0471095850}}

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

* [[Juris{{cite book|last=Hartmanis]] (1989),|first=Juris |author-link=Juris Hartmanis “Overview|chapter=Overview of computationalComputational Complexity Theory” in J. Hartmanis (ed.),Theory |title=Computational Complexity Theory, Providence: |publisher=American Mathematical Society, |pp.=1-17 |isbn=978-0-8218-0131-4 |series=Proceedings of Symposia in Applied Mathematics 1–17.|volume=38 |mr=1020807}}

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

* {{Cite book |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