Recursively enumerable set
Encyclopedia
In computability theory
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...

, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:
• There is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

such that the set of input numbers for which the algorithm halts is exactly the set of numbers in S.

Or, equivalently,
• There is an algorithm that enumerates
Enumeration
In mathematics and theoretical computer science, the broadest and most abstract definition of an enumeration of a set is an exact listing of all of its elements . The restrictions imposed on the type of list used depend on the branch of mathematics and the context in which one is working...

the members of S. That means that its output is simply a list of the members of S: s1, s2, s3, ... . 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
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

, the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...

containing all recursively enumerable sets is RE
RE (complexity)
In computability theory and computational complexity theory, RE is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Informally, it means that if the answer is 'yes', then there is some procedure which takes finite time to...

. In recursion theory
Recursion theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...

, the lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...

of r.e. sets under inclusion is denoted .

## Formal definition

A set S of natural numbers is called recursively enumerable if there is a partial recursive function (synonymously, a partial computable function) whose domain
Domain (mathematics)
In mathematics, the domain of definition or simply the domain of a function is the set of "input" or argument values for which the function is defined...

is exactly S, meaning that the function is defined if and only if its input is a member of S.

The definition can be extended to an arbitrary countable set A by using Gödel number
Gödel number
In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was famously used by Kurt Gödel for the proof of his incompleteness theorems...

s 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.

## 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
Primitive recursive function
The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions...

or empty. Even if S is infinite, repetition of values may be necessary in this case.
Diophantine:
• There is a polynomial p with integer coefficients and variables x, a, b, c, d, e, f, g, h, i ranging over the natural numbers such that
• There is a polynomial from the integers to the integers such that the set S contains exactly the non-negative numbers in its range.

The equivalence of semidecidability and enumerability can be obtained by the technique of dovetailing
Dovetailing (computer science)
Dovetailing in algorithm design, is a technique that interleaves different computations, performing them essentially simultaneously. Algorithms that use dovetailing are sometimes referred to as dovetailers....

.

The Diophantine characterizations of a recursively enumerable set, while not as straightforward or intuitive as the first definitions, were found by Yuri Matiyasevich
Yuri Matiyasevich
Yuri Vladimirovich Matiyasevich, is a Russian mathematician and computer scientist. He is best known for his negative solution of Hilbert's tenth problem, presented in his doctoral thesis, at LOMI .- Biography :* In 1962-1963 studied at Saint Petersburg Lyceum 239...

as part of the negative solution to Hilbert's Tenth Problem
Hilbert's tenth problem
Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900. Its statement is as follows:Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite...

. Diophantine sets predate recursion theory and are therefore historically the first way to describe these sets (although this equivalence was only remarked more than three decades after the introduction of recursively enumerable sets).
The number of bound variables in the above definition of the Diophantine set
Diophantine set
In mathematics, a Diophantine equation is an equation of the form P=0 where P is a polynomial with integer coefficients...

is the best known so far; it might be that a lower number can be used to define all diophantine sets.

## Examples

• Every recursive set
Recursive set
In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set....

is recursively enumerable, but it is not true that every recursively enumerable set is recursive.
• A recursively enumerable language
Recursively enumerable language
In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing-acceptable. It is known as a type-0 language in the Chomsky hierarchy of formal languages...

is a recursively enumerable subset of a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...

.
• 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
Diophantine set
In mathematics, a Diophantine equation is an equation of the form P=0 where P is a polynomial with integer coefficients...

(the converse is trivially true).
• The simple set
Simple set
In recursion theory a subset of the natural numbers is called a simple set if it is recursively enumerable, but every infinite subset of its complement fails to be enumerated recursively...

s are recursively enumerable but not recursive.
• The creative sets are recursively enumerable but not recursive.
• Any productive set
Productive set
In computability theory, productive sets and creative sets are types of sets of natural numbers that have important applications in mathematical logic...

is not recursively enumerable.
• Given a Gödel numbering  of the computable functions, the set (where is the Cantor pairing function  and indicates is defined) is recursively enumerable. This set encodes the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...

as it describes the input parameters for which each Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

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.

## Properties

If A and B are recursively enumerable sets then AB, AB 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.

A set is recursively enumerable if and only if it is at level of the arithmetical hierarchy
Arithmetical hierarchy
In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene-Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them...

.

A set is called co-recursively enumerable or co-r.e. if its complement
Complement (set theory)
In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

is recursively enumerable. Equivalently, a set is co-r.e. if and only if it is at level of the arithmetical hierarchy.

A set A is recursive
Recursive set
In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set....

(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.

Some pairs of recursively enumerable sets are effectively separable and some are not.

## Remarks

According to the Church-Turing thesis, any effectively calculable function is calculable by a Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

, and thus a set S is recursively enumerable if and only if there is some algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

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.

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
Alpha recursion theory
In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals \alpha. An admissible ordinal is closed under \Sigma_1 functions. Admissible ordinals are models of Kripke–Platek set theory. In what follows \alpha is considered to be fixed.The...

, 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.