Theory of Computation

Catalog description

This course explores what computers can and can't do, although it does not require any background in computer science or programming. Topics include finite state machines, push-down automata, Turing machines and recursive functions; mechanisms for formal languages, such as regular grammars, context-free grammars, context-sensitive grammars; and decidable versus undecidable problems.