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

# Computable Function

## See also

Ackermann Function, Church-Turing Thesis, Computable Number, Constructible Function, Primitive Recursive Function, Turing Machine## Explore with Wolfram|Alpha

## References

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. https://mathworld.wolfram.com/ComputableFunction.html