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

Definition

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

[itex]f:\mathbb{N} \to \mathbb{N}[itex]

with

[itex]f(x) =

\left\{\begin{matrix} 0 &\mbox{if}\ x \in S \\ \neq 0 &\mbox{if}\ x \notin S \end{matrix}\right. [itex]

In other words the set S is recursive iff the indicator function [itex]1_{S}[itex] 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 AB and AB 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

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy