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

Announcements:

• 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. Schneider.

Handouts:

• Syllabus
• Outline
• Academic Integrity Policy (part of the Lehman College undergraduate and graduate bulletins)
• Presentation Schedule
  
• Assignment 1 (presentations begin 5 February)
• Finite State Machine Applet by Matt Chapman.
• Assignment 2 (presentations begin 17 February)
• Assignment 3 (presentations begin 24 February) 
• Assignment 4 (presentations begin 16 March)
• Exam 1 Information (Thursday, 11 March)
• Assignment 5 (presentations begin 1 April)
• Turing Machine Links:
  
  • An overview of Alan Turing's life and work by Andrew Hodges
  • A Turing Machine applet by David Eck.
  • A Turing Machine applet by H. Weber.
• Assignment 6 (presentations begin 15 April)
• Some links on induction:
  
  • A 60 Second Introduction to Induction by Lyman S. Taylor (Georgia Tech)
  • Overview from computabilty course at Stanford University.
    

Useful Links:

• Book's webpage