Limiting recursive

In computability theory, the term limiting recursive (also limit recursive or limit computable) describes sets that 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 $lim\_\{s\; oinfty\}\; g(n,\; s)=1$ if $nin\; S$ and $lim\_\{s\; oinfty\}\; g(n,\; s)=0$ otherwise.

A partial function "f"("n") is limiting recursive if there is a partial computable function "g"("n","s") such that$lim\_\{s\; o\; infty\}\; g(n,s)$ is defined if and only if "f"("n") is defined, and in this case$lim\_\{s\; o\; infty\}\; g(n,s)\; =\; f(n)$.

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$lim\_\{s\; oinfty\}\; g(e,s)$ 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 $Delta^0\_2$ 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