|
|
|
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's Thesis, Computable Number, Primitive Recursive Function, Turing Machine
References
Dötzel, G. ``A Function to End All Functions.'' Algorithm: Recreational Programming 2, 16-17, 1991.