CSC 8510
Theory of Computability
3 Credits Format: lecture Level: graduate
Description: 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.
Textbooks:
- Introduction to the Theory of Computation, 2nd Edition, Sipser, Thompson Course Technology
Objectives: No objective data is available.
Coordinator: Dr. Giorgi Japaridze
Prerequisites: None
Required For:
- M.S. in Computer Science