Instructor : Yiannis N. Moschovakis, MS 6240, ynm@math.ucla.edu
Teaching Assistant : Humberto Naves, MS 6160, hnaves@math.ucla.edu
Lectures : Monday - Wednesday - Friday, 12:00 - 12:50, MS 5127
Discussion Section : Thursday, 12:00 - 12:50, MS 5127
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.
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. Its main aim is to make precise what it means for a relation to be decidable (by some algorithm) and to prove rigorously that some of the basic relations of mathematics are absolutely undecidable, including provability and truth for (elementary) propositions of number theory. The main heroes whose work will be discussed are Kurt Gödel, Alan Turing, Alonzo Church and Stephen Kleene.
Some of the specific topics covered by the course are: Recursive and effectively computable functions on the natural numbers; the Church-Turing thesis. The Normal form and Enumeration Theorem; the Recursion Theorem; unsolvability and undecidability results. Recursive and recursively enumerable sets; relative recursiveness and the arithmetical hierarchy. The undecidability of elementary provability and truth for arithmetic.
Text: The course will be taught from a set of lecture notes Recursion and Computation which will be posted on the class Homepage and will be available to buy from the UCLA Associated Publishing Services before the beginning of the Winter Quarter.
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 Thursday. It will not be possible to accept late homework.
Grading. The grade will be based on two midterms (about 40% of
the grade), the final exam (about 40%) and the Homework, which
will count for 20%.
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.