Computer Science 416/685: Computability Theory
Lehman College, City University of New York
Spring 2004
Instructor:Dr. Katherine St. John
E-mail: stjohn@lehman.cuny.edu
Phone: 718-960-7423
Office: Gillet 137D
Office Hours: Thursdays 8-8:50am, 11am-12:50pm and by appointment
Lecture: Tuesdays & Thursdays 9-10:50am
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:
Useful Links: