Each formula or function is equivalent to a Turing machine.
Layers in the hierarchy are defined as those forumlas which satisfy a proposition (description) of a certain complexity.
For example, the category , also written as , are those which satisfy propositions with one existential quantifier:
proposition holdsThese are precisely the recursively enumerable sets (think: there exists a program with the following property).
A formula is in the level if it satisfies a proposition quantified first by , and a total of n alternating existential () and universal () quantifiers.
Formulas are classified as in an equivalent fashion, except that the quantifiers commence with .
Formulas are in the level if they are in both and .
Suppose that there is an oracle machine capable of calculating all the functions in a level . This machine is incapable of solving its own halting problem (Turing's proof still applies). The halting problem for in fact sits in .
See also: recursion theory, analytical hierarchy.