CSCI-572 : Computability and Complexity
This course explores the relationship between problems, algorithms, and languages. Computability: finite automata, rewriting systems, Turing machines (linear speedup, robustness, and the Universal Turing machine). It presents recursive and recursively enumerable languages, the Church-Turing thesis, and complexity classes defined in terms of time, space, and circuits.