Dieses Modul dient dazu, auf mathematisch präzise Weise Antworten auf die folgenden Fragen zu vermitteln: Was können Computer berechnen und was nicht? Wie klassifiziert und vergleicht man Berechnungsprobleme gemäß des zu ihrer Lösung notwendigen Aufwands? Wie definiert man die Syntax von textuellen Objekten? Wie definiert man ihre Semantik? Was bedeutet Korrektheit und wie weist man sie nach?
Das Modul behandelt die Grundzüge der Rekursionstheorie, der Komplexitätstheorie, der Theorie der formalen Sprachen, der Automatentheorie und der Korrektheitstheorie. Zentrale Begriffe sind Berechenbarkeit, Entscheidbarkeit und Semi-Entscheidbarkeit, Reduzierbarkeit, Komplexitätsklassen, Vollständigkeit, Schwerlösbarkeit, Automaten, Grammatiken, Ausdrücke, Korrektheitsaussagen, Kalküle und (relative) Vollständigkeit.
G1.1, G2.1
schriftliche Teilprüfungen und Abschlussprüfung
Michael Sipser, Introduction to the Theory of Computation, 2nd Ed., Boston: PWS, 2005.