**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

**which is posted on the class Homepage and can be bought from the UCLA Associated Publishing Services.**

*Recursion and Computation*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.*