63.460 Theory of
Computing
David Keil (dkeil@frc.mass.edu)
Assessment
questions (PDF ver.)
Topics (with slides):
Discrete Math
and Data Structures review
1. Uncountable
sets
Diagonal proofs
2. Deterministic finite
automata, regular languages, and lexical analysis
3. Pushdown automata,
context-free grammars, and parsing
4. Turing machines and
undecidability
Equivalence of 1-tape
and 2-tape TMs
5. Random-access
machines and recursively definable functions
6. Models of
interactive computation
Peter
Wegner, Why Interaction Is More Powerful Than Algorithms
Dina Goldin,
Persistent Turing Machines as a Model of Interactive Computation