Di, 19.10.04: Einführung. Die GOTO-Sprache,
G-berechenbare (partielle) Funktionen. Hier finden Sie einen GOTO-Interpreter (in Perl)
und einige Beispielprogramme.
Do, 21.10.04: G-entscheidbare Mengen, berechenbare
Funktionen über beliebigen Wertebereichen, primitiv rekursive
Funktionen und deren G-Berechenbarkeit. Hier finden Sie einen Compiler, der primitiv rekursive Funktionen in GOTO-Programme übersetzt (von Paul Ebermann).
Di, 26.10.04: Primitiv rekursive
Prädikate. Beschränkte Summation, Minimalisierung, und
Quantifizierung. Kodierung von Paaren und Tupeln. Die
Ackermannfunktion.
Do, 28.10.04: Fortsetzung
Ackermannfunktion. Minimalisierung, die Klasse der rekursiven
Funktionen. Die Churchsche These. Kodierung von Listen,
einfache Listenfunktionen, Listenrekursion.
Di, 2.11.04: Numerierung von Programmen und Funktionen,
s-m-n Satz, Padding Lemma, universelle Programme, Kleenescher Normalformsatz
Do, 4.11.04: Effektive Operationen auf berechenbaren
Funktionen und entscheidbaren Mengen, Berechenbarkeit der
Ackermannfunktion, unentscheidbare Mengen, K, Satz von Rice
Di, 9.11.04: Rekursive Aufzählbarkeit und
Semi-Entscheidbarkeit (verschiedene Charakterisierungen), Besipiele
nicht r.e. Mengen, Satz von Rice-Shapiro und Anwendungen
Do, 11.11.04: Beweis des Satzes von Rice-Shapiro,
Fixpunktsatz, Fixpunktsatz mit Parametern
Di, 16.11.04: Zweiter Rekursionssatz mit Anwendungen,
Charakterisierung der berechenbaren Funktionen über
Fixpunktdefinitionen, Many-one Reduktionen Hier finden Sie einige Programme, die den eigenen Code
ausgeben. Viele weitere Programme finden Sie auf der Quine Page.
Do, 18.11.04: m-Äquivalenz und m-Vollständigkeit,
produktive und kreative Mengen, Satz von Myhill.
Di, 23.11.04: Einfache Mengen (Eigenschaften und
Existenz), relative Berechenbarkeit (grundlegende Theorie
parallel zur Standardtheorie).
Do, 25.11.04: Turing Reduktionen, grundlegende
Eigenschaften, die Sprungoperation, die Arithmetische Hierachie
Di, 30.11.04: Charakterisierung der Arithmetischen
Hierachie über "Sprünge der leeren Menge"
Do, 2.12.04: Satz von Post, Endlichkeitslemma
Di, 7.12.04: Klassifikation entscheidbarer Probleme
Do, 9.12.04: Charakterisierung der arithmetischen
Hierarchie über Definierbarkeit in der Logik der ersten Stufe
Di, 14.12.04: Die erstufige Theorie des
Standardmodells der natürlichen Zahlen, der Erste Gödelsche Unvollständigkeitssatz
Di, 4.1.05: Unlösbarkeitsgrade (Einführung,
einfache Eigenschaften), Satz von Kleene und Post
Do, 6.1.05: Satz von Kleene und Post (Beweis zu
Ende), Satz von Friedberg und Muchnik, Grundidee des
Prioritätsarguments
Di, 11.1.05: Beweis des Satzes von Friedberg und
Muchnik, Satz von Dekker
Do, 13.1.05: Sacks'scher Zerlegungssatz
Di, 18.1.05: Folgerungen aus dem Sacks'schen
Zerlegungssatz; f-Bäume, e-zerfällende Bäume
