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

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

** Teaching Assistant:** Nelly Fazio (fazio@cs.nyu.edu)

## Objectives

We will examine the intellectual 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.
We will examine the intimate relation between classes of computational
problems and languages, and touch on issues of programming and compiling.
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".

A lengthy and entertaining survey of languages, Turing machines, and computability
is "Godel, Escher, Bach" by Douglas Hofstadter. Much of his discussion on
artificial Intelligence is dated, but much of the book is still fun to read.
## 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_fa03

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_fa03

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.

For a flavor of the work expected for this course, see last year's offering
at
theory_of_computation_fall02

Assignment I

Assignment II

Assignment III

Solution (pdf)

Assignment IV

Assignment V

Solution (pdf)

Assignment VI

Assignment VII

Syllabus