The Ultimate Recursive set Dog Breeds Information Guide and Reference

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

$f:\mathbb{N} \to \mathbb{N}$

with

$f(x) = \left\{\begin{matrix} 0 &\mbox{if}\ x \in S \\ \neq 0 &\mbox{if}\ x \notin S \end{matrix}\right.$

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.