Mathematics 114C Winter 2009

Computability Theory

CANCELED

Math 114C has been canceled for winter 2009. Students wishing to study the material as a Math 197 reading course should consult the instructor.

The Mathematics Department's undergraduate logic courses have recently been re-numbered as follows:

Math 114C: Computability Theory. Offered every other year, alternating with 114S.
Math 114L: Mathematical Logic. Offered every year.
Math M114S: Set Theory. Offered every other year, alternating with 114C.

There are no longer courses numbered 114A or 114B.

Instructor for 114C: Herbert B. Enderton.
hbe@math.ucla.edu Office MS 7905. Office hours Mon & Wed 2:00-3:30. Also we have "virtual office hours" for the course.

Teaching Assistant:

Topics for 114C:

Making the computability concept into mathematics: Turing machines and other models.
The unsolvability of the halting problem, which shows that you can't do everything.
Decidable sets, effectively enumerable sets, and others.
Connections to logic: definability of computable sets. The Gödel incompleteness theorem.
Feasible computability: P and NP.

These subjects are relevant to theoretical computer science and to the philosophy of mathematics, as well as to mathematics.

Prerequisites: There is no specific body of information that is required. But our main order of business is proving theorems (not calculating numbers or writing programs). For this reason, you should have some positive experience with proofs before taking this course.

Textbook: The only text will be course notes, which are posted on the website.

Homework: Yes! Although the homework problem sets account for only a small part of the course grade, you should definitely do them, in order to master the material. Besides, every little bit helps, especially if the tests do not all go well. Late homework will normally not be graded.

Tests: There will be two midterms and a final, on dates TBA.

Grading: The final exam constitutes a large part of the grade. The two midterms together constitute another large part. The homework accounts for a small part. ("Large" means 40-50%. "Small" means no more than 10%.) To get an Incomplete grade, you must be doing passing work when struck by unforeseen external disaster.

Website: http://www.math.ucla.edu/~hbe/114c.1.09w