Bitte warten...
Bitte warten...
English
Hilfe
Login
Forschungsportal
Suche
Forschungsprofile
Forschungsprojekte
Projektvollmacht
Lehre
Forschung
Organisation
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
Sebastiaan Terwijn
(E104)
Institut
E104 - Institut für Diskrete Mathematik und Geometrie
Förderungmittel
FWF - Österr. Wissenschaftsfonds (National)
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
Forschungsschwerpunkte
Computational Intelligence: 100%
Schlagwörter
Deutsch
Englisch
Konstruktive Logik
constructive logic
Wahrscheinlichkeitslogik
probability logic
Berechenbarkeit
computability
Publikationen
Publikationsliste