Limiting recursive
From Wikipedia, the free encyclopedia
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.
[edit] Definition
A set S is limiting recursive if there is a total computable function g(n,s) such that 
if 
and 
otherwise.
A partial function f(n) is limiting recursive if there is a partial computable function g(n,s) such that 
is defined if and only if f(n) is defined, and in this case 
.
[edit] 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 g(e,s) be 1 if the Turing machine with index e halts on input 0 after s or fewer steps, and let g(e,s) be 0 otherwise. Then for each e the limit 
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 
of the arithmetical hierarchy.
[edit] References
Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7
