Computability

A mathematical function is computable (also effectively computable or recursive), unless they are calculating instruction ( algorithm) can be formulated ( computability theory ). The function for calculating an algorithm is given by the output of the algorithm to react to the input. The domain of the function is the set of inputs, produces an output for the algorithm. If the algorithm does not terminate, then the input is not an element of the definition set.

The term algorithm is based on a calculation model. Several computational models have been developed, however, it has been found that the strongest of them to the model of Turing machine ( Turing - powerful) are equally strong. The Church - Turing thesis asserts, therefore, that the Turing machines reflect the intuitive notion of computability. In computability theory accurately be called the functions computable, which are Turing -computable.

The Turing powerful computational models in addition to the Turing machine include, for example, the WHILE programs, μ - recursive functions, register machines and the lambda calculus.

For the calculation models that are weaker than Turing machines include, for example, the LOOP programs. This can not, for example calculate the Turing - computable Ackermann function.

A the concept of predictability of closely related concept is that of decidability. A subset of a set (for example, a formal language ) is determinable as its characteristic function ( substantially the associated predicate ) is calculated.

Formal definition

It is said that the algorithm calculates with the function when entering after a finite number of steps outputting the value and not terminated when entering.

A function is calculated when there is an algorithm that calculates.

The notion of computability can be transferred equivalent to partial functions. A partial function is called computable if it restricted to its domain is a computable function.

Number functions

In computability theory usually only functions of natural numbers are considered.

Definition of computable functions with Register Machines

A function is computable if and only if there is a digit register machine whose machine function, so is true with matches.

For example, the function

( the terminated for no argument ) calculated because there is a corresponding register machine.

Definition of WHILE programs

A function (as above) is computable if and only if there is a WHILE program with

Here is the input encoding, the output encoding and the realized about the semantics of machine function.

Definition by recursion

Be, Sub Prk and the operations of the μ - recursion, the substitution and primitive recursion. Functions that can be generated from the set of primitive recursive functions by reason repeatedly applying these operators, called μ - recursive. The set of recursive functions is exactly the set of computable functions.

Transition from single-digit to multi-digit functions

About the Cantor pairing function is carried back the notion of computability of a k- ary function on the predictability of digit functions. In particular, you can use it to define in a natural way, which functions are computable on the rational numbers.

Word functions

The predictability of word functions can be demonstrated either by means of Turing machines. Alternatively, leads to a standard numbering of the words above and shows that the number of functions so generated are calculated.

Uniform computability

A binary function f ( x, y) f a can be calculated with the property that for any fixed value of a by fa (y) = f (a, y) defined digit function need not necessarily be calculated in itself; for each value of a there is indeed an algorithm ( ie about a program for a Turing machine ) Ta, the calculated fa, but the mapping a → Ta is not computable in general.

Family ( FA: a = 0,1,2, ... ) is computable functions of uniform predictable, if it is an algorithm which provides an algorithm to each of a Ta which FA calculated. One can easily show that such a family is exactly then uniform computable if the binary function (x, y) → fx (y) is computable.

Properties

• The composition of computable functions is computable.
• The domain of a computable function is recursive enumerable (see projection set ).
• The value range of a computable function is recursive enumerable.
• The universal function takes its first parameter as a Gödel number of an algorithm and applies this algorithm to its second parameter. The universal function can be calculated for example by a universal Turing machine.