|
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.
Definition
A subset S of the natural numbers is called recursive if there exists a total computable function
- <math>f:\mathbb{N} \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
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
See also
|
