Arithmetical hierarchy

Each formula or function is equivalent to a Turing machine.

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

For example, the category <math>\Sigma_1</math>, also written as <math>\Sigma_1^0</math>, are those which satisfy propositions with one existential quantifier:

<math>\exists x_1 : </math> proposition holds

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

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

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

Formulas are in the level <math>\Delta_n^0</math> if they are in both <math>\Sigma_n^0</math> and <math>\Pi_n^0</math>.

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

See also: recursion theory, analytical hierarchy[?].