Recursive set
From Free net encyclopedia
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 or not a given element belongs to the set. A more general class of sets are called recursively enumerable sets. These sets include the decidable sets, but only require that they halt on either yes or no (or both, which would make the set decidable) in finite time.
Contents |
Definition
A subset S of the natural numbers is called recursive if there exists a total computable function
- <math>f:S \to \mathbb{N}</math>
with
- <math>f(x)
\left\{\begin{matrix} = 0 &\mbox{if}\ x \in S \\ \neq 0 &\mbox{if}\ x \notin S \end{matrix}\right. </math>
In other words the set S is recursive iff the indicator function <math>1_{S}</math> is computable.
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.
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 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.
See also
eo:Vikipedio:Projekto matematiko/Rekursie aro fr:Ensemble récursif it:Insieme ricorsivo he:קבוצה רקורסיבית ja:帰納的集合 zh:递归集合