New blog, and 117b – About this course

This is the first post of this blog (an older one having perished unceremoniously).

117b is the second of a three-part course at Caltech on the basics of computability theory and computational complexity theory. This part is devoted to introducing 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.

Advertisement