Limiting recursive

From Wikipedia, the free encyclopedia

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.

[edit] Definition

A set S is limiting recursive if there is a total computable function g(n,s) such that $\lim_{s\to\infty} g(n, s)=1$ if $n\in S$ and $\lim_{s\to\infty} 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 \to \infty} g(n,s)$ is defined if and only if f(n) is defined, and in this case $\lim_{s \to \infty} g(n,s) = f(n)$ .

[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 $\lim_{s\to\infty} 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.