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.
Evaluation
Oral examination, 13-scale
Lecturers
Ulrich Kohlenbach and Mogens Nielsen
Credits
2 points/10 ECTS
Semester
Spring