from Wikipedia, the free encyclopedia

A mathematical function is calculable (also effectively calculable or recursive ) if a calculation instruction ( algorithm ) can be formulated for it ( calculability theory ). The function that an algorithm computes is given by the output with which the algorithm reacts to an input . The domain of the function is the amount of inputs for which the algorithm produces an output. 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 . Various calculation models have been developed, but it has been found that the strongest of them are equally strong ( Turing-powerful ) to the model of the Turing machine . The Church-Turing thesis therefore claims that the Turing machines reproduce the intuitive concept of predictability. In the calculability theory, exactly those functions are called calculable that are Turing-calculable.

The Turing powerful calculation models include the Turing machine, for example, two-cellar machines , WHILE programs , μ-recursive functions , register machines and the lambda calculus .

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

A concept closely related to the concept of predictability is that of decidability . A subset of a set (for example a formal language ) is called decidable if its characteristic function (essentially the associated predicate) can be calculated.

Formal definition

Is assumed: the algorithm calculates the function of , when at the input of the value by a finite number of steps and outputs for entry of not terminated .

A function is said to be computable if there is an algorithm that computes it.

The concept of calculability can be applied equally to partial functions . A partial function is said to be calculable if it is a calculable function restricted to its domain .

Number functions

In the computability theory mostly only functions of natural numbers are considered.

Definition of calculable functions with register machines

A function is computable if and only if there is a -digit register machine is, the machine function with matches, that is true.

For example, the function is

(which does not terminate for any argument) calculable, since there is a corresponding register machine.

Definition with WHILE programs

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


Thereby the input coding , the output coding and the machine function realized by the semantics.

Definition by recursion

Let , Sub and Prk be the operations of µ-recursion , substitution and primitive recursion . Functions that can be generated from the set of primitive-recursive basic functions by repeatedly using these operators are called µ-recursive. The set of recursive functions is exactly the set of computable functions.

Transition from single-digit to multi-digit functions

Using the Cantor pairing function , the concept of the calculability of a k -place function is reduced to that of the calculability of single-digit functions. In particular, it defines in a natural way whether functions of rational numbers can be calculated.

Word functions

The predictability of word functions can be shown with the help of Turing machines . As an alternative, standard numbering is introduced using the words above and shows that the number functions generated in this way can be calculated.

Uniform predictability

A two-digit function f ( x , y ) with the property that for every fixed value a the one-digit function f a defined by f a ( y ) = f ( a , y ) is computable, does not necessarily have to be computable itself; for every value a there is an algorithm (e.g. a program for a Turing machine) T a that calculates f a , but the mapping aT a is generally not computable.

A family ( f a : a = 0, 1, 2, ...) of computable functions is called uniformly computable if there is an algorithm that delivers an algorithm T a for every a that computes f a . One can easily show that such a family is uniformly computable if and only if the two-digit function ( x , y ) → f x ( y ) is computable.


See also


  • SB Cooper: Computability Theory. Chapman & Hall / CRC, 2004, ISBN 1-58488-237-9 .
  • Nigel Cutland: Computability, An introduction to recursive function theory. Cambridge University Press, 1980, ISBN 0-521-29465-7 .
  • Hans Hermes : Enumerability - Decidability - Calculability. Introduction to the theory of recursive functions . Berlin - Göttingen - Heidelberg 1961, 2nd edition. 1971 (as Heidelberg paperback).
  • Stephen Kleene : Introduction to Metamathematics. North-Holland, 1952, ISBN 0-7204-2103-9 .
  • Piergiorgio Odifreddi : Classical Recursion Theory . North-Holland, 1989, ISBN 0-444-87295-7 .
  • Hartley Rogers , Jr .: Theory of recursive functions and effective computability . McGraw-Hill, 1967, ISBN 978-0-262-68052-3 .
  • Dieter Rödding: Register machines. In: Mathematics Lessons . Issue 18, 1972, ISSN  0025-5807 , pp. 32-41.
  • JC Shepherdson, HE Sturgis: Computability of Recursive Functions. Journal of the ACM, Volume 10, Issue 2, April 1963, ISSN  0004-5411 , pp. 217-255.

Web links

Wiktionary: predictability  - explanations of meanings, word origins, synonyms, translations