Recursive set

From Wikipedia, the free encyclopedia

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.

1 Formal Definition
2 Examples
3 Properties
4 References

[edit] Formal Definition

A subset S of the natural numbers is called recursive if there exists a total computable function <math>f</math> such that <math>f(x) = 0\,</math> if <math>x \in S</math> and <math>f(x) \not = 0</math> if <math>x \notin S</math>. In other words, the set S is recursive if and only if the indicator function <math>1_{S}</math> 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 A × B are recursive sets.

A set A is a recursive set if and only if A and the complement of A are 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 <math>\Delta^0_1</math> of the arithmetical hierarchy.

A set is recursive if and only if it is the range of a nondecreasing partial computable function.