Editing Primitive recursive function (section)

==Variants==
===Constant functions===
Instead of <math>C_n^k</math>,
alternative definitions use just one 0-ary ''zero function'' <math>C_0^0</math> as a primitive function that always returns zero, and built the constant functions from the zero function, the successor function and the composition operator.

=== Iterative functions ===
Robinson{{sfn|Robinson|1947}} considered various restrictions of the recursion rule. One is the so-called ''iteration rule'' where the function ''h'' does not have access to the parameters ''x<sub>i</sub>'' (in this case, we may assume without loss of generality that the function ''g'' is just the identity, as the general case can be obtained by substitution):
:<math>\begin{align} f(0,x) & = x,\\
 f(S(y),x) & = h(y,f(y,x)). \end{align}</math>
He proved that the class of all primitive recursive functions can still be obtained in this way.

=== Pure recursion ===
Another restriction considered by Robinson{{sfn|Robinson|1947}} is ''pure recursion'', where ''h'' does not have access to the induction variable ''y'':
:<math>\begin{align} f(0,x_1,\ldots,x_k) & = g(x_1,\ldots,x_k),\\
 f(S(y),x_1,\ldots,x_k) & = h(f(y,x_1,\ldots,x_k),x_1,\ldots,x_k). \end{align}</math>
Gladstone{{sfn|Gladstone|1967}} proved that this rule is enough to generate all primitive recursive functions. Gladstone{{sfn|Gladstone|1971}} improved this so that even the combination of these two restrictions, i.e., the ''pure iteration'' rule below, is enough:
:<math>\begin{align} f(0,x) & = x,\\
 f(S(y),x) & =  h(f(y,x)). \end{align}</math>
Further improvements are possible: Severin{{sfn|Severin|2008}} prove that even the pure iteration rule ''without parameters'', namely
:<math>\begin{align} f(0) & = 0,\\
 f(S(y)) & =  h(f(y)), \end{align}</math>
suffices to generate all [[unary operation|unary]] primitive recursive functions if we extend the set of initial functions with truncated subtraction ''x ∸ y''. We get ''all'' primitive recursive functions if we additionally include + as an initial function.

=== Additional primitive recursive forms ===

Some additional forms of recursion also define functions that are in fact
primitive recursive.  Definitions in these forms may be easier to find or
more natural for reading or writing. [[Course-of-values recursion]] defines primitive recursive functions. Some forms of [[mutual recursion]] also define primitive recursive functions.

The functions that can be programmed in the [[LOOP (programming language)|LOOP programming language]] are exactly the primitive recursive functions. This gives a different characterization of the power of these functions. The main limitation of the LOOP language, compared to a [[Turing-complete language]], is that in the LOOP language the number of times that each loop will run is specified before the loop begins to run.

=== Computer language definition ===

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>{{citation
| doi=10.1145/800196.806014
| contribution=The complexity of loop programs
| last1=Meyer
| first1=Albert R.
| authorlink1=Albert R. Meyer
| last2=Ritchie
| first2=Dennis M.
| authorlink2=Dennis Ritchie
| title=ACM '67: Proceedings of the 1967 22nd national conference
| year=1967
| pages=465–469
| doi-access=free
}}</ref> is such a language. Its computing power coincides with the primitive recursive functions. A variant of the LOOP language is [[Douglas Hofstadter]]'s [[BlooP and FlooP|BlooP]] in ''[[Gödel, Escher, Bach]]''. Adding unbounded loops (WHILE, GOTO) makes the language [[general recursive function|general recursive]] and [[Turing completeness|Turing-complete]], as are all real-world computer programming languages.

The definition of primitive recursive functions implies that their computation halts on every input (after a finite number of steps). On the other hand, the [[halting problem]] is [[undecidable problem|undecidable]] for general recursive functions.