** 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