Recursive set
From Wikipedia, the free encyclopedia
 |
It has been suggested that Recursively enumerable set be merged into this article or section. (Discuss) |
In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set. A set which is not computable is called noncomputable or undecidable.
A more general class of sets consists of the recursively enumerable sets. For these sets, it is only required that there is an algorithm that correctly decides when a number is in the set; the algorithm may give no answer (but not the wrong answer) for numbers not in the set.
Contents |
[edit] Formal definition
A subset S of the natural numbers is called recursive if there exists a total computable function 
such that 
if 
and 
if 
. In other words, the set S is recursive if and only if the indicator function 
is computable.
[edit] Examples
- The empty set is computable.
- The entire set of natural numbers is computable.
- Every finite or cofinite subset of the natural numbers is computable.
- The set of prime numbers is computable.
- A recursive language is a recursive subset of a formal language.
[edit] Properties
If A is a recursive set then the complement of A is a recursive set. If A and B are recursive sets then A ∩ B, A ∪ B and the image of A × B under the Cantor pairing function are recursive sets.
A set A is a recursive set if and only if A and the complement of A are both recursively enumerable sets. The preimage of a recursive set under a total computable function is a recursive set. The image of a computable set under a total computable bijection is computable.
A set is recursive if and only if it is at level 
of the arithmetical hierarchy.
A set is recursive if and only if it is either the range of a nondecreasing total computable function or the empty set. The image of a computable set under a nondecreasing total computable function is computable.
[edit] References
Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7
Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1
Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7
