This course studies fundamental computer models and their computational limitations. Finite-state machines and pumping lemmas, the Chomsky hierarchy, Turing machines and algorithmic universality, noncomputability and undecidability, tradeoffs between power and formal tractability.
Prerequisites: CSC 173 & MTH 150.
Last updated 1/31/2007. Maintained by Marty Guenther (marty@cs.rochester.edu)