Editing Computable function (section)

=== Relation to recursively defined functions ===

In a function defined by a [[recursive definition]], each value is defined by a fixed first-order formula of other, previously defined values of the same function or other functions, which might be simply constants. A subset of these is the [[primitive recursive function]]s. Another example is the [[Ackermann function]], which is recursively defined but not primitive recursive.<ref>{{cite journal 
 |last= Péter 
 |first= Rózsa
 |author-link= Rózsa Péter
 |journal= [[Mathematische Annalen]] 
 |title= Konstruktion nichtrekursiver Funktionen 
 |year= 1935 
 |volume= 111
 |pages= 42–60 
 |doi= 10.1007/BF01472200
 |s2cid= 121107217 
}}</ref>

For definitions of this type to avoid circularity or infinite regress, it is necessary that recursive calls to the same function within a definition be to arguments that are smaller in some [[well-partial-order]] on the function's domain. For instance, for the Ackermann function <math>A</math>, whenever the definition of <math>A(x,y)</math> refers to <math>A(p,q)</math>, then <math>(p,q) < (x,y)</math> w.r.t. the [[lexicographic order]] on pairs of [[natural number]]s. In this case, and in the case of the primitive recursive functions, well-ordering is obvious, but some "refers-to" relations are nontrivial to prove as being well-orderings. Any function defined recursively in a well-ordered way is computable: each value can be computed by expanding a tree of recursive calls to the function, and this expansion must terminate after a finite number of calls, because otherwise [[Kőnig's lemma]] would lead to an infinite descending sequence of calls, violating the assumption of well-ordering.