Mathematics 114C, Computability Theory, Winter 2017



Instructor : Yiannis N. Moschovakis, MS 6240, ynm@math.ucla.edu
Teaching Assistant: Assaf Shani, MS 2344, assafshani@ucla.edu
Lectures : Monday - Wednesday - Friday, 12:00 - 12:50, MS 5118
Discussion Section: Tuesday, 12:00 - 12:50, Bunche 3117
Conference Hours of Moschovakis : M-W 1:00 - 2:00, F 11:00 - 12:00 and by appointment, best made after class or by email.
Conference Hours of Ashaf: Thursdays 12-1, at MS 2344.
What it is about: This course is aimed at Mathematics majors and mathematically inclined Computer Science and Philosophy majors who have an interest in the foundations of mathematics and theoretical computer science. Its main aim is to make precise what it means for a function on the natural numbers to be computable by some algorithm, and to prove rigorously that some basic mathematical problems are absolutely unsolvable. The main heroes whose work will be discussed are Kurt Gödel, Alan Turing, Alonzo Church, Emil Post and Stephen Kleene.

Text and contents: The course will be taught from a set of lecture notes Recursion and Computation which is posted on the class Homepage and can be bought from the UCLA Associated Publishing Services.

The main part of the course is based on the first four chapters of the Notes which cover the following topics: primitive recursive, μ-recursive and general recursive functions on the natural numbers; the Church-Turing Thesis. The Normal form and Enumeration Theorem; unsolvability and undecidability results. Recursively enumerable, r.e. complete, creative and simple sets; the 2nd Recursion Theorem. Relative recursiveness and the arithmetical hierarchy.
After this, we will cover applications to logic (Tarski's undecidability of arithmetical truth and Gödel's 1st Incompleteness Theorem) in Chapter 4 or some advanced topics on recursive functionals and effective operations in Chapter 5, depending on the time and the interests of the students.

Prerequisites: One of Mathematics 110A or 131A, or Philosophy 135, or consent of the instructor.
To receive the "consent of the instructor" (and the Permit to Enroll that goes with it), you need to send me an email message with a list of the upper division courses in Mathematics, Philosophy or Computer Science that you have taken and your grades in these courses.


Homework
will be assigned on the Homepage of the class and collected in the Section meeting every week. It will not be possible to accept late homework.


Grading
. The grade will be based on two midterms (about 40% of the grade), for which students will be given at least two weeks warning; the final exam (about 30%); and the Homework, which will count for 30%.


Fair warning. This course is more difficult, it is more abstract and it covers substantially more material than the typical, upper division math course. It is especially fast-paced in the beginning, and if you stay behind in the first two weeks, you will never catch up.