Editing Primitive recursive function (section)

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