Theory of Computation
Mon/Wed 11:00 a.m.-12:15 p.m.
This course examines simple models of computation, studying what
computations they can and *cannot* make. We begin with Chapter 2,
Finite State Automata. During the term we go to stronger and
stronger models, ending with Turing Machines and Godel/Turing
results on undecidibility.
Questions about the course? Send me an email, at the address below.
Instructor: Joel Spencer
Office: wwh829, x83219
Required textbook: Elements of the Theory of Computation
Author and Publisher: Lewis & Papadimitriou, publ by Prentice Hall
Edition: 2nd, 1998 [Note: 1st Edition is *not* OK]
ISBN Number: 0-13-262478-8