Geology students reviewing a topographical map. background

Course Catalog

Theory of Computation

This is a lecture and laboratory course that formalizes a definition of a computation model and uses it to study the fundamental question, “What can and cannot be computed?” Students study deterministic and non-deterministic computational models, such as finite automata, push-down automata and Turing machines, as well as regular expressions and grammars. Types of problems that can and cannot be solved by each of these models of computation are identified. The Church/Turing thesis, which attempts to describe what is and is not solvable by our current model of computation, is also studied. Prerequisite: CSCI 220. Alternate years.

Grade Basis: Letter Grade
Credits: 4.0