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.

Formal definition

edit

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.

Limit lemma

edit

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  .

Proof

edit

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  . Suppose that   for some Turing reduction   and define a computable function   as follows

 

Now suppose that the computation   converges in   steps and only looks at the first   bits of  . Now pick   such that for all    . If   then the computation   converges in at most   steps to  . Hence   has a limit of  , so   is limit computable.

As the   sets are just the sets computable from   by Post's theorem, the limit lemma also entails that the limit computable sets are the   sets.

An early result foreshadowing the equivalence of limit-computability with  -ness was anticipated by Mostowski in 1954, using a hierarchy   and formulas  , where   is a function obtained from an arbitrary primitive recursive function   such that   is equivalent to  .[1]

Extension

edit

Iteration of limit computability can be used to climb up the arithmetical hierarchy. Namely, an  -ary function   is   iff it can be written in the form   for some  -ary recursive function \(g\), under the assumption that all limits exist.[2]

Limit computable real numbers

edit

A real number x is computable in the limit if there is a computable sequence   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. An infinite sequence   of binary digits is computable in the limit if and only if there is a total computable function   taking values in the set   such that for each i the limit   exists and equals  . Thus for each i, as t increases the value of   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.

Examples

edit

Set-theoretic extension

edit

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

For a given admissible ordinal  , define the  -arithmetical hierarchy:

  • A relation   on   is   if it is  -recursive.
  •   is   if it is the projection of a   relation.
  •   is   if its complement is  .

Let   be a partial function from   to  . The following are equivalent:

  • (The graph of)   is  .
  •   is weakly  -recursive in  , the  -jump of   using indices of  -computable functions.
  • There is an  -recursive function   approximating   such that  .

  denotes that either   and   are both undefined, or they are both defined and equal.

See also

edit

References

edit
  1. ^ A. Mostowski, "Examples of sets definable by means of two and three quantifiers". Fundamenta Mathematicae vol. 42, iss. 2, pp.259--270 (1955)
  2. ^ G. Criscuolo, E. Minicozzi, G. Trautteur, "Limiting recursion and the arithmetic hierarchy". Revue française d’automatique informatique recherche opérationnelle, Informatique théorique, book 9, no. R3 (1975), pp.5--12. Publisher Dunod-Gauthier-Villars.
  3. ^ S. G. Simpson, "Degree Theory on Admissible Ordinals", pp.170--171. Appearing in J. Fenstad, P. Hinman, Generalized Recursion Theory: Proceedings of the 1972 Oslo Symposium (1974), ISBN 0-7204-22760.
  1. J. Schmidhuber, "Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit", International Journal of Foundations of Computer Science, 2002, doi:10.1142/S0129054102001291.
  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, doi:10.23638/LMCS-14(3:13)2018.