Theory of Computation

V22.0453 .01
Fall 2003

Monday-Wednesday 3:30 am - 4:45 pm
Room 513, Warren Weaver Hall

Professor Edmond Schonberg
Room 410, Warren Weaver Hall

Instructor: Edmond Schonberg (

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

Teaching Assistant: Nelly Fazio (


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.



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:

You can also subscribe by sending an e-mail message to 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.


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