# Computable function

**Computable functions** are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Any definition, however, must make reference to some specific model of computation but all valid definitions yield the same class of functions.
Particular models of computability that give rise to the set of computable functions are the Turing-computable functions and the general recursive functions.

Before the precise definition of computable function, mathematicians often used the informal term *effectively calculable*. This term has since come to be identified with the computable functions. Note that the effective computability of these functions does not imply that they can be *efficiently* computed (i.e. computed within a reasonable amount of time). In fact, for some effectively calculable functions it can be shown that any algorithm that computes them will be very inefficient in the sense that the running time of the algorithm increases exponentially (or even superexponentially) with the length of the input. The fields of feasible computability and computational complexity study functions that can be computed efficiently.

According to the Church–Turing thesis, computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space. Equivalently, this thesis states that a function is computable if and only if it has an algorithm. Note that an algorithm in this sense is understood to be a sequence of steps a person with unlimited time and an unlimited supply of pen and paper could follow.

The Blum axioms can be used to define an abstract computational complexity theory on the set of computable functions. In computational complexity theory, the problem of determining the complexity of a computable function is known as a function problem.

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.^{[2]}

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.

The basic characteristic of a computable function is that there must be a finite procedure (an algorithm) telling how to compute the function. The models of computation listed above give different interpretations of what a procedure is and how it is used, but these interpretations share many properties. The fact that these models give equivalent classes of computable functions stems from the fact that each model is capable of reading and mimicking a procedure for any of the other models, much as a compiler is able to read instructions in one computer language and emit instructions in another language.

Enderton [1977] gives the following characteristics of a procedure for computing a computable function; similar characterizations have been given by Turing [1936], Rogers [1967], and others.

Enderton goes on to list several clarifications of these 3 requirements of the procedure for a computable function:

The field of computational complexity studies functions with prescribed bounds on the time and/or space allowed in a successful computation.

A set `A` of natural numbers is called **computable** (synonyms: **recursive**, **decidable**) if there is a computable, total function *f* such that for any natural number `n`, *f*(`n`) = 1 if `n` is in `A` and *f*(`n`) = 0 if `n` is not in `A`.

A set of natural numbers is called **computably enumerable** (synonyms: **recursively enumerable**, **semidecidable**) if there is a computable function *f* such that for each number `n`, *f*(`n`) is defined if and only if `n` is in the set. Thus a set is computably enumerable if and only if it is the domain of some computable function. The word *enumerable* is used because the following are equivalent for a nonempty subset `B` of the natural numbers:

If a set `B` is the range of a function *f* then the function can be viewed as an
enumeration of `B`, because the list *f*(0), *f*(1), ... will include every element of `B`.

Because each finitary relation on the natural numbers can be identified with a corresponding set of finite sequences of natural numbers, the notions of **computable relation** and **computably enumerable relation** can be defined from their analogues for sets.

A key property of a formal language is the level of difficulty required to decide whether a given word is in the language. Some coding system must be developed to allow a computable function to take an arbitrary word in the language as input; this is usually considered routine. A language is called **computable** (synonyms: **recursive**, **decidable**) if there is a computable function *f* such that for each word `w` over the alphabet, *f*(`w`) = 1 if the word is in the language and *f*(`w`) = 0 if the word is not in the language. Thus a language is computable just in case there is a procedure that is able to correctly tell whether arbitrary words are in the language.

A language is **computably enumerable** (synonyms: **recursively enumerable**, **semidecidable**) if there is a computable function *f* such that *f*(`w`) is defined if and only if the word `w` is in the language. The term *enumerable* has the same etymology as in computably enumerable sets of natural numbers.

The following examples illustrate that a function may be computable though it is not known which algorithm computes it.

The **Church–Turing thesis** states that any function computable from a procedure possessing the three properties listed above is a computable function. Because these three properties are not formally stated, the Church–Turing thesis cannot be proved. The following facts are often taken as evidence for the thesis:

The Church–Turing thesis is sometimes used in proofs to justify that a particular function is computable by giving a concrete description of a procedure for the computation. This is permitted because it is believed that all such uses of the thesis can be removed by the tedious process of writing a formal procedure for the function in some model of computation.

Given a function (or, similarly, a set), one may be interested not only if it is computable, but also whether this can be *proven* in a particular proof system (usually first order Peano arithmetic). A function that can be proven to be computable is called **provably total**.

The set of provably total functions is recursively enumerable: one can enumerate all the provably total functions by enumerating all their corresponding proofs, that prove their computability. This can be done by enumerating all the proofs of the proof system and ignoring irrelevant ones.

The converse is not true, as not every provably total function is primitive recursive. Indeed, one can enumerate all the primitive recursive functions and define a function *en* such that for all *n*, *m*: *en*(*n*,*m*) = *f*_{n}(*m*), where *f*_{n} is the n-th primitive recursive function (for k-ary functions, this will be set to *f*_{n}(*m*,*m*...*m*)). Now, *g*(*n*) = *en*(*n*,*n*)+1 is provably total but not primitive recursive, by a diagonalization argument: had there been a *j* such that *g* = *f*_{j}, we would have got *g*(*j*) = *en*(*j*,*j*)+1 = *f*_{j} (*j*)+1= *g*(*j*)+1, a contradiction. (The Gödel numbers of all primitive recursive functions *can* be enumerated by a primitive recursive function, though the primitive recursive functions' values cannot.)

One such function, which is provable total but not primitive recursive, is the Ackermann function: since it is recursively defined, it is indeed easy to prove its computability (However, a similar diagonalization argument can also be built for all functions defined by recursive definition; thus, there are provable total functions that cannot be defined recursively^{[citation needed]}).

In a sound proof system, every provably total function is indeed total, but the converse is not true: in every first-order proof system that is strong enough and sound (including Peano arithmetic), one can prove (in another proof system) the existence of total functions that cannot be proven total in the proof system.

If the total computable functions are enumerated via the Turing machines that produces them, then the above statement can be shown, if the proof system is sound, by a similar diagonalization argument to that used above, using the enumeration of provably total functions given earlier. One uses a Turing machine that enumerates the relevant proofs, and for every input *n* calls *f*_{n}(*n*) (where *f*_{n} is *n*-th function by *this* enumeration) by invoking the Turing machine that computes it according to the n-th proof. Such a Turing machine is guaranteed to halt if the proof system is sound.

The real numbers are uncountable so most real numbers are not computable. See computable number. The set of finitary functions on the natural numbers is uncountable so most are not computable. Concrete examples of such functions are Busy beaver, Kolmogorov complexity, or any function that outputs the digits of a noncomputable number, such as Chaitin's constant.

Similarly, most subsets of the natural numbers are not computable. The halting problem was the first such set to be constructed. The Entscheidungsproblem, proposed by David Hilbert, asked whether there is an effective procedure to determine which mathematical statements (coded as natural numbers) are true. Turing and Church independently showed in the 1930s that this set of natural numbers is not computable. According to the Church–Turing thesis, there is no effective procedure (with an algorithm) which can perform these computations.

The notion of computability of a function can be relativized to an arbitrary set of natural numbers *A*. A function *f* is defined to be **computable in A** (equivalently

**or**

*A*-computable**computable relative to**) when it satisfies the definition of a computable function with modifications allowing access to

*A**A*as an oracle. As with the concept of a computable function relative computability can be given equivalent definitions in many different models of computation. This is commonly accomplished by supplementing the model of computation with an additional primitive operation which asks whether a given integer is a member of

*A*. We can also talk about

*f*being

**computable in**by identifying

*g**g*with its graph.

Hyperarithmetical theory studies those sets that can be computed from a computable ordinal number of iterates of the Turing jump of the empty set. This is equivalent to sets defined by both a universal and existential formula in the language of second order arithmetic and to some models of Hypercomputation. Even more general recursion theories have been studied, such as **E-recursion theory** in which any set can be used as an argument to an E-recursive function.

Although the Church–Turing thesis states that the computable functions include all functions with algorithms, it is possible to consider broader classes of functions that relax the requirements that algorithms must possess. The field of Hypercomputation studies models of computation that go beyond normal Turing computation.