Concept
Post's theorem
Overview
In computability theory, Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Related ideas
- First-order logic
- Computability theory
- Truth value
- Turing machine
- Emil Leon Post
- Structure (mathematical logic)
- Universal quantification
- Turing degree
- Decision problem
- Empty set
- Turing reduction
Place in the tradition
Part of Outline of logic.