Theorie der Berechenbarkeit
Computability Theory
8 CPirregularlyDEno longer offered
Contents
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.
Learning outcomes
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.
Assessment
Prüfungsgespräch benotet
Literature (1)
- Soare: Enumerable Turing Degrees
Source: BTU's module description · retrieved 14 Oct 2026Original