# 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 . ${\ displaystyle P}$ ${\ displaystyle f \ colon T \ rightarrow \ mathbb {N}}$${\ displaystyle T \ subseteq \ mathbb {N} ^ {k}}$${\ displaystyle P}$${\ displaystyle \ left (n_ {1}, \ ldots, n_ {k} \ right) \ in T}$${\ displaystyle f \ left (n_ {1}, \ ldots, n_ {k} \ right)}$${\ displaystyle \ left (n_ {1}, \ ldots, n_ {k} \ right) \ in \ mathbb {N} ^ {k} \ setminus T}$

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 . ${\ displaystyle f \ colon \ mathbb {N} ^ {k} \ rightsquigarrow \ mathbb {N}}$ ${\ displaystyle f \ colon \ operatorname {Def} (f) \ to \ mathbb {N}}$

### 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. ${\ displaystyle f \ colon \ mathbb {N} ^ {k} \ rightarrow \ mathbb {N}}$${\ displaystyle k}$ ${\ displaystyle M}$${\ displaystyle f}$${\ displaystyle f = f_ {M}}$

For example, the function is

${\ displaystyle f (x) = {\ mbox {div}}}$

(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 ${\ displaystyle f}$ ${\ displaystyle P}$

${\ displaystyle f = AC \ circ \ tau (P) \ circ EC}$.

Thereby the input coding , the output coding and the machine function realized by the semantics. ${\ displaystyle EC}$${\ displaystyle AC}$${\ displaystyle \ tau (P)}$${\ displaystyle P}$

#### 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. ${\ displaystyle \ mu}$${\ displaystyle \ mu}$

#### 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. ${\ displaystyle \ Sigma ^ {*}}$

## 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.

## 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, , pp. 32-41.
• JC Shepherdson, HE Sturgis: Computability of Recursive Functions. Journal of the ACM, Volume 10, Issue 2, April 1963, , pp. 217-255.