TOPICS

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

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

## Explore with Wolfram|Alpha

More things to try:

## 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