encyclopedia

Arithmetical hierarchy

In mathematical logic, the arithmetical hierarchy (also known as the arithmetic hierarchy) classifies the set of all formulas (or functions) according to their degree of solvability.

Each formula or function is equivalent to a Turing machine.

Layers in the hierarchy are defined as those formulas which satisfy a proposition (description) of a certain complexity.

For example, the category $Σ 1$ , also written as $\Sigma_1^0$ , are those which satisfy propositions with one existential quantifier:

$\exists x_1 :$ proposition holds

These are precisely the recursively enumerable sets (think: there exists a program with the following property).

A formula is in the level $\Sigma_n^0$ if it satisfies a proposition quantified first by $\exists$ , and a total of n alternating existential ( $\exists$ ) and universal ( $\forall$ ) quantifiers.

Formulas are classified as $\Pi_n^0$ in an equivalent fashion, except that the quantifiers commence with $\forall$ .

Formulas are in the level $\Delta_n^0$ if they are in both $\Sigma_n^0$ and $\Pi_n^0$ .

Suppose that there is an oracle machine capable of calculating all the functions in a level $\Delta_n^0$ . This machine is incapable of solving its own halting problem (Turing's proof still applies). The halting problem for $\Delta_n^0$ in fact sits in $\Delta_{n+1}^0$ .

Post's theorem describes the close connection between the arithmetical hierarchy and the Turing degrees.

The polynomial hierarchy is a "feasible resource-bounded" version of the arithmetical hierarchy, in which polynomial length bounds are placed on the strings involved, or equivalently, polynomial time bounds are placed on the Turing machines involved.

References

G.Japaridze, The logic of the arithmetical hierarchy. In: Annals of Pure and Applied Logic 66 (1994), pp.89-112.

Categories: Computability | Set theory

The contents of this article are licensed from Wikipedia.org under the GNU Free Documentation License.
How to see transparent copy

01-04-2007 01:21:04

| | | |