CSCI 22000 - Theory of Computation

Course Credit: 1
The theory of abstract machines and formal languages is introduced in this course. Computability by finite automata, pushdown automata and Turing machines is examined and related to pattern matching, lexical analysis, compilation and programming for digital computer systems. Proofs by induction, construction, contradiction and reduction are used to formalize computability theory and the limitations of computing. Prerequisite(s): CSCI 12000, and either MATH 21500 OR MATH 22300 Alternate Years.