Computer Science 311 - Theory of Computation
Theory of Computation
Fall
2025
01
4.00
Audrey Lee St. John
TTH 09:00AM-10:15AM
Mount Holyoke College
128100
astjohn@mtholyoke.edu
Are there any limits to what computers can do? Does the answer to this question depend on whether you use a PC or a Mac? Is C more powerful than Python? This course explores these questions by investigating several models of computation, illustrating the power and limitations of each of these models, and relating them to computational problems and applications. Topics include finite state automata, pushdown automata, grammars, Turing machines, the Halting Problem, and NP-completeness.
Prereq: COMSC-205 and MATH-232.
This 3-minute student-created video gives an overview: https://www.youtube.com/watch?v=SV57Yv8BXBc.