Content deleted Content added
→Some common primitive recursive functions: rm out-of-scope explanations that the truth values can be denoted 0 and 1. also rm tag requiring this removal |
typo: if it were bounded by a primitive recursive function, it would be also primitive recursive Tag: Reverted |
||
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 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.
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>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 non-primitive recursive function of the input size.<ref>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]].
| |||