TOPICS
Search

Primitive Recursive Function


As first shown by Meyer and Ritchie (1967), do-loops (which have a fixed iteration limit) are a special case of while-loops. A function that can be implemented using only do-loops is called primitive recursive. (In contrast, a computable function can be coded using a combination of for- and while-loops, or while-loops only.) Examples of primitive recursive functions include power, greatest common divisor, and p_n(the function giving the nth prime).

The Ackermann function is the simplest example of a well-defined total function that is computable but not primitive recursive, providing a counterexample to the belief in the early 1900s that every computable function was also primitive recursive (Dötzel 1991; Wolfram 2002, p. 907).


See also

Ackermann Function, Computable Function, General Recursive Function, Recursive Function, Total Function

Explore with Wolfram|Alpha

References

Dötzel, G. "A Function to End All Functions." Algorithm: Recreational Programming 2, 16-17, 1991.Meyer, A. and Ritchie, D. "The Complexity of Loop Programs." Proc. 22nd National ACM Conference. Washington, DC: pp. 465-470, 1967.Péter, R. Rekursive Funktionen in der Komputer-Theorie. Budapest: Akad. Kiado, 1951.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, 907, 2002.

Referenced on Wolfram|Alpha

Primitive Recursive Function

Cite this as:

Weisstein, Eric W. "Primitive Recursive Function." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PrimitiveRecursiveFunction.html

Subject classifications