Models and Logics
Goals The aims of this course are to provide the students with a basic knowledge of fundamental parts of theoretical computer science, including automata, logic and computability.
Contents Regularity: Finite automata, regular grammars, regular expressions, properties of these including their expressive equivalence and their limitations.
Computability: Turing machines and their languages, universality, undecidability - including the Halting problem.
Logic: Logical expressions, satisfiability and validity, first order logic, proof systems, completeness, Gödel's incompleteness theorem.
Lecturers Ulrich Kohlenbach and Mogens Nielsen
Credits 10 ECTS