Mo, 12.4.10: Allgemeine Notation; Syntax und Semantik von
GOTO-Programmen; Berechenbare Funktionen; Beispiele
Do, 15.4.10: Existenz nichtberechenbarer totaler
Funktionen; Entscheidbare Prädikate; Kodierungen und
berechenbare Funktionen über anderen Wertebereichen;
GOTO-Programme über anderen Funktionen bzw. mit
Unterprogrammen; primitiv rekursive Funktionen
Mo, 19.4.10: Beispiele primitiv rekursiver
Funktionen; primitiv rekursive Prädikate; Abschluss unter
quantorenfreier Logik, beschränkter Summation und
Produktbildung, beschränkten Quantoren, beschränkter
Minimalisierung; Kodierung von Paaren und Tupeln; die
Ackermannfunktion
Do, 22.4.10: Beweis, dass die Ackermannfunktion
nicht primitiv rekursiv ist; Minimalisierung; rekursive Funktionen
Mo, 26.4.10: rekursiv = berechenbar; Syntax und Semantik des
λ-Kalküls
Do, 29.4.10: Programmieren im λ-Kalkül
Mo, 3.5.10: Fixpunktsatz für den λ-Kalkül;
λ-definierbar = berechenbar; Church-Turingsche These;
Kodierung von Listen
Do, 6.5.10: Programmieren mit Listen;
Listenrekursion; Kodierung von Programmen und Indizes
berechenbarer Funktionen; s-m-n Satz
Mo, 10.5.10: Paddinglemma; Satz über universelle
Funktionen; Kleene'scher Normalformsatz; Anwendungen
Do, 20.5.10: die Menge K; Unentscheidbarkeit des
Halteproblems; Satz von Rice, Charaktersierungen von rekursiver
Aufzählbarkeit
Do, 27.5.10: Charaktersierung von Entscheidbarkeit
durch rekursive Aufzählbarkeit; Definition partieller
Funktionen durch Fallunterscheidungen; Satz von Rice und
Shapiro
Mo, 31.5.10: Kleene'sche Fixpunktsatz; Fixpunktsatz
mit Parametern; Zweiter Rekursionssatz; Anwendungen
Mo, 21.6.10: Rekursiv aufzählbare Grade; Satz von
Kleene und Post
Do, 24.6.10: Satz von
Friedberg und Muchnik; vorbereitende Lemmata; Beweisidee
Mo, 28.6.10: Beweis des Satzes von Friedberg und
Muchnik; Übersicht über weitere Sätze über
rekursiv aufzählbare Grade; Sprungoperator
Do, 1.7.10: Sprünge von Mengen und Graden;
Definition der arithmtischen Hierarchie; Charakterisierung über Sprünge der
leeren Menge; Kleene'scher Hierarchiesatz; Satz von Post;
Abschlusseigenschaften der Stufen der Hierarchie
Mo, 5.7.10: Abschlusseigenschaften; Satz von Post; Vollständigkeit
Do, 8.7.10: Vollständigkeitsresultate für die
ersten Stufen der arithmetischen Hierarchie
Last modified: Mon Aug 2 14:44:56 CEST 2010
Martin Grohe
