Computation in the limit

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 if there is a total computable function such that The 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. In contrast, the set is computable if and only if it is computable in the limit by a function and there is a second computable function that takes input i and returns a value of t large enough that the has stabilized. 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 if and only if it is computable from . Moreover, the limit lemma (and its relativization) hold uniformly. Thus one can go from an index for the function to an index for relative to . One can also go from an index for relative to to an index for some that has limit . As is a [computably enumerable] set, it must be computable in the limit itself as the computable function can be defined whose limit as 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 are limit computable. Fix sets which are identified with their characteristic functions and a computable function with limit .