In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if Computability theory is the branch of theoretical computer science that studies which problems are computationally solvable using different models of computation. ... Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ... 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. ...

• 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 and only if the input is an element of S.

Or, equivalently, Flowcharts are often used to represent algorithms. ...

• There is an algorithm that "generates" the members of S. That means that its output is simply a list of the members of S: s₁, s₂, s₃, ... If necessary it runs forever.

The complexity class containing all recursively enumerable sets is RE. In computational complexity theory, a complexity class is a set of problems of related complexity. ... RE (recursively enumerable) is the class of decision problems for which a yes answer can be verified by a Turing machine in a finite amount of time. ...

Common-programming-sense should suggest how to convert either of these algorithms to the other, thus showing the equivalence of the existence of either with the existence of the other. The first condition suggests why the term semi-decidable is sometimes used; the second suggests why computably enumerable is used.

Definition

A countable set S is called recursively enumerable if there exists a partial computable function such that S is the range of f : This article needs to be cleaned up to conform to a higher standard of quality. ... In computability theory computable functions or Turing computable functions are the basic objects of study. ... In mathematics, the range of a function is the set of all output values produced by that function. ...

rng(f) = S

f is called an enumerative function because it associates a rank in the enumeration to every element of S.

Alternatively, a countable set S is recursively enumerable if there exists a partial computable function f such that

In other words if S is the domain of f : In mathematics, the domain of a function is the set of all input values to the function. ...

dom(f) = S

(Note that this is one of two possible senses of the domain of a partial function, but the one preferred in recursion theory. See the discussion at partial function.) This article needs to be cleaned up to conform to a higher standard of quality. ...

A set S is called co-recursively enumerable or co-r.e. if the complement of S is recursively enumerable. In set theory and other branches of mathematics, two kinds of complements are defined, the relative complement and the absolute complement. ...

Remarks

Since the Church-Turing thesis states that computable functions are defined equivalently by Turing machines and other models of computation, we can state the definition as In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. ... An artistic representation of a Turing Machine . ... An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system. ...

A countable set S is called recursively enumerable if there exists a Turing machine that always halts when given an element of S as input, and that never halts when given an input that does not belong to S.

This is also a very common definition of recursively enumerable set.

Examples

• every recursive set is recursively enumerable, but it is not true that every recursively enumerable set is recursive.
• a recursively enumerable language is a recursive enumerable set in the set of all possible words over the alphabet of the language.
• Matiyasevich's theorem states that every Diophantine set is recursively enumerable.
• simple sets are recursively enumerable but not recursive.
• creative sets are recursively enumerable but not recursive.
• Given a Gödel numbering φ of the computable functions then the set (with the Cantor pairing function) is recursively enumerable. This set encodes the halting problem as it describes the input parameters for which each Turing machine halts.
• Given a Gödel numbering φ of the computable functions then the set is recursively enumerable. This set encodes the problem of deciding a function value.

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 recursively enumerable language in mathematics, logic and computer science, is a type of formal language which is also called recursively enumerable, partially decidable or Turing-recognizable. ... 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. ... Matiyasevichs theorem, proven in 1970 by Yuri Matiyasevich, implies that Hilberts tenth problem is unsolvable. ... In mathematics, a set S of j-tuples of integers is Diophantine precisely if there is some polynomial with integer coefficients f(n1, ..., nj, x1, ..., xk) such that a tuple (n1, ..., nj) of integers is in S if and only if there exist some integers x1, ..., xk with f(n1... In computability theory a simple set is an example of a set which is recursively enumerable but not recursive. ... In computability theory productive sets and their complement creative sets are special sets with important applications in mathematical logic. ... In formal number theory a Gödel numbering is a function which assigns to each symbol and formula of some formal language a unique natural number called a Gödel number (GN). ... In mathematics a pairing function is a process to uniquely encode two natural numbers into a single natural number. ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and its initial input, determine whether the program, when executed on this input, ever halts (completes). ... An artistic representation of a Turing Machine . ...

Properties

If A and B are recursively enumerable sets then A ∩ B, A ∪ B and A × B are recursively enumerable sets. A set A is a recursive set if and only if both A and the complement of A are recursively enumerable sets. The preimage of a recursively enumerable set under a computable function is a recursively enumerable set. 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. ...