Computer Science 416/685: Computability Theory
Lehman College, City University of New York
Spring 2008

Instructor:	Dr. Katherine St. John
E-mail:	katherine.stjohn at lehman.cuny.edu
Phone:	718-960-7423
Office:	Gillet 137E
Office Hours:	Tuesdays 12:40-1:30pm (G 219/137) and 3:30-4:20pm (G 137), Thursdays 12:40-1:30pm (G 219/137), and by appointment.
Class Hours:	Tuesdays, Thursdays 9am-10:50am.

Announcements:

• Information about the final exam is now available.
• Since we will not have time to cover Homework 6 (Chapter 3) before the second exam, it will not be included on the exam. Instead, the exam will cover Chapters 0-2, Homeworks 1-5.
• Afternoon office hours will start in Gillet 219 (classroom for my 11am course) and move to Gillet 137 (Prof. St. John's office).
• Who should take this course?  This course is aimed at undergraduate and masters students who are planning doctoral studies in computer science, applied mathematics, or mathematics.  It is required by almost all Ph.D. programs in computer science either the course itself or as prerequisite to the doctoral level course.  Many programs will allow you to "make up" the course during your first year of doctoral study, but it is still worth taking this course earlier rather than later since the material appears on the GRE.  The material is a mixture of computer science and mathematics, so, will be of interest to computer science and applied mathematics students considering doctoral study and mathematics students who are minoring in computer science.
• What is computability theory?  Computability theory studies such questions as "can I find an algorithm that will solve this problem?" and "which problem is harder to compute?" in a rigorous fashion.  We will also cover automata and languages (regular languages, finite state automata, nondeterminism, regular expressions, context-free languages and grammars, and pushdown automata), computability theory (Turing machines, decidability, and reducibility), as well as time and space complexity and intractability.
• Should I sign up for undergraduate or graduate credit?  This course is being taught both as an undergraduate and masters course.  While the lectures will be the same for the two courses, the assignments, reading, and exams will be at a higher level for masters students.  If you are a masters students, you must take the course for graduate credit.  If you are an undergraduate student, it's suggested that you take this for undergraduate credit.  However, if you wish to take the course for graduate credit, you will need to get the permission of the graduate chair, Prof. Berger.

Handouts:

• Syllabus
• Outline
• Academic Integrity Policy (part of the Lehman College undergraduate and graduate bulletins)
• Presentation Schedule
• Assignment 1 (presentations begin 5 February)
• Assignment 2 (presentations begin 14 February)
• Finite State Machine Applet by Matt Chapman
• Assignment 3 (presentations begin 21 February)
• Information about Exam 1
• Assignment 4 (presentations begin 6 March)
• Assignment 5 (presentations begin 18 March)
• Assignment 6 (presentations begin 25 March)
• Turing Machine Links:
  • An overview of Alan Turing's life and work by Andrew Hodges
  • A Turing Machine applet by David Eck.
• Information about Exam 2
• Assignment 7 (presentations begin 29 April)
• Assignment 8 (presentations begin 8 May)
• Information about Final Exam

Useful Links:

• Book's webpage

(This page last updated on 10 March 2008.)