Logic and
Theory of
Discrete Systems

Informatik 7

Rekursionstheorie

Thema der Vorlesung ist die Theorie der berechenbaren Funktionen. Sie wurde
durch Gödel, Church, Kleene, Turing und Post in den 30er Jahren des
20. Jahrhunderts begründet. Seitdem wurde Berechenbarkeitstheorie als
Teildisziplin der mathematischen Logik weiterentwickelt, gleichzeitig bildet
sie die Grundlage der theoretischen Informatik. Die eleganten Begriffe und
Techniken der Berechenbarkeitstheorie dienen vor allem der Komplexitätstheorie
oft als Vorbild.

Zur Illustration ein Beispiel: Ein Saboteur will durch einen Algorithmus jedes
Programm P, etwa in der Programmiersprache JAVA, so ändern, dass das
entstehende Programm P' etwas anderes leistet als P. Wie kann er das
erreichen? - Gar nicht! Ein Hauptsatz der Berechenbarkeitstheorie besagt, dass
der Saboteur sein Vorhaben nicht verwirklichen kann, egal welchen
Sabotage-Algorithmus er benutzt.

Vorlesungen

Dienstag 10:15-11:45 (Raum 5056) und Mittwoch 10:15-11:45 (Raum 5056)

Übung: Donnerstag 12:15-13:45 (5054)

Die erste Vorlesung findet am 10.10.2017 statt.

 

FaLang translation system by Faboba