Berechenbarkeitsaspekte Nichtklassischer Logik

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 erwünschte 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 große Fortschritte erzielt wurden, besser zu verstehen. Wahrscheinlichkeitslogik ist eine neuere und weniger kanonische Art Logik, die dennoch viele fundamentale Fragen über die logische und computationale Natur der Wahrscheinlichkeit aufwirft. Wir konzentrieren uns in diesem Projekt auf eine bestimmte Art der Wahrscheinlichkeitslogik, die auf Valiants berühmtes 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 Komplexität 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 Maßtheorie.

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 erwünschte 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 große Fortschritte erzielt wurden, besser zu verstehen. Wahrscheinlichkeitslogik ist eine neuere und weniger kanonische Art Logik, die dennoch viele fundamentale Fragen über die logische und computationale Natur der Wahrscheinlichkeit aufwirft. Wir konzentrieren uns in diesem Projekt auf eine bestimmte Art der Wahrscheinlichkeitslogik, die auf Valiants berühmtes 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 Komplexität 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 Maßtheorie.