Editing Computable function (section)

{{short description|Mathematical function that can be computed by a program}}
'''Computable functions''' are the basic objects of study in [[computability theory]]. Informally, a [[function (mathematics)|function]] is ''computable'' if there is an [[algorithm]] 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 specific [[model of computation]]. 

Many such models of computation have been proposed, the major ones being [[Turing machine]]s, [[register machine]]s, [[lambda calculus]] and [[general recursive function]]s. 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.

The [[Church–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, [[mathematician]]s often used the informal term ''effectively 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 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 [[exponential growth|exponentially]] (or even [[Tetration|superexponentially]]) with the length of the input. The fields of [[feasible computability]] and [[Computational complexity theory|computational complexity]] study functions that can be computed efficiently.

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 computing the value of a function is known as a [[function problem]], by contrast to [[decision problem]]s whose results are either "yes" of "no".