Modulnummer:
| 12414
- Modul nicht mehr im Angebot ab WS 2008/9 |
Modultitel: | Theorie der Berechenbarkeit |
|
Computability Theory
|
Einrichtung: |
Fakultät 1 - Mathematik, Naturwissenschaften und Informatik
|
Verantwortlich: | -
Prof. Dr.rer.nat.habil von Braunmühl, Burchard
|
Lehr- und Prüfungssprache: | Deutsch |
Dauer: | 1 Semester |
Angebotsturnus: |
sporadisch nach Ankündigung
|
Leistungspunkte: |
8
|
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. |
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. |
Empfohlene Voraussetzungen: | keine |
Zwingende Voraussetzungen: | keine |
Lehrformen und Arbeitsumfang: | -
Vorlesung
/ 4 SWS
-
Übung
/ 2 SWS
|
Unterrichtsmaterialien und Literaturhinweise: | Soare: Enumerable Turing Degrees |
Modulprüfung: | Keine Angabe - Angabe ab Wintersemester 2016/17 erforderlich! |
Prüfungsleistung/en für Modulprüfung: | Prüfungsgespräch benotet |
Bewertung der Modulprüfung: | Prüfungsleistung - benotet |
Teilnehmerbeschränkung: | keine |
Zuordnung zu Studiengängen: | - keine Zuordnung vorhanden
|
Bemerkungen: | keine |
Veranstaltungen zum Modul: | keine |
Veranstaltungen im aktuellen Semester: | - keine Zuordnung vorhanden
|