Deeper Computability

In this Chapter, we will develop a number of more advanced tools we can use to tackle issues in computability theory. In particular, we will be able to deal with problems more complex than the halting problem, as delve more deeply into the fine structure of reducibilities and noncomputable sets. We introduce Turing reducibility. We prove the s-m-n theorem and recursion theorem. We will look at computable structure theory via computable linear orderings. We introduce the arithmetical hierarchy and show how definability aligns with computation. Finally we will look at constructions in the Turing degrees including the finite extension and finite injury methods, showing how Post’s Problem was solved.