| Recursive Set |
Article Index for Recursive |
Website Links For Set |
Information AboutRecursive Set |
| CATEGORIES ABOUT RECURSIVE SET | |
| recursion theory | |
| theory of computation | |
|
A more general class of sets are called Recursively Enumerable Set s. 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. DEFINITION A subset ''S'' of the Natural Numbers is called recursive if there exists a Total Computable Function : with : In other words the set ''S'' is recursive Iff the Indicator Function is Computable . EXAMPLES
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 Set s. The Preimage of a recursive set under a Total Computable Function is a recursive set. SEE ALSO |
|
|