In computability theory, a function is called limit computable if it is the limit of a uniformly computable sequence of functions. The terms computable in the limit, limit recursive and recursively approximable are also used. One can think of limit computable functions as those admitting an eventually correct computable guessing procedure at their true value. A set is limit computable just when its characteristic function is limit computable.

If the sequence is uniformly computable relative to D, then the function is limit computable in D.

Formal definition

A total function is limit computable if there is a total computable function such that

is limit computable in D computable in D also satisfying

A set of natural numbers is defined to be computable in the limit if and only if its characteristic function is computable in the limit. In contrast, the set is computable and there is a second computable function that takes input i and returns a value of t has stabilized.

Limit lemma

The limit lemma (the Turing jump of the empty set.

Proof

is a [computably enumerable] set, it must be computable in the limit itself as the computable function can be defined

.

It therefore suffices to show that if limit computability is preserved by Turing reduction as follows

is limit computable.

by Post's theorem sets.

-ness was anticipated by Mostowski.

Extension

Iteration of limit computability can be used to climb up the arithmetical hierarchy, under the assumption that all limits exist.

Limit computable real numbers

A real number x is computable in the limit of rational numbers (or, which is equivalent, computable real numbers) which converges to x. In contrast, a real number is computable if and only if there is a sequence of rational numbers which converges to it and which has a computable modulus of convergence.

such that for each i. Thus for each i, as t. As with the case of computable real numbers, it is not possible to effectively move between the two representations of limit computable reals.

Examples

• The real whose binary expansion encodes the halting problem is computable in the limit but not computable.

• The real whose binary expansion encodes the truth set of first-order arithmetic is not computable in the limit.

• Chaitin's constant.

Set-theoretic extension

There is a modified version of the limit lemma for α-recursion theory-arithmetical hierarchy, which is a hierarchy defined relative to some admissible ordinal.

-arithmetical hierarchy:

• -recursive.

• relation.

• .

. The following are equivalent:

• .

• -computable functions.

• .

are both undefined, or they are both defined and equal.

See also

• Specker sequence

References

1. J. Schmidhuber, "Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit", International Journal of Foundations of Computer Science, 2002, .

2. R. Soare. Recursively Enumerable Sets and Degrees. Springer-Verlag 1987.

3. V. Brattka. A Galois connection between Turing jumps and limits. Log. Methods Comput. Sci., 2018, .