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. A total function
is limit computable in D if there is a total function
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.
and there is a second computable function that takes input i and returns a value of t large enough that the
The limit lemma states that a set of natural numbers is limit computable if and only if the set is computable from
(the Turing jump of the empty set).
The relativized limit lemma states that a set is limit computable in
Moreover, the limit lemma (and its relativization) hold uniformly.
goes to infinity is the characteristic function of
It therefore suffices to show that if limit computability is preserved by Turing reduction, as this will show that all sets computable from
and define a computable function
by Post's theorem, the limit lemma also entails that the limit computable sets are the
An early result foreshadowing the equivalence of limit-computability with
-ness was anticipated by Mostowski in 1954, using a hierarchy
[1] Iteration of limit computability can be used to climb up the arithmetical hierarchy.
iff it can be written in the form
-ary recursive function \(g\), under the assumption that all limits exist.
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.
When a real number is viewed as a sequence of bits, the following equivalent definition holds.
of binary digits is computable in the limit if and only if there is a total computable function
taking values in the set
eventually becomes constant and equals
As with the case of computable real numbers, it is not possible to effectively move between the two representations of limit computable reals.
There is a modified version of the limit lemma for α-recursion theory via functions in the
are both undefined, or they are both defined and equal.