Vortragsankündigung, Bereichsseminar Theoretische Informatik,
Dienstag, den 2. Mai 00, 15:15 - 16:45, Raum 3-68, Hauptgebäude
Dr. J. Waldmann, Institut für Informatik, Universität Leipzig

Aktuelles aus der Kombinatorischen Logik

Die Kombinatorische Logik (Schönfinkel 1924, Curry 1930) ist ein Kalkül für logische und funktionale Formeln. Sie steht damit dem Lambda-Kalkül nahe, kommt aber ganz ohne Variablen aus.

Heute scheint ihre ``historische Aufgabe'' erfüllt: Semantisch gesehen hat man kombinatorische Vollständigkeit und kann damit Modelle für den Lambda-Kalkül basteln (Barendregt et al, ca. 1980); gleichzeitig eröffnet das die Möglichkeit, funktionale Programme in (Super-)Kombinatoren zu übersetzen (Bird et al, ca. 1980) Syntaktischerseits war die Betrachtung von Eigenschaften der CL-Reduktionsrelation (wie Konfluenz und Standardisierung) ein Ausgangspunkt für die Untersuchung von Term-Ersetzungs-Systemen (Klop et al, ca. 1980)

Ich möchte durch Beispiele aus den letzten Jahren belegen, daß die Entwicklung in der Kombinatorischen Logik trotz dieser Erfolge keineswegs stagniert, sonder nach wie vor interessante Resultate und Fragen liefert.

Der Vortrag liefert Illustrationen zu den derzeit laufenden Vorlesungen Lambda-Kalkül (Prof. Herre) sowie Termgleichungen (Dr. Hartwig). Die Beispiele werden jedoch ohne Vorkenntnisse verständlich sein. Ich lade deswegen gerade jüngere Studenten besonders ein, sich hier einen Einblick in wichtige Theorie-Themen des Hauptstudiums zu verschaffen.


Literatur (Online)
http://www.informatik.uni-leipzig.de/~joe/ mailto:joe@informatik.uni-leipzig.de