63.460 Theory of Computing
David Keil (
Topics (with slides):
Introduction
and discrete math review
1. Cardinalities of sets
Diagonal proofs
Gödel’s Theorem
2. Deterministic finite
automata, regular languages, and lexical analysis
3. Pushdown automata,
context-free grammars, and parsing
4. Turing machines and
undecidability
5. Random-access
machines and recursively definable functions
6. Models of interactive,
parallel, and distributed computation