Primitive recursive function: Difference between revisions

Revision as of 13:45, 28 February 2024

Revision as of 13:48, 28 February 2024

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]].