Introduction to Theory of Computing

3 credits

Characterizations of computability (using machines, languages and functions). Universality, equivalence and Church's thesis. Unsolvable problems. Restricted models of computation. Finite automata, grammars and formal languages. [3-0-0] Prerequisite: One of CPSC 320 or MATH 220 or MATH 226.