Predictability
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 a → T 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.
properties
- The composition of predictable functions is predictable.
- The domain of a computable function can be recursively enumerated (see projection theorem ).
- The range of values of a calculable function can be enumerated recursively.
- The universal function takes its first parameter as the god number of an algorithm and applies this algorithm to its second parameter. The universal function can be calculated, for example, using a universal Turing machine .
See also
- Stop problem
- Godel's incompleteness theorem
- Semi-decidable set
- Predictable consequence
- Calculable number
literature
- 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
- Entry in Edward N. Zalta (Ed.): Stanford Encyclopedia of Philosophy .