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 ofHilbert’s tenth problem.

Finally, we will discuss examples of undecidability arising in diverse areas of mathematics and computer science.

This entry was posted on Sunday, December 31st, 2006 at 4:10 am and is filed under 117b: Computability theory. You can follow any responses to this entry through the RSS 2.0 feed.
Responses are currently closed, but you can trackback from your own site.