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 In mathematics, the term "characteristic function" can refer to any of several distinct concepts:
* The indicator function of a subset, that is the function
::\mathbf_A\colon X \to \,
:which for a given subset ''A'' of ''X'', has value 1 at points ...
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
In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is de ...
is limit computable if there is a
total computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
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 number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
s is defined to be computable in the limit if and only if its
characteristic function In mathematics, the term "characteristic function" can refer to any of several distinct concepts:
* The indicator function of a subset, that is the function
::\mathbf_A\colon X \to \,
:which for a given subset ''A'' of ''X'', has value 1 at points ...
is computable in the limit. In contrast, the set is
computable
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...
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
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
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine w ...
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
As
is a
omputably enumerableset, 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
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to s ...
, 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 In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
Background
The statement of Post's theorem uses several concepts relating to definability and ...
, the limit lemma also entails that the limit computable sets are the
sets.
Limit computable real numbers
A
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
''x'' is computable in the limit if there is a computable sequence
of
rational numbers
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all rat ...
(or, which is equivalent,
computable real numbers) which converges to ''x''. In contrast, a real number is
computable
Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is close ...
if and only if there is a sequence of rational numbers which converges to it and which has a computable
modulus of convergence
In real analysis, a branch of mathematics, a modulus of convergence is a function that tells how quickly a convergent sequence converges. These moduli are often employed in the study of computable analysis and constructive mathematics.
If a sequ ...
.
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
* The real whose binary expansion encodes the
halting problem
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a ...
is computable in the limit but not computable.
* The real whose binary expansion encodes the truth set of
first-order arithmetic
In first-order logic, a first-order theory is given by a set of axioms in some
language. This entry lists some of the more common examples used in model theory and some of their properties.
Preliminaries
For every natural mathematical structure ...
is not computable in the limit.
*
Chaitin's constant
In the computer science subfield of algorithmic information theory, a Chaitin constant (Chaitin omega number) or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will ...
.
See also
*
Specker sequence
In computability theory, a Specker sequence is a computable, monotonically increasing, bounded sequence of rational numbers whose supremum is not a computable real number. The first example of such a sequence was constructed by Ernst Specker (194 ...
References
#
J. Schmidhuber, "Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit", ''International Journal of Foundations of Computer Science'', 2002, .
#
R. Soare. ''Recursively Enumerable Sets and Degrees''. Springer-Verlag 1987.
# V. Brattka. ''A Galois connection between Turing jumps and limits''. ''Log. Methods Comput. Sci.'', 2018, {{Doi, 10.23638/LMCS-14(3:13)2018.
Computability theory
Theory of computation