Computer Science 311 - Theory of Computation
Fall
2019
01
4.00
Audrey St. John
MW 02:55PM-04:10PM;F 02:55PM-03:45PM
Mount Holyoke College
109313
Clapp Laboratory 206;Clapp Laboratory 206
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 PASCAL? This seminar 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 Universal Turing Machine, and computability.
Prereq: COMSC-201 or COMSC-205; MATH-232.