Computability and Complexity

3 credits

Finite automata. Context-free grammars and push-down automata. Turing machine. The universal Turing machine. Nondeterministic Turing machine. The halting problem and unsolvability. Post correspondence problem. Time complexity. Space complexity.