Post's theorem

In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.

The statement of Post's theorem uses several concepts relating to definability and recursion theory. This section gives a brief overview of these concepts, which are covered in depth in their respective articles.

The arithmetical hierarchy classifies certain sets of natural numbers that are definable in the language of Peano arithmetic. A formula is said to be ${\displaystyle \Sigma _{m}^{0}}$ if it is an existential statement in prenex normal form (all quantifiers at the front) with ${\displaystyle m}$ alternations between existential and universal quantifiers applied to a formula with bounded quantifiers only. Formally a formula ${\displaystyle \phi (s)}$ in the language of Peano arithmetic is a ${\displaystyle \Sigma _{m}^{0}}$ formula if it is of the form

...
Wikipedia