Incomputability theory andcomputational complexity theory,RE (recursively enumerable) is theclass ofdecision problems for which a 'yes' answer can be verified by aTuring machine in a finite amount of time.^[1] Informally, it means that if the answer to a problem instance is 'yes', then there is some procedure that takes finite time to determine this, and this procedure never falsely reports 'yes' when the true answer is 'no'. However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases. Such a procedure is sometimes called asemi-algorithm, to distinguish it from analgorithm, defined as a complete solution to a decision problem.^[2]

Similarly,co-RE is the set of all languages that arecomplements of a language inRE. In a sense,co-RE contains languages of which membership can be disproved in a finite amount of time, but proving membership might take forever.

Equivalently,RE is the class of decision problems for which a Turing machine can list all the 'yes' instances, one by one (this is what 'enumerable' means).Each member ofRE is arecursively enumerable set and therefore aDiophantine set.

To show this is equivalent, note that if there is a machine${\displaystyle E}$ that enumerates all accepted inputs, another machine that takes in a string can run${\displaystyle E}$ and accept if the string is enumerated. Conversely, if a machine${\displaystyle M}$ accepts when an input is in a language, another machine can enumerate all strings in the language by interleaving simulations of${\displaystyle M}$ on every input and outputting strings that are accepted (there is an order of execution that will eventually get to every execution step because there are countably many ordered pairs of inputs and steps).

The set ofrecursive languages (R) is a subset of bothRE andco-RE.^[3] In fact, it is the intersection of those two classes, because we can decide any problem for which there exists a recogniser and also a co-recogniser by simply interleaving them until one obtains a result. Therefore:

${\displaystyle \text{R}=\text{RE}\cap \text{co-RE}}$.

Conversely, the set of languages that are neitherRE norco-RE is known asNRNC. These are the set of languages for which neither membership nor non-membership can be proven in a finite amount of time, and contain all other languages that are not in eitherRE orco-RE. That is:

${\displaystyle \text{NRNC}=\text{ALL}-(\text{RE}\cup \text{co-RE})}$.

Not only are these problems undecidable, but neither they nor their complement are recursively enumerable.

In January of 2020, a preprint announced a proof thatRE was equivalent to the classMIP* (the class where a classical verifier interacts with multiple all-powerful quantum provers who shareentanglement);^[4] a revised, but not yet fully reviewed, proof was published inCommunications of the ACM in November 2021. The proof implies that theConnes embedding problem andTsirelson's problem are false.^[5]

RE-complete is the set of decision problems that are complete forRE. In a sense, these are the "hardest" recursively enumerable problems. Generally, no constraint is placed on the reductions used except that they must bemany-one reductions.

Examples of RE-complete problems:

1. Halting problem: Whether a program given a finite input finishes running or will run forever.
2. ByRice's theorem, deciding membership of a in any nontrivial subset of the set ofpartial recursive functions isRE-hard. It will be complete whenever the set is recursively enumerable.
3. John Myhill (1955)^[6] proved that allcreative sets areRE-complete.
4. The uniformword problem forgroups orsemigroups. (Indeed, theword problem for some individual groups isRE-complete.)
5. Deciding membership in a generalunrestrictedformal grammar. (Again, certain individual grammars haveRE-complete membership problems.)
6. Thevalidity problem forfirst-order logic.
7. Post correspondence problem: Given a list of pairs of strings, determine if there is a selection from these pairs (allowing repeats) such that the concatenation of the first items (of the pairs) is equal to the concatenation of the second items.
8. Determining if aDiophantine equation has any integer solutions.

co-RE-complete is the set of decision problems that are complete forco-RE. In a sense, these are the complements of the hardest recursively enumerable problems.

Examples of co-RE-complete problems:

1. Thedomino problem forWang tiles.
2. Thesatisfiability problem forfirst-order logic.

• Knuth–Bendix completion algorithm
• List of undecidable problems
• Polymorphic recursion
• Risch algorithm
• Semidecidability

• Complexity classes
• Undecidable problems

• Articles with short description
• Short description matches Wikidata