Editing Computable function (section)

==Definition==
{{see also|Total Turing machine}}
Computability of a function is an informal notion. One way to describe it is to say that a function is computable if its value can be obtained by an [[effective method|effective procedure]]. With more rigor, a function <math>f:\mathbb N^k\rightarrow\mathbb N</math>
is computable if and only if there is an effective procedure that, given any {{mvar|k}}-[[tuple]] <math>\mathbf x</math> of natural numbers, will produce the value <math>f(\mathbf x)</math>.<ref>{{cite book|last1=Enderton|first1=Herbert|title=A Mathematical Introduction to Logic|date=2002|publisher=Elsevier|location=USA|isbn=0-12-238452-0|page=209|edition=Second}}</ref> In agreement with this definition, the remainder of this article presumes that computable functions take finitely many [[natural numbers]] as arguments and produce a value which is a single natural number.

As counterparts to this informal description, there exist multiple formal, mathematical definitions. The class of computable functions can be defined in many equivalent [[model of computation|models of computation]], including
* [[Turing machine]]s
* [[General recursive function]]s
* [[Lambda calculus]]
* Post machines ([[Post–Turing machine]]s and [[Tag system|tag machines]]).
* [[Register machine]]s

Although these models use different representations for the functions, their inputs, and their outputs, translations exist between any two models, and so every model describes essentially the same class of functions, giving rise to the opinion that formal computability is both natural and not too narrow.<ref>{{cite book|last1=Enderton|first1=Herbert|title=A Mathematical Introduction to Logic|date=2002|publisher=Elsevier|location=USA|isbn=0-12-238452-0|page=208,262|edition=Second}}</ref> These functions are sometimes referred to as "recursive", to contrast with the informal term "computable",<ref>C. J. Ash, J. Knight, ''Computable Structures and the Hyperarithmetical Hierarchy'' (Studies in Logic and the Foundation of Mathematics, 2000), p. 4</ref> a distinction stemming from a 1934 discussion between Kleene and Gödel.<ref>R. Soare, [http://www.people.cs.uchicago.edu/~soare/History/compute.pdf Computability and Recursion] {{Webarchive|url=https://web.archive.org/web/20220331221004/http://www.people.cs.uchicago.edu/~soare/History/compute.pdf |date=2022-03-31 }} (1995). Accessed 9 November 2022.</ref><sup>p.6</sup>

For example, one can formalize computable functions as [[μ-recursive function]]s, which are [[partial function]]s that take finite [[tuple]]s of [[natural number]]s and return a single natural number (just as above). They are the smallest class of partial functions that includes the constant, successor, and projection functions, and is [[Closure (mathematics)|closed]] under [[function composition|composition]], [[Primitive recursive function|primitive recursion]], and the [[μ operator]].

Equivalently, computable functions can be formalized as functions which can be calculated by an idealized computing agent such as a [[Turing machine]] or a [[register machine]]. Formally speaking, a [[partial function]] <math>f:\mathbb N^k\rightarrow\mathbb N</math> can be calculated if and only if there exists a computer program with the following properties:
# If <math>f(\mathbf x)</math> is defined, then the program will terminate on the input <math>\mathbf x</math> with the value <math>f(\mathbf x)</math> stored in the computer memory.
# If <math>f(\mathbf x)</math> is undefined, then the program never terminates on the input <math>\mathbf x</math>.