Class Description

AH: Arithmetic Hierarchy

The analog of PH in computability theory.

Let Δ₀ = Σ₀ = Π₀ = R. Then for i>0, let

• Δ_i = R with Σ_i-1 oracle.
• Σ_i = RE with Σ_i-1 oracle.
• Π_i = coRE with Σ_i-1 oracle.

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: ${\displaystyle \Sigma _{0}=\Delta _{0}=\Pi _{0}}$ is the set of numbers decided by formula with one free variable and bounded quantifier, where the primitives are + and ${\displaystyle \times }$. A bounded quantifier is of the form ${\displaystyle \phi =\forall i<j\psi }$ or ${\displaystyle \phi =\exists i<j\psi }$ where ${\displaystyle j}$ is considered to be free in ${\displaystyle \phi }$. Then ${\displaystyle \Sigma _{i+1}}$ is the sets of number validating a formula of the form ${\displaystyle \exists X_{1}\dots \exists X_{n},\psi }$ with ${\displaystyle \psi \in \Delta _{i}}$. The set Π_i is the set of formula who are negation of ${\displaystyle \Sigma _{i}}$ formula. And Δ_i = Σ_i ∩ Π_i.

Linked From

RE: Recursively Enumerable Languages

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

More about...