CSCI 460 Theory of Computing
David Keil (dkeil@framingham.edu)
Framingham State University, Spring 2012
Assessment
questions (PDF ver.)
Topics (with links to slides and handouts):
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
7. Models of
concurrent and multistream computation
Updated 1/17/12