CSC 280: Computer Models and Limitations

Spring 2007 Information

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)