The arithmetical hierarchy is a classification system for sets based on the complexity of formulas that define them. It was independently invented by Kleene and Mostowski and is important in computability theory, effective descriptive set theory, and the study of formal theories such as Peano arithmetic. The Tarski-Kuratowski algorithm provides an upper bound on the classifications assigned to a formula and the set it defines, while the hyperarithmetical and analytical hierarchies extend the arithmetical hierarchy.
Carnegie Mellon University
Spring 2015
A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.
No concepts data
+ 35 more concepts