Content deleted Content added
Mearrcteell (talk | contribs) If we don't exclude functions recursively calling themselves, the restriction to for-loops is useless in delimiting the PR functions. Tags: Reverted Visual edit |
|||
Line 1:
{{Short description|Function computable with bounded loops}}
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) and that does not recursively call itself. 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 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.
| |||