Topics include: Turing machines and the Church-Turing thesis Decidability, the halting problem Reducibility, undecidable problems Decidability of logical theories, Kolmogorov complexity Time classes: P, NP, and NP-complete Space classes: Savitch's theorem, PSPACE-completeness, and NL-completeness Hierarchy theorems, approximation algorithms, probabilistic algorithms Parallel computation, cryptography 2004.08