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 , also written as , are those which satisfy propositions with one existential quantifier:

proposition holds

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 .