CSC 8510 :
Theory of Computability

Automata theory: deterministic and non-deterministic finite automata, pushdown automata, regular languages, context-free grammars, pumping lemma. Computability and recursion theory: Turing machines and their variations, decidability and recursive enumerability, mapping reducibility and Turing reducibility, undecidability of the halting problem, logical theories and Godel's incompleteness theorem. Complexity theory: time complexity, space complexity, major open problems on computational complexity. Corequisite: CSC 8301 or degree program in mathematics.