Computable function


Computable functions are the basic objects of study in computability theory. Informally, a 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 machines, register machines, lambda calculus and general 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.
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, mathematicians 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. 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 with the length of the input. The fields of feasible computability and 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 problems whose results are either "yes" or "no".

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
is computable if there is an effective procedure that, given any -tuple of natural numbers, will produce the value. 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 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 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.p.6
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. 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 that can be calculated by an idealized computing agent such as a Turing machine or a register machine. Formally speaking, a partial function can be calculated if there exists a computer program with the following properties:
  1. If is defined, then the program will terminate on the input with the value stored in the computer memory.
  2. If is undefined, then the program never terminates on the input.

    Characteristics of computable functions

The basic characteristic of a computable function is that there must be a finite procedure 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 gives the following characteristics of a procedure for computing a computable function; similar characterizations have been given by Turing , Rogers , and others.
  • "There must be exact instructions, finite in length, for the procedure." Thus every computable function must have a finite program that completely describes how the function is to be computed. It is possible to compute the function by just following the instructions; no guessing or special insight is required.
  • "If the procedure is given a k-tuple x in the domain of f, then after a finite number of discrete steps the procedure must terminate and produce f." Intuitively, the procedure proceeds step by step, with a specific rule to cover what to do at each step of the calculation. Only finitely many steps can be carried out before the value of the function is returned.
  • "If the procedure is given a k-tuple x that is not in the domain of f, then the procedure might go on forever, never halting. Or it might get stuck at some point, but it must not pretend to produce a value for f at x." Thus if a value for f is ever found, it must be the correct value. It is not necessary for the computing agent to distinguish correct outcomes from incorrect ones because the procedure is defined as correct if and only if it produces an outcome.
Enderton goes on to list several clarifications of these 3 requirements of the procedure for a computable function:
  1. The procedure must theoretically work for arbitrarily large arguments. It is not assumed that the arguments are smaller than the number of atoms in the Earth, for example.
  2. The procedure is required to halt after finitely many steps in order to produce an output, but it may take arbitrarily many steps before halting. No time limitation is assumed.
  3. Although the procedure may use only a finite amount of storage space during a successful computation, there is no bound on the amount of space that is used. It is assumed that additional storage space can be given to the procedure whenever the procedure asks for it.
To summarise, based on this view a function is computable if:
The field of computational complexity studies functions with prescribed bounds on the time and/or space allowed in a successful computation.

Computable sets and relations

A set of natural numbers is called computable if there is a computable, total function such that for any natural number, if is in and if is not in.
A set of natural numbers is called computably enumerable if there is a computable function such that for each number, is defined if and only if 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 of the natural numbers:
  • is the domain of a computable function.
  • is the range of a total computable function. If is infinite then the function can be assumed to be injective.
If a set is the range of a function then the function can be viewed as an
enumeration of, because the list will include every element of.
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.

Formal languages

In computability theory in computer science, it is common to consider formal languages. An alphabet is an arbitrary set. A word 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. A language 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 called computable if there is a computable function such that for each word over the alphabet, if the word is in the language and 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 if there is a computable function such that is defined if and only if the word is in the language. The term enumerable has the same etymology as in computably enumerable sets of natural numbers.

Examples

The following functions are computable:
If f and g are computable, then so are: f + g, f * g, Function composition| if
f is unary, max, min, and many more combinations.
The following examples illustrate that a function may be computable though it is not known which algorithm computes it.
  • The function f such that f = 1 if there is a sequence of at least n consecutive fives in the decimal expansion of, and f = 0 otherwise, is computable. = 1 if n < k and f
  • Each finite segment of an uncomputable sequence of natural numbers is computable. E.g., for each natural number n, there exists an algorithm that computes the finite sequence Σ, Σ, Σ,..., Σ — in contrast to the fact that there is no algorithm that computes the entire Σ-sequence, i.e. Σ for all n. Thus, "Print 0, 1, 4, 6, 13" is a trivial algorithm to compute Σ, Σ, Σ, Σ, Σ; similarly, for any given value of n, such a trivial algorithm exists to compute Σ, Σ, Σ,..., Σ.