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