Computability and Complexity (CoCo) is a course covering the theoretical subjects of what is computable by various types of machines and the complexity (running time and space usage) of the computable things.

CoCo largely is about the theoretical structure around languages (sets of strings). One can define problems as a language and then consider how a machine may define such a language.

CoCo covers some things also covered in Implementering af Programmeringssprog, namely, deterministic finite automata, non-deterministic finite automata and context-free grammars. It also covers push-down automata and Turing machines.

The deterministic and non-deterministic finite automata correspond to the regular languages, which can also be described by regular expressions.

The push-down automata describes the same languages as those described by context-free grammars.

Finally the course spends a long time on Turing machines and what is computable/non-computable (decidable/undecidable) on a Turing machine. Turing machines are a theoretical machine that works slightly differently to modern day computers, but nevertheless can do all the same things.