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]).
Defined in [Sch16]. Let and where is applied to itself times. For example , , etc. Then define, , note that this has the same growth rate as where A is the Ackermann function. This class is equal to DTIME(Fω(p(n))) over all primitive-recursive functions p(n). The class remains unchanged if we replace DTIME with NTIME or DSPACE.
Strictly contains ELEMENTARY, Tower, and PR. Is strictly contained in R.
The relationship between this class and PR is analogous to the relationship between Tower and ELEMENTARY. That is, Ack contains problems "barely" outside of PR and, unlike PR, has complete problems.
The reachability problems for Petri nets [Ler22] and vector addition systems [CO22] are complete for this class under primitive recursive reductions, as well as the problem of navigating robots through a maze of gadgets with spawner and destroyer nodes [Ani+23].
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.
P equipped with an oracle that, given a string x, returns the length of the shortest program that outputs x.
A similar class was defined in [ABK+02], where it was also shown that PK contains PSPACE. It is not known whether PK contains all of R, or even any recursive problem not in PSPACE.
See also: BPPKT.
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 class of decision problems for which there's a polynomial-time algorithm with the following property. Whenever it's given two instances, a "yes" and a "no" instance, the algorithm can always decide which is the "yes" instance.
Defined in [Sel79], where it was also shown that if NP is contained in P-Sel then P = NP.
There exist P-selective sets that are not recursive (i.e. not in R).
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].
