Berechenbarkeitsaspekte Nichtklassischer Logik

01.12.2005 - 01.02.2008
Forschungsförderungsprojekt
Das Hauptthema dieses Projekts besteht aus zwei Arten von nichtklassischer Logik, nämlich konstruktive Logik und Wahrscheinlichkeitslogik. Konstruktive Logik geht auf den Anfang des 20. Jahrhunderts zurück und versucht die verschiedenen Formen des konstruktiven mathematischen Argumentierens zu erfassen. Man hat von Anfang an versucht diese syntaktische Behandlungsweise des Konstruktivismus mit der computationalen Mathematik zu verknüpfen, zum Beispiel durch computationale Interpretationen der Regeln und Axiomen der konstruktiven Logik. Dies aber erwies sich als sehr schwierig, und tatsächlich scheiterten alle Ansätze, bis Skvortsova 1988 bewies, dass die Ideen Kolmogorovs und Medvedevs erfolgreich angewandt werden konnten, um die erwuenschte computationale Semantik zu erhalten. Die Struktur der Medvedev Grade, die von ihr benutzt wurde, hat viele andere Anwendungen in der mathematischen Logik. Wir planen, die Beziehungen zwischen dieser Struktur und der konstruktiven Logik weiter zu erforschen. Insbesondere hoffen wir, die Beziehungen mit der Theorie der Pi-0-1 Klassen, in der kürzlich in der Berechenbarkeitstheorie grosse Fortschritte erzielt wurden, besser zu verstehen. Wahrscheinlichkeitslogik ist eine neuere und weniger kanonische Art Logik, die dennoch viele fundamentale Fragen ueber die logische und computationale Natur der Wahrscheinlichkeit aufwirft. Wir konzentrieren uns in diesem Projekt auf eine bestimmte Art der Wahrscheinlichkeitslogik, die auf Valiants beruehmtes pac-Modell basiert. Dieses Modell der Induktion ist mittlerweile das dominante Paradigma in der Komplexitätstheorie und verwandten Gebieten geworden. Wir planen, die elementare Theorie dieser Logik zu entwickeln, und werden insbesondere versuchen, die Komplexitaet der verschiedenen Entscheidbarkeitsprobleme, die mit ihr verbunden sind, festzustellen. Eng verbunden hiermit wird die gleichzeitige Entwicklung der Modell- und Beweistheorie der Wahrscheinlichkeitslogik sein, was wiederum verbunden ist mit verschiedenen Schwierigkeiten aus der Wahrscheinlichkeits- und Masstheorie.

Personen

Projektleiter_in

Institut

Förderungsmittel

  • Fonds zur Förderung der wissenschaftlichen Forschung (FWF)

Forschungsschwerpunkte

  • Information and Communication Technology

Schlagwörter

DeutschEnglisch
Konstruktive Logikconstructive logic
Wahrscheinlichkeitslogikprobability logic
Berechenbarkeitcomputability