Computable Function

Any computable function can be incorporated into a program using while-loops (i.e., "while something is true, do something else"). For-loops (which have a fixed iteration limit) are a special case of while-loops, so computable functions could also be coded using a combination of for- and while-loops. The Ackermann function is the simplest example of a well-defined total function which 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).

See also

Ackermann Function, Church-Turing Thesis, Computable Number, Constructible Function, Primitive Recursive Function, Turing Machine

Explore with Wolfram|Alpha


Dötzel, G. "A Function to End All Functions." Algorithm: Recreational Programming 2, 16-17, 1991.

Referenced on Wolfram|Alpha

Computable Function

Cite this as:

Weisstein, Eric W. "Computable Function." From MathWorld--A Wolfram Web Resource.

Subject classifications