Computation in the limit

From Wikipedia, the free encyclopedia

You have new messages (last change).

In computability theory, a real number or set of natural numbers is called computable in the limit if there is a uniformly computable sequence of computable approximations that converges to it.

Contents

[edit] Formal definition

A real number x is computable in the limit if there is a computable sequence ri 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. A infinite sequence ω of binary digits is computable in the limit if and only if there is a total computable function φ(t,i) taking values in the set {0,1} such that for each i the limit \lim_{t \rightarrow \infty} \phi(t,i) exists and equals ω(i). Thus for each i, as t increases the vaue of φ(t,i) eventually becomes constant and equals ω(i).

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 (when viewed as an infinite binary sequence). In contrast, the set is computable if and only if it is computable in the limit by a function φ(t,i) and there is a second computable function that takes input i and returns a value of t large enough the φ(t,i) has stabilized.

[edit] 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.

[edit] Relationship to the arithmetical hierarchy

A real number whose binary expansion is computably enumerable is called a computable number; every such number is at level \Delta^0_1 of the arithmetical hierarchy.

The limit lemma states that an infinite binary expansion is computable in the limit if and only if it is at level \Delta^0_2 of the arithmetical hierarchy. A consequence of Post's theorem is that a real number is computable in the limit if and only if it is computable relative to an oracle for the Halting problem. Not every real that is computable in the limit is computable.

[edit] 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.
Retrieved from "http://en.wikipedia.org../../../c/o/m/Computation_in_the_limit.html"