Berechenbarkeit und Logik

  • Moduldetails

    Dozent: Prof. Dr. Heribert Vollmer

    Frequenz: zweijährlich (ungerade) im Sommersemester

    Veranstaltungsart: Vorlesung, Übung und Seminar (2V + 1Ü + 2S, 7 CP)

    Prüfung: mündl. Prüfung

  • Vorlesungsinhalte

    Das Modul vermittelt vertiefte Kenntnisse über die Problemfelder der Berechenbarkeit und Beweisbarkeit. Nach erfolgreichem Abschluss kennen die Studierenden die Bedeutung der mathematischen Logik für die Informatik. Sie haben Verständnis für die Möglichkeiten und die Grenzen von Berechenbarkeit, Formalisierbarkeit und Beweisbarkeit erlangt. Sie analysieren auftretende Berechnungsprobleme hinsichtlich ihrer Formalisierbarkeit und Lösbarkeit.

    Inhalt:

    In dieser Vorlesung beschäftigen wir uns mit der Frage, welche Berechnungsprobleme überhaupt algorithmisch lösbar sind. Ausgehend von der Unentscheidbarkeit des sog. Halteproblems werden wir verschiedene Stufen der algorithmischen Unlösbarkeit kennenlernen. Besonders interessante Aussagen ergeben sich dabei aus dem Bereich der mathematischen Logik; hier werden wir insbesondere die Gödel'schen Unvollständigkeitssätze behandeln.

    Gliederung:

    • Rekursive Aufzählbarkeit
    • Prädikatenlogik der ersten Stufe
    • Unentscheidbarkeit der Prädikatenlogik der ersten Stufe
    • Beweise in der Prädikatenlogik der ersten Stufe
    • Arithmetische Definierbarkeit
    • Repräsentierbarkeit
    • Der Gödelsche Unvollständigkeitssatz
    • Die arithmetische Hierarchie
    • Relative Berechenbarkeit
  • Informationen zur Prüfung

    Die Abschlussprüfung des Moduls ist eine mündliche Prüfung.

    Termin

    Die Prüfungstermine vergeben wir über eine institutsinterne Website (siehe Link unten). Achtung: Dies ersetzt nicht die Anmeldung der Prüfung im QIS.


    Anmeldung

    Je nach Prüfungsordnung ist eine Anmeldung im QIS erforderlich (siehe Link unten).


    Studienleistung

    Falls Ihre Prüfungsordnung eine Studienleistung für dieses Modul vorsieht, kontaktieren Sie bitte den Dozenten.

Materialien

Alle Materialien finden Sie im Stud.IP.

Prüfungsanmeldung

Online-Anmeldung beim Prüfungsamt
Termin für mündliche Prüfung vereinbaren