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

Background

The statement of Post's theorem uses several concepts relating to definability and computability theory.