structural:scholar_edition, information:classification, stylistic:tone, structural:summarization
Definition

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 procedure. With more rigor, a function f: N k → N {\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} } is computable if and only if there is an effective procedure that, given any k - tuple x {\displaystyle \mathbf {x} } of natural numbers, will produce the value f (x) {\displaystyle f(\mathbf {x})}. 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 models of computation, including

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. These functions are sometimes referred to as "recursive", to contrast with the informal term "computable", a distinction stemming from a 1934 discussion between Kleene and Gödel.

For example, one can formalize computable functions as μ-recursive functions, which are partial functions that take finite tuples of natural numbers 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 closed under composition, 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 f: N k → N {\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} } can be calculated if and only if there exists a computer program with the following properties: