Theory of Computation

V22.0453 .01
Fall 2002

Monday-Wednesday 11:00 am - 12:15 pm
Room 102, Warren Weaver Hall

Professor Edmond Schonberg
Room 410, Warren Weaver Hall

Instructor: Edmond Schonberg (schonberg@cs.nyu.edu)

Office hours: Monday-Wednesday 5:00 to 6:30 pm, and by appointment.

Teaching Assistant: Ji-Ae Shin (jiae@cs.nyu.edu)

Objectives

We will examine the foundations of our profession: how can we formalize the notion of computation, what mathematical descriptions can we give of different models of computation, what are the limits of computation (are there precisely formulated problems which no computation can answer?) and finally, how fast can we compute the answer to various classes of problems. This study has a mathematical flavor, and we will present arguments in a reasonably rigorous manner, with theorems and their proofs. We will try to keep in sight the actual practice of writing programs, even though the course will not have a required programming component. The topic itself is one of the great intellectual achievements of the last 80 years, and has had a cultural impact much beyond Computer Science per se.

Course Work

Paper assignments, mid-term examination, final examination, roughly with the same weight.

Textbooks

required:

Michael Sipser : Introduction to the Theory of Computation (PWS PUblishing 2000)

Recommended :

There are numerous texts on the subject, that you may want to consult. A good modern one is: "Introduction to Automata Theory, Languages, and Computation" by Hopcroft, Motwani, and Ullman.
An excellent survey of the historical origins of computers, fueled by efforts to mechanize Logic, can be found in Martin Davis's book "The Universal Computer: the road from Leibnitz to Turing", recently reprinted in paperback as "Engines of Logic".

Class list

All students should register themselves with the class list, which is used for all technical discussions concerning the course. To register, go to the following web page, and follow the instructions:

cs.nyu.edu/mailman/listinfo/v22_0453_001_fa02

You can also subscribe by sending an e-mail message to majordomo@cs.nyu.edu. The contents of the message should be the single line:
     subscribe v22_0453_001_fa02
you will be notified in return that you are a list participant. Please send all your questions to this list (not to the instructor) so that everyone can participate.

Assignments

Assignment I
Assignment II
Assignment III
Assignment IV
Assignment V
Assignment VI