12414 - Theorie der Berechenbarkeit Modulübersicht

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