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 |
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.
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.
Redirecting to Recursive set
|
|
Wikis
Search
