Computable function

Computable functions are the basic objects of study in computability theory. The set of computable functions is equivalent to the set of Turing-computable functions and partial recursive functions. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Their definition, however, must make reference to some specific model of computation.

Before the precise definition of computable function, mathematicians often used the informal term effectively computable. 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 computable 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 any function which has an algorithm is computable.

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.

Definition

There are many equivalent ways to define the class of computable functions. For concreteness, the remainder of this article will assume that computable functions have been defined as those finitary partial functions on the natural numbers that can be calculated by a Turing machine. There are many equivalent models of computation that define the same class of computable functions. These models of computation include

• Turing machines
• μ-recursive functions
• Lambda calculus
• Post machines (Post-Turing machines and tag machines).
• Register machines

and others.

Each computable function f takes a fixed number of natural numbers as arguments. Because the functions are partial, they may not be defined for every possible choice of input. If a computable function is defined then it returns a single natural number as output (this output can be interpreted as a list of numbers using a pairing function). These functions are also called partial recursive functions. In computability theory, the domain of a function is taken to be the set of all inputs for which the function is defined.

A function which is defined for all arguments is called total. If a computable function is total, it is called a total computable function or total recursive function.

The notation indicates that the partial function f is defined on arguments , and the notation indicates that f is defined on the arguments and the value returned is y.