Inhalte

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 (Churchsche These). Von diesen Berechenbarkeitsmodellen wollen wir hier neben der Turingmaschine auch den Kalkül der rekursiven Funktionen, die Lambda-Berechenbarkeit von Church, die unbeschränkte Registermaschine von Shepherson und Sturgis, die Postschen Systeme, die Markov Algorithmen, u.a. behandeln und ihre Gleichwertigkeit aufzeigen. Viele Aufgaben sind dem Rechner nicht zugänglich. Wir zeigen, daß aber auch unter den mathematisch präzisierbaren Aufgaben bei weitem nicht alle durch Rechner lösbar sind. Wir zeigen weiterhin, daß es in vielen Aufgabenklassen schwerste Aufgaben gibt, deren Lösung auch zu Lösungen aller übrigen Aufgaben der Klasse führt. Zur Klassifikation der nicht berechenbaren Mengen oder Funktionen betrachten wir verschiedene Reduzierbarkeitsbegriffe mit den davon induzierten Unlösbarkeitsgraden (unsolvability degrees). Als Anwendungen dieser Theorie in der klassischen Mathematik untersuchen wir am Ende auch die Berechenbarkeit reeller Zahlen und Funktionen.

Lernziele

Einsicht in die prinzipielle algorithmische Lösbarkeit bzw. Unlösbarkeit von Problemen, in die verschiedenen Präzisierungsversuchen dieser Fragen, in die Graduierungen von Unlösbarkeit und in die Problematik des Begriffs der Berechenbarkeit bei reellen Zahlen und Funktionen.

Prüfungsleistung

Prüfungsgespräch benotet

Literatur (1)

Soare: Enumerable Turing Degrees