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 or not a given element belongs to the set. A more general class of sets are called recursively enumerable sets. 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. Computability theory is that part of the theory of computation dealing with which problems are solvable by algorithms (equivalently, by Turing machines), with various restrictions and extensions. ... In mathematics the term countable set is used to describe the size of a set, e. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... Flowcharts are often used to represent algorithms. ... In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input â€” typically an integer or a tuple of integers or a sequence of characters â€” eventually halts if it...

Definition

A subset S of the natural numbers is called recursive if there exists a total computable function Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... In mathematics and computer science, a partial function from the domain X to the codomain Y is a binary relation over X and Y which associates with every element in the set X at most one element in the set Y. If a partial function associates with every element in... In computability theory computable functions or Turing computable functions are the basic objects of study. ...

with

In other words the set S is recursive iff the indicator function 1_S is computable. ↔ ⇔ ≡ For other possible meanings of iff, see IFF. In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. Common alternative phrases to iff or if and only if include Q is necessary and sufficient for P and P... In the mathematical subfield of set theory, the indicator function is a function defined on a set X which is used to indicate membership of an element in a subset A of X. Remark. ... In computability theory computable functions or Turing computable functions are the basic objects of study. ...

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.

In mathematics and more specifically set theory, the empty set is the unique set which contains no elements. ... In mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. ... A recursive language in mathematics, logic and computer science, is a type of formal language which is also called recursive, decidable or Turing-decidable. ... An alphabet is a complete standardized set of letters — basic written symbols — each of which roughly represents a phoneme of a spoken language, either as it exists now or as it may have been in the past. ...

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 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. In set theory and other branches of mathematics, two kinds of complements are defined, the relative complement and the absolute complement. ... ↔ ⇔ ≡ For other possible meanings of iff, see IFF. In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. Common alternative phrases to iff or if and only if include Q is necessary and sufficient for P and P... In set theory and other branches of mathematics, two kinds of complements are defined, the relative complement and the absolute complement. ... In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input â€” typically an integer or a tuple of integers or a sequence of characters â€” eventually halts if it... In mathematics, the image of an element x in a set X under the function f : X → Y, denoted by f(x), is the unique y in Y that is associated with x. ... In mathematics and computer science, a partial function from the domain X to the codomain Y is a binary relation over X and Y which associates with every element in the set X at most one element in the set Y. If a partial function associates with every element in... In computability theory computable functions or Turing computable functions are the basic objects of study. ...

See also

• recursively enumerable set
• recursive function