Theory of Computation

Spencer, Joel

Mon/Wed 11:00 a.m.-12:15 p.m.

CIWW 102

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 Email: spencer@cs.nyu.edu 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