Recursive set

In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether a given element belongs to the set or not. A more general class of sets are called recursively enumerable sets. For those sets the algorithm only terminates if the element belongs to the set otherwise it does not halt.

Contents

1 Definition 2 Notes 3 Examples 4 See also

Definition

A subset S of the natural numbers is called recursive if there exists a total computable function

with

In other words the set S is recursive iff the indicator function 1_S is computable

Notes

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 and A ∪ B are recursive sets. A set A is a recursive set iff 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.

Examples

• the empty set
• the natural numbers
• every finite subset of the natural numbers
• the set of prime numbers
• a recursive language is a recursive set in the set of all possible words over the alphabet of the language.

See also

• recursively enumerable set
• recursive function