Recursive set
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 a given number belongs to the set.
A more general class of sets consists of the recursively enumerable sets, also called semidecidable 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.
A set which is not computable is called noncomputable or undecidable.
Formal definition
A subset S of the natural numbers is called recursive if there exists a total computable function f such that
f(x) = 1 if x ∈ S and f(x) = 0 if x ∉ S . In other words, the set S is recursive if and only if the indicator function 1S is computable.
Examples
Every finite or cofinite subset of the natural numbers is computable. This includes these special cases:
- The empty set is computable.
- The entire set of natural numbers is computable.
- Each natural number (as defined in standard set theory) is computable; that is, the set of natural numbers less than a given natural number is computable.