Thema: Theorie der Berechenbarkeit (Rekursionstheorie)

Vorkenntnisse: Vorlesung Informatik III "Grundlagen der Theoretischen Informatik".

Inhalt: In der Theorie der Berechenbarkeit geht es u.a. um die Frage, welche Aufgaben prinzipiell durch Rechner gelöst werden können. Zu der Frage, was berechenbar heißen soll, hat man viele Ansätze entwickelt, die sich als äquivalent erwiesen haben (Churche These). Viele Aufgaben sind dem Rechner nicht zugänglich. Wir zeigen, dass aber auch unter den mathematisch präzisierbaren Aufgaben bei weitem nicht alle durch Rechner lösbar sind. Wir zeigen weiterhin, dass es in vielen Aufgabenklassen schwerste Aufgaben gibt, deren Lösung auch zu Lösungen aller übrigen Aufgaben der Klasse führt. Wir werden in diesem Seminar die verschiedenen Versionen des Berechenbarkeitsbegriffes durchgehen. Zur Klassifikation der nicht berechenbaren Mengen oder Funktionen betrachten wir weiterhin verschiedene Reduzierbarkeitsbegriffe mit den davon induzierten Unlösbarkeitsgraden (unsolvability degrees). (Säule Grundlagen der Informatik)