117b – References

There won’t be a required textbook. In lecture, I will mention references according to the topics being discussed. General references that may be useful are:

The incompleteness phenomenon, by M. Goldstern and H. Judah. AK Peters (1998), 1-56881-093-8

Hilbert’s tenth problem, by Y. Matiyasevich. MIT Press (1993), 0-262-13295-8 or 978-0-262-13295-4

Mathematical logic, by J. Shoenfield. ASL (2001), 1-56881-149-7

117b – Grading Policy

Grading will be based on Homework assignments. There will be no exams.

Solutions to homework problems should be written individually, although collaboration is allowed. All references used to solve a problem should be explicitly mentioned, including those students you collaborated with. However, you cannot look up solutions from any source (including other students, earlier years’ solution sets, books, etc).

No late submissions of solutions are allowed, except for medical problems (note needed from the health center) or serious personal difficulties (note needed from the Dean’s office).

Please, and this is very important, make sure that what you turn in is your final solution, as opposed to a draft or your scratch work. Be neat and professional about the appearance of your work. However, if you cannot find a complete solution to a problem, turn in a partial solution, indicating what is missing. Again, this does not mean that you can turn in your scratch work for problems you only have partially completed, but make clear at the beginning of your solution that you did not finish the problem.  

117b – About this course

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.