Computable functions are the basic objects of study incomputability theory. Informally, afunction iscomputable if there is analgorithm that computes the value of the function for every value of its argument. Because of the lack of a precise definition of the concept of algorithm, every formal definition of computability must refer to a specificmodel of computation.
Many such models of computation have been proposed, the major ones beingTuring machines,register machines,lambda calculus andgeneral recursive functions. Although these four are of a very different nature, they provide exactly the same class of computable functions, and, for every model of computation that has ever been proposed, the computable functions for such a model are computable for the above four models of computation.
TheChurch–Turing thesis is the unprovable assertion that every notion of computability that can be imagined can compute only functions that are computable in the above sense.
Before the precise definition of computable functions,mathematicians often used the informal termeffectively calculable. This term has since come to be identified with the computable functions. The effective computability of these functions does not imply that they can beefficiently 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 increasesexponentially (or evensuperexponentially) with the length of the input. The fields offeasible computability andcomputational complexity study functions that can be computed efficiently.
TheBlum axioms can be used to define an abstractcomputational complexity theory on the set of computable functions. In computational complexity theory, the problem of computing the value of a function is known as afunction problem, by contrast todecision problems whose results are either "yes" or "no".
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 aneffective procedure. With more rigor, a functionis computable if there is an effective procedure that, given anyk-tuple of natural numbers, will produce the value.[1] In agreement with this definition, the remainder of this article presumes that computable functions take finitely manynatural numbers as arguments and produce a value that 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 equivalentmodels 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] These functions are sometimes referred to as "recursive", to contrast with the informal term "computable",[3] a distinction stemming from a 1934 discussion betweenKleene andGödel.[4]p.6
For example, one can formalize computable functions asμ-recursive functions, which arepartial functions that take finitetuples ofnatural 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 isclosed undercomposition,primitive recursion, and theμ operator.
Equivalently, computable functions can be formalized as functions that can be calculated by an idealized computing agent such as aTuring machine or aregister machine. Formally speaking, apartial function can be calculated if there exists a computer program with the following properties:
The basic characteristic of a computable function is that there must be a finite procedure (analgorithm) 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 acompiler 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:
To summarise, based on this view a function is computable if:
The field ofcomputational complexity studies functions with prescribed bounds on the time and/or space allowed in a successful computation.
A setA of natural numbers is calledcomputable (synonyms:recursive,decidable) if there is a computable, total functionf such that for any natural numbern,f(n) = 1 ifn is inA andf(n) = 0 ifn is not inA.
A set of natural numbers is calledcomputably enumerable (synonyms:recursively enumerable,semidecidable) if there is a computable functionf such that for each numbern,f(n) is definedif and only ifn is in the set. Thus a set is computably enumerable if and only if it is the domain of some computable function. The wordenumerable is used because the following are equivalent for a nonempty subsetB of the natural numbers:
If a setB is the range of a functionf then the function can be viewed as anenumeration ofB, because the listf(0),f(1), ... will include every element ofB.
Because eachfinitary relation on the natural numbers can be identified with a corresponding set of finite sequences of natural numbers, the notions ofcomputable relation andcomputably enumerable relation can be defined from their analogues for sets.
Incomputability theory in computer science, it is common to considerformal languages. Analphabet is an arbitrary set. Aword on an alphabet is a finite sequence of symbols from the alphabet; the same symbol may be used more than once. For example, binary strings are exactly the words on the alphabet{0, 1}. Alanguage is a subset of the collection of all words on a fixed alphabet. For example, the collection of all binary strings that contain exactly 3 ones is a language over the binary alphabet.
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 calledcomputable (synonyms:recursive,decidable) if there is a computable functionf such that for each wordw over the alphabet,f(w) = 1 if the word is in the language andf(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 iscomputably enumerable (synonyms:recursively enumerable,semidecidable) if there is a computable functionf such thatf(w) is defined if and only if the wordw is in the language. The termenumerable has the same etymology as in computably enumerable sets of natural numbers.
The following functions are computable:
Iff andg are computable, then so are:f +g,f *g, iff isunary, max(f,g), min(f,g),arg max{y ≤f(x)} and many more combinations.
The following examples illustrate that a function may be computable though it is not known which algorithm computes it.
TheChurch–Turing thesis states that any function computable from a procedure possessing the three properties listedabove 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 beproven in a particular proof system (usuallyfirst-orderPeano arithmetic). A function that can be proven to be computable is calledprovably total.
The set of provably total functions isrecursively 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.
In a function defined by arecursive 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 theprimitive recursive functions. Another example is theAckermann function, which is recursively defined but not primitive recursive.[5]
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 somewell-partial-order on the function's domain. For instance, for the Ackermann function, whenever the definition of refers to, then with respect to thelexicographic order on pairs ofnatural numbers. 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 otherwiseKőnig's lemma would lead to an infinite descending sequence of calls, violating the assumption of well-ordering.
In asound 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 inputn outputsfn(n) + 1 (wherefn isn-th function bythis enumeration) by invoking the Turing machine that computes it according to then-th proof. Such a Turing machine is guaranteed to halt if the proof system is sound, but the total function it computes cannot be any of the functions proven total by the proof system, otherwise there would be somen for whichfn(n) + 1 =fn(n).
Every computable function has a finite procedure giving explicit, unambiguous instructions on how to compute it. Furthermore, this procedure has to be encoded in the finite alphabet used by the computational model, so there are onlycountably many computable functions. For example, functions may be encoded using a string of bits (the alphabetΣ = {0, 1}).
The real numbers are uncountable so most real numbers are not computable. Seecomputable number. The set offinitary functions on the natural numbers is uncountable so most are not computable. Concrete examples of such functions areBusy beaver,Kolmogorov complexity, or any function that outputs the digits of a noncomputable number, such asChaitin's constant.
Similarly, most subsets of the natural numbers are not computable. Thehalting problem was the first such set to be constructed. TheEntscheidungsproblem, proposed byDavid 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) that can perform these computations.
The notion of computability of a function can berelativized to an arbitraryset ofnatural numbersA. A functionf is defined to becomputable inA (equivalentlyA-computable orcomputable relative toA) when it satisfies the definition of a computable function with modifications allowing access toA as anoracle. 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 that asks whether a given integer is a member ofA. We can also talk aboutf beingcomputable ing by identifyingg with its graph.
Hyperarithmetical theory studies those sets that can be computed from acomputable ordinal number of iterates of theTuring jump of the empty set. This is equivalent to sets defined by both a universal and existential formula in the language ofsecond-order arithmetic and to some models ofhypercomputation. Even more general recursion theories have been studied, such asE-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 ofhypercomputation studies models of computation that go beyond normal Turing computation.
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems (list), paradoxes | |||||||||
| Logics |
| ||||||||
| Set theory |
| ||||||||
| Formal systems (list), language, syntax |
| ||||||||
| Proof theory | |||||||||
| Model theory | |||||||||
| Computability theory | |||||||||
| Related | |||||||||
