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 *D* of **Turing degrees**, and proceed to prove a few structural results about *D*.

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.

### Like this:

Like Loading...

*Related*

This entry was posted on December 31, 2006 at 4:10 am and is filed under 117b, Syllabus. 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.