We continue the introduction to the basic mathematical theory of computation. The term will roughly cover three topics.
First, we will introduce the notion of relative computability, use this to define the structure of Turing degrees, and proceed to prove a few structural results about .
Second, we will study the connection between undecidability, mathematical logic, and number theory; in particular, we will provide proofs of Gödel’s incompleteness theorems and of the undecidability of Hilbert’s tenth problem.
Finally, we will discuss examples of undecidability arising in diverse areas of mathematics and computer science.