Computable Function (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
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
References
Dötzel, G. "A Function to End All Functions." Algorithm: Recreational Programming 2, 16-17, 1991.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Computable Function." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ComputableFunction.html