Recursive Sets

In the field of Computability-Theory, a recursive set is a set of natural numbers for which a Turing-Machine can decide membership. A set is considered recursive if there exists an Algorithm that terminates for every possible input, correctly identifying whether that input belongs to the set or not. This property is the defining characteristic of Decidability within Mathematical-Logic.

The Church-Turing-Thesis provides the foundation for this definition, equating the intuitive notion of effectively calculable sets with those whose Characteristic-Function is a Computable-Function. Unlike Recursively-Enumerable-Sets, which only guarantee termination for elements belonging to the set, recursive sets ensure termination for all inputs, whether they are members or not. A fundamental result known as Post-s-Theorem states that a set is recursive if and only if both the set and its complement are recursively enumerable.

Common examples of recursive sets include the set of Prime-Numbers, the set of even integers, and all finite sets. Conversely, the Halting-Problem represents a set that is not recursive, illustrating the inherent limits of computation. Detailed formalisms can be found in the Stanford Encyclopedia of Philosophy and Wolfram MathWorld.

• Recursively-Enumerable-Sets
• Decidability
• Halting-Problem
• Rice-s-Theorem