The class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. (If the answer is 'no,' on the other hand, the machine might never halt.)
Equivalently, the class of decision problems for which a Turing machine can list all the 'yes' instances, one by one (this is what 'enumerable' means).
A problem C is complete for RE if (1) C is in RE and (2) any problem in RE can be reduced to C by a Turing machine.
Actually there are two types of reduction: M-reductions (for many-one), in which a single instance of the original problem is mapped to an instance of C, and T-reductions (for Turing), in which an algorithm for the original problem can make arbitrarily many calls to an oracle for C.
RE-complete sets are also called creative sets for some reason.
The canonical RE-complete problem is the halting problem: i.e., given a Turing machine, does it halt when started on a blank tape?
The famous unsolvability of the halting problem [Tur36] implies that R does not equal RE.
Also, RE does not equal coRE.
RE and coRE can be generalized to the arithmetic hierarchy AH.
There are problems in RE that are neither RE-complete under T-reductions, nor in R [Fri57] [Muc56]. This is the resolution of Post's problem [Pos44].
Indeed, RE contains infinitely many nonequivalent 'T-degrees.' (A T-degree is a class of problems, all of which can be T-reduced to one another.) The structure of the T-degrees has been studied in more detail than you can possibly imagine [Sho99].
The analog of PH in computability theory.
Let Δ0 = Σ0 = Π0 = R. Then for i>0, let
Then AH is the union of these classes for all nonnegative constant i.
Each level of AH strictly contains the levels below it.
An equivalent definition is: is the set of numbers decided by formula with one free variable and bounded quantifier, where the primitives are + and . A bounded quantifier is of the form or where is considered to be free in . Then is the sets of number validating a formula of the form with . The set Πi is the set of formula who are negation of formula. And Δi = Σi ∩ Πi.
Usually called AP in the literature. I've renamed it AxP to distinguish it from the "other" AP.
The class of real-valued functions from {0,1}n to [0,1] that can be approximated within any ε>0 by a deterministic Turing machine in time polynomial in n and 1/ε.
Defined by [KRC00], who also showed that the set of AxP machines is in RE.
Does not equal RE.
The problem "given a computable predicate P, is P true of all positive integers?" is coRE-complete.
Same as MIP, except that the provers can share arbitrarily many entangled qubits. The verifier is classical, as are all messages between the provers and verifier.
Defined in [CHT+04], where evidence was given suggesting that MIP* does not "obviously" equal NEXP.
MIP* contains NEXP [IV12]. By contrast, MIP, the corresponding class without entanglement, equals NEXP (and even MIP[2,1] with two provers and one round equals NEXP).
Even MIP*[4,poly] and MIP[5,1] contain NEXP [IV12].
MIP*[2,1] contains XOR-MIP*[2,1].
In 2012 it was shown that QMIP = MIP* [RUV12]
In 2020 it was shown that MIP* = RE [JNVWY20].
Basically, the class of functions definable by recursively building up arithmetic functions: addition, multiplication, exponentiation, tetration, etc. What's not allowed is to "diagonalize" a whole series of such functions to produce an even faster-growing one. Thus, the Ackermann function was proposed in 1928 as an example of a recursive function that's not primitive recursive, showing that PR is strictly contained in R.
Alternatively, the PR functions are exactly those functions that can be computed via programs in any reasonable, idealized ALGOL-like programming language where only definite loops are allowed, that is, loops where the number of iterations is specified before the loop starts (so FOR-loops are okay but not WHILE- or REPEAT-loops), and recursive calls are not allowed.
Alternatively, the PR functions are those functions whose termination can be proved by well-founded induction using an ordinal less than ωω. (There are other systems for higher ordinals. Notably, Gödel's System T is an extension of PR with higher-order functions, and it allows all functions whose termination can be proved by well-founded induction using an ordinal less than ε0, including Ackermann's function.)
An interesting difference is that PR functions can be explicitly enumerated, whereas functions in R cannot be (since otherwise the halting problem would be decidable). In this sense, PR is a "syntactic" class whereas R is "semantic."
On the other hand, we can "enumerate" any RE set by a PR function in the following sense: given an input (M,k), where M is a Turing machine and k is an integer, if M halts within k steps then output M; otherwise output nothing. Then the union of the outputs, over all possible inputs (M,k), is exactly the set of M that halt.
PR strictly contains ELEMENTARY.
The quantum generalization of MIP, and the multi-prover generalization of QIP.
A quantum multi-prover interactive proof system is the same as a classical one, except that all messages and verifier computations are quantum. As in MIP, there is no communication among the provers; however, the provers share unlimited prior entanglement. The number of provers and number of rounds can both be polynomial in n.
Defined in [KM02].
Shown to be equal to MIP* in [RUV12], and thus RE [JNVWY20].
QMIP contains NEXP simply because MIP* contains NEXP [IV12]. Since we know that NEXP = QMIPne, this tells us that giving the provers unlimited prior entanglement does not make the class less powerful.
The class of decision problems solvable by a Turing machine. Often identified with the class of 'effectively computable' functions (the Church-Turing thesis).
Defined in [Tur36], [Chu41], and other seminal early papers.
Strictly contains PR, the primitive recursive functions (see [Kle71]).
