Dozent: Herr Dr. Merlin Carl
Termin und Raum: Mittwoch 11.45-13.15, Raum D436.
Übungstermin ist Donnerstag von 15.15-16.45 in Raum D431. Die Übungen finden wöchentlich statt, beginnend am 02.05.2013.
Hier finden Sie den Eintrag im Vorlesungsverzeichnis mit weiteren Informationen.
Grundlagen und Inhalte
Der Begriff der Berechnung ist, neben dem des Beweises, einer der zentralen Begriffe der Mathematik. Mit dem Aufkommen formaler Berechenbarkeitskonzepte zu Beginn des 20. Jahrhunderts wurde dieser Begriff erstmals einer präzisen mathematischen Behandlung zugänglich. Die Angemessenheit dieser Konzepte an den intuitiven Begriff von Berechenbarkeit ist u.a. dadurch eindrucksvoll abgesichert, dass alle Präzisierungsversuche sich bisher als äquivalent erwiesen haben. Insbesondere wurde es damit möglich, Grenzen des Berechenbaren aufzuzeigen, indem man beweist, dass gewisse Probleme prinzipiell überhaupt nicht oder nur mir nicht realisierbarem Aufwand an Zeit und Speicherplatz durch Berechnungen gelöst werden können. Ein prominentes Beispiel ist z.B. das Resultat von Matiyasevich, dass es unmöglich ist, eine Berechnungsvorschrift anzugeben, die die Lösbarkeit diophantischer Gleichungen entscheidet. Da digitale Computer als begrenzte Realisierungen dieser Konzepte betrachtet werden können, sind solche Ergebnisse auch von praktischem Interesse. Der Begriff der Turing-Berechenbarkeit spielt darüber hinaus in verschiedenen Bereichen der Mathematik (z.B. in der Logik, der Modelltheorie, der Beweistheorie) sowie der theoretischen Informatik, der künstlichen Intelligenz, der Philosophie des Geistes, den Kognitionswissenschaften und gewissen Zweigen der Biologie eine wesentliche Rolle.
Als Themen sind vorgesehen: Formale Modelle der Berechenbarkeit (Turingmaschinen, rekursive Funktionen, Registermaschinen), Rekursionssätze, rekursive und rekursiv aufzählbare Mengen, Unmöglichkeitsresultate, Berechenbarkeit und Beweisbarkeit sowie ggf. elementare Komplexitätstheorie, Turinggrade und Hilbert's zehntes Problem.
Literatur zur Vorlesung
Cutland: "Computability - An Introduction to Recursive Function Theory"
Ebbinghaus/Flum/Thomas: "Einführung in die mathematische Logik"
Informationen zur Benotung und der Klausur
Die Note wird durch eine Abschlussklausur ermittelt. Zum Bestehen außerdem
erforderlich ist das Erreichen von mindestens 50% der Übungspunkte.
Die Klausur findet statt am Donnerstag, dem 01.08.2013 ab 15.15 in Raum D431
Übungsblätter
Die Bearbeitungen der Übungsblätter sind am Übungstermin der auf die Ausgabe folgenden Woche abzugeben.
Hinweis: Gegenüber der Fassung, die hier eingestellt wird, können sich bis zur Ausgabe noch einzelne Änderungen ergeben. Gültig ist jeweils die Fassung, die in der Vorlesung als Ausdruck ausgeteilt wird.
Hier finden Sie einige Anmerkungen und Korrekturen zur Vorlesung und den Übungen .
Ein Video , das eine physikalische Realisierung einer Turingmaschine (mit endlichem Band) bei der Arbeit zeigt.
Ein Gedicht , das einen Beweis für die Unlösbarkeit des Halteproblems darstellt (erforderlich für die Zusatzaufgabe von Blatt 8).
Hier finden Sie ein kleines Prolog-Programm zur Simulation von URMs.
(Disclaimer: Der Autor des hier zum Download dargebotenen Programmes haftet nicht für Schäden an Soft- oder Hardware, die durch das Benutzen des Programmes entstehen.)
Zum Ausführen benötigen Sie eine für Ihr Betriebssystem geeignete Version von SWI-Prolog, die Sie hier herunterladen können.
Kurzanleitung: Ein URM-Programm wird als Liste von Paaren geschrieben, wobei der erste Eintrag die Programmzeile, der zweite den Befehl darstellt. Die Befehle werden wie folgt dargestellt:
Nachfolgerbefehl: [s,I], wobei I der Index des angesprochenen Registers ist.
Nullbefehl: [z,I], wobei I der Index des angesprochenen Registers ist.
Transferbefehl: [t,I,J] (kopiert den Inhalt von Register I in Register J)
Sprungbefehl: [j,I,J,Z] (springt in Zeile Z, falls die Registerinhalte der Register I und J gleich sind, andernfalls zur folgenden Zeile)
Ein gültiges Programm sieht also z.B. so aus: [[1,[s,2]],[2,[j,1,2,1]],[3,[s,3]],[4,[t,3,1]]]
Weiter wird eine Registerbelegung als Liste von Paaren geschrieben, wobei der erste Eintrag den Registerindex, der zweite den Registerinhalt darstellt (natürlich sind diese Listen endlich und sollten nur
die für ein Programm relevanten Register enthalten). Eine gültige Registerbelegung ist z.B. [[1,4],[2,6],[3,9]].
Schließlich ist ein Programmzustand ein Paar [Z,R], wobei Z der Index der aktiven Programmzeile und R die aktuelle Registerbelegung ist, also z.B. [1,[[1,4],[2,6],[3,9]]].
Der Simulator kennt zwei Befehle: Um den Simulator mit einem Programm P und einem Anfangszustand S für K viele Schritte laufen zu lassen, geben Sie in die Prolog-Befehlszeile das Kommando
"execute(P,S,K,_)." ein.
Um den Simulator mit einem Programm P und einem Anfangszustand S so lange laufen zu lassen, bis P stoppt, geben Sie in die Prolog-Befehlszeile das Kommando
"execute(P,S,inf,0,_)." ein. (Warnung: Falls P nicht hält, wird auch der Simulator nicht anhalten und Sie müssen das Programm von außen beenden.)