Computability and Complexity (CoCo)

At course completion, the successful student will have:

Knowledge of

• Computational models such as finite automata, pushdown automata, and Turing machines, the languages recognised by some of these models, and techniques for showing their limitations, such as the pumping lemmas for regular and for context-free languages.
• The power and limits of algorithmic solvability, with focus on the computationally unsolvable Halting problem.
• The reducibility method for proving that additional problems are computationally unsolvable.
• How to analyse algorithms and their time and space complexity and how to classify problems according to the amount of time and space required to solve them.
• Known computational problems that are solvable in principle but not in practice, i.e. intractable problems.

Skills in

• Reading and writing specifications of languages using computational models and grammars.
• Classifying given languages according to type (regular, context-free, etc.) and algorithmic problems according to complexity (time and space).
• Showing the equivalence between certain machine models.
• Presenting the relevant constructions and proofs in writing, using precise terminology and an appropriate level of technical detail.

Competences to

• Reason reliably about language classes and computational models and their strengths and limitations, and about the complexity of algorithms and algorithmic problems.
• Communicate effectively about the theory of computation, both for accessing advanced topics from the research literature, and convincingly presenting the results of own work.