Theory of Computation
Monday-Wednesday 3:30 am - 4:45 pm
Room 513, Warren Weaver Hall
Professor Edmond Schonberg
Room 410, Warren Weaver Hall
Instructor: Edmond Schonberg (email@example.com)
Office hours: Monday-Wednesday 5:00 to 6:30 pm, and by appointment.
Teaching Assistant: Nelly Fazio (firstname.lastname@example.org)
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.
Paper assignments, mid-term examination, final examination, roughly with
the same weight.
Michael Sipser : Introduction to the Theory of Computation (PWS Publishing 2000)
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
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.
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
contents of the message should be the single line:
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
For a flavor of the work expected for this course, see last year's offering