Theory of Computation
CSCI 361 / Math 361
Fall 2021
Catalog Description
This course introduces a formal framework for investigating both the computability and complexity of problems. We study several models of computation including finite automata, regular languages, context-free grammars, and Turing machines. These models provide a mathematical basis for the study of computability theory--the examination of what problems can be solved and what problems cannot be solved— and the study of complexity theory—the examination of how efficiently problems can be solved. Topics include the halting problem and the P versus NP problem.
Meetings
Instructor
Aaron Williams
Office: TBL 309A and Schow SSL 014
Phone: (413) 597-2774
Materials and Syllabus
Materials for the course are hosted on Google Classroom and are available only to students enrolled in the class.
Please contact the instructor for a copy of the syllabus.