In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable 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. ... 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...

• There is an algorithm that, when given an input number, eventually halts if and only if the input is an element of S.

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

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

The first condition suggests why the term semidecidable is sometimes used; the second suggests why computably enumerable is used. The abbreviations r.e. and c.e. are often used, even in print, instead of the full phrase.

In computational complexity theory, the complexity class containing all recursively enumerable sets is RE. In recursion theory, the lattice of r.e. sets under inclusion is denoted . In computer science, computational complexity theory is the branch of the theory of computation that studies the complexity, or efficiency, of solving computational problems. ... 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. ... 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. ... The name lattice is suggested by the form of the Hasse diagram depicting it. ...

Formal definition

A set S of natural numbers is called recursively enumerable if there is a partial recursive (i.e. computable) function whose domain (co-range) is exactly S, meaning that the function is defined if and only if its input is a member of S. In mathematics, the domain of a function is the set of all input values to the function. ...

The definition can be extended to an arbitrary countable set A by using Gödel numbers to represent elements of the set and declaring a subset of A to be recursively enumerable if the set of corresponding Gödel numbers is recursively enumerable. 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). ...

Equivalent formulations

The following are all equivalent properties of a set S of natural numbers:

Semidecidability:

• The set S is recursively enumerable. That is, S is the domain (co-range) of a partial recursive function.
• There is a partial recursive function f such that:

Enumerability:

• The set S is the range of a partial recursive function.
• The set S is the range of a total recursive function or empty. If S is infinite, the function can be chosen to be injective.
• The set S is the range of a primitive recursive function or empty. Even if S is infinite, repetition of values may be necessary in this case.

In mathematics, an injective function (or one-to-one function or injection) is a function which maps distinct input values to distinct output values. ... In computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. ...

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 recursively enumerable subset of a formal language.
• The set of all provable sentences in an effectively presented axiomatic system is a recursively enumerable set.
• Matiyasevich's theorem states that every recursively enumerable set is a Diophantine set (the converse is trivially true).
• The simple sets are recursively enumerable but not recursive.
• The creative sets are recursively enumerable but not recursive.
• Any productive set is not recursively enumerable.
• Given a Gödel numbering φ of the computable functions, the set (where is the Cantor pairing function and indicates φ_i(x) is defined) 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, the set is recursively enumerable. This set encodes the problem of deciding a function value.
• Given a partial function f from the natural numbers into the natural numbers, f is a partial recursive function if and only if the graph of f, that is, the set of all pairs such that f(x) is defined, is recursively enumerable.

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 partially decidable or Turing-recognizable. ... In mathematics, logic, and computer science, a formal language is a set of finite-length words (i. ... 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. ... This article or section does not cite its references or sources. ... 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 (with the ordered pair of natural numbers mapped to a single natural number with the Cantor pairing function) are recursively enumerable sets. The preimage of a recursively enumerable set under a partial recursive function is a recursively enumerable set. In mathematics a pairing function is a process to uniquely encode two natural numbers into a single natural number. ... 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. ...

A set is recursively enumerable if and only if it is at level of the arithmetical hierarchy. In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene hierarchy classifies the set of arithmetic formulas (or arithmetic sets) according to their degree of solvability. ...

A set T is called co-recursively enumerable or co-r.e. if its complement is recursively enumerable. Equivalently, a set is co-r.e. if and only if it is at level of the arithmetical hierarchy. In set theory and other branches of mathematics, two kinds of complements are defined, the relative complement and the absolute complement. ...

A set A is recursive (synonym: computable) if and only if both A and the complement of A are recursively enumerable. A set is recursive if and only if it is either the range of an increasing total recursive function or finite. 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. ...

Remarks

According to the Church-Turing thesis, any effectively calculable function is calculable by a Turing machine, and thus a set S is recursively enumerable if and only if there is some algorithm which yields an enumeration of S. This cannot be taken as a formal definition, however, because the Church-Turing thesis is an informal conjecture rather than a formal axiom. 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 . ... Flowcharts are often used to graphically represent algorithms. ...

The definition of a recursively enumerable set as the domain of a partial function, rather than the range of a total recursive function, is common in contemporary texts. This choice is motivated by the fact that in generalized recursion theories, such as α-recursion theory, the definition corresponding to domains has been found to be more natural. Other texts use the definition in terms of enumerations, which is equivalent for recursively enumerable sets.

References

Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0262680521; ISBN 0070535221

Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7

Soare, Robert I. Recursively enumerable sets and degrees. Bull. Amer. Math. Soc. 84 (1978), no. 6, 1149--1181.