Limiting recursive
In computability theory, the term limiting recursive (also limit recursive or limit computable) describes sets that are not computable but are the limit of a sequence of computable sets.
Definition
A set S is limiting recursive if there is a total computable function g(n,s) such that <math>\lim_{s\to\infty} g(n, s)=1</math> if <math>n\in S</math> and <math>\lim_{s\to\infty} g(n, s)=0</math> otherwise.
A partial function f(n) is limiting recursive if there is a partial computable function g(n,s) such that
<math>\lim_{s \to \infty} g(n,s)</math> is defined if and only if f(n) is defined, and in this case
<math>\lim_{s \to \infty} g(n,s) = f(n)</math>.
Properties
There are limit recursive sets that are not recursive; a particular example is the Halting problem which is the set of indices of Turing machines that halt on input 0. To see this, let <math>g(e,s)</math> be 1 if the Turing machine with index e halts on input 0 after s or fewer steps, and let <math>g(e,s)</math> be 0 otherwise. Then for each e the limit
<math>\lim_{s\to\infty} g(e,s)</math> exists and equals 1 if and only if the Turing machine with index e halts.
The limit lemma states that a set of natural numbers if limiting recursive if and only if the set is at level <math>\Delta^0_2</math> of the arithmetical hierarchy.
References
Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7