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 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.

Formal Definition

A subset S of the natural numbers is called recursive if there exists a total computable function $f$ such that $f(x)\; =\; 0\backslash ,$ if $x\; \backslash in\; S$ and $f(x)\; \backslash not\; =\; 0$ if $x\; \backslash notin\; S$. In other words, the set S is recursive if and only if the indicator function $1\_\{S\}$ is computable.

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.

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 $\backslash Delta^0\_1$ of the arithmetical hierarchy.

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

See also

• Recursively enumerable set
• Computable function

Recursion theory | Theory of computation

Rekursiv entscheidbare Menge | Komputebla aro | Ensemble récursif | Insieme ricorsivo | קבוצה רקורסיבית | 帰納的集合 | Zbiór rekurencyjny | 递归集合