Rekursionstheorie (Vorlesung)

Rechner können alles, zumindest alles interessante, oder? - Der Informatik als Wissenschaft liegt der Begriff des "Berechenbaren" zugrunde. Trotzdem es sich dabei um einen intuitiven Begriff handelt, glaubt man fest, das "Berechenbare" durch die bekannten Formalisierungen genau gefaßt zu haben.  Als solche Formalisierungen seien zu nennen: Turing-Maschinen (TM), Random-Access-Maschinen (RAM), partiell-rekursive Funktionen oder bekannte Programmiersprachen. Die untersuchten Objekte sind berechenbare Funktionen und aufzählbare Mengen.

Gemäß unseres Verständnisses bilden die aufzählbaren Mengen genau die von Rechnern lösbaren Probleme. Die Rekursionstheorie untersucht Eigenschaften aufzählbarer Mengen und studiert dabei sowohl die prinzipiellen Möglichkeiten realer Rechner als auch deren Grenzen.

Vorlesungsinhalt

Die zentralen Begriffe der Vorlesung werden berechenbare Funktion und aufzählbare Menge sein. Diese Begriffe werden im ersten Abschnitt der Vorlesung kennengelernt und untersucht. Im weiteren Verlauf werden wir Eigenschaften aufzählbarer Mengen untersuchen. Wir werden untersuchen, wie verschieden oder ähnlich sich aufzählbare Mengen sind, und dabei feststellen, daß die aufzählbaren Mengen eine große Verschiedenheit aufweisen. Wir werden sehen, wie aus schwierigen Mengen noch schwierigere Mengen werden und dabei zur Arithemtischen Hierarchie kommen.

Die Themen der Vorlesung lassen sich so knapp zusammenfassen:

  • Modelle der Berechenbarkeit und die Church-Turing-These
  • Eigenschaften aufzählbarer und anderer Mengen
  • Reduzierbarkeiten
  • die Arithmetische Hierarchie.

Teilnahmevoraussetzung und Einordnung der Vorlesung

Die Vorlesung baut auf den Inhalt der Grundlagenveranstaltung auf. Alle verwendeten Begriffe werden dennoch definiert. Ein Verständnis für formale Methoden und abstrakte Probleme wird allerdings vorausgesetzt.

Die Vorlesung bildet einen der theoretischen Grundpfeiler des Informatik-Studiums. Viele Begriffe anderer Gebiete der theoretischen Informatik, wie zum Beispiel der Komplexitätstheorie, entspringen der Rekursionstheorie.

Termine

Vorlesungfreitags, 8 Uhr c.t.H 6
Übungal gustoH 405

Dozent

Daniel Meister

Prüfungstermine

Die mündlichen Prüfungen finden ab der Woche vom 23.07.2012 statt. Für die Woche vom 15.10.2012 sind Nachprüfungen vorgesehen. Im LSF-Portal angegebene Termine sind pro forma; eine konkrete Terminierung erfolgt auf jeden Fall nach Vereinbarung.