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.