Definierbarkeit und Berechenbarkeit

Die Theorie der Berechenbarkeit ist eine der zentralen Gebiete der mathematischen Logik, seit den fundamentalen Arbeiten in den Dreißiger Jahren von A. Turing, K. Gdel, A. Church und S. Kleene. Insbesondere wurde durch die Formalisierung des Berechenbarkeitsbegriffs gezeigt, dass viele mathematische Probleme unentscheidbar sind. Die allgemeine Theorie der Berechenbarkeit erlaubt die Klassifikation von Problemen nach ihrem "Unberechenbarkeitsgrad". Konzepte der Berechenbarkeitstheorie fanden auch Anwendungen in Algebra und Modelltheorie. Ein wichtiges Beispiel ist die Theorie der berechenbaren Modelle, in der die algorithmische Komplexität abzählbarer Modelle betrachtet wird. Deskriptive Mengenlehre behandelt Fragen der Definierbarkeit von Mengen reeller Zahlen. Die Resultate und Methoden dieser Theorie sind eng mit denen der klassischen Rekursionstheorie verwandt. Diese Verbindung wird noch gestärkt durch neuere Ergebnisse zur effektiven Theorie der Kardinalzahlen, basierend auf Wadge Reduzierbarkeit, sowie durch neue Resultate zur Definierbarkeit von Äquivalenzrelationen. Viele Ideen der deskriptiven Mengenlehre können in berechenbarer Modelltheorie angewendet werden, zB zur Klassifikation von isomorphen und bi-einbettbaren Klassen von berechenbaren Strukturen. Admissible set theory und verallgemeinerte Berechenbarkeit entstand in den Sechziger Jahren in den Arbeiten von S. Kripke, R. Platek, Y. Moschovakis, R. Montague, J. Barwise, G. Kreisel and G. Sacks. Das Hauptziel dieser Theorie ist die Untersuchung von Berechenbarkeit in Strukturen, die sich wesentlich von den natürlichen Zahlen unterscheiden: Reelle Zahlen, admissible Ordinalzahlen und beliebige admissible Mengen mit Urelementen. Admissible set theory kann als grundlegendes Werkzeug in der Untersuchung von verallgemeinerter Berechenbarkeit abstrakter Strukturen dienen. Das Projekt behandelt die Hauptfragen der erwähnten Gebiete, sowie neue Fragen die aus dem Zusammenspiel der für die jeweiligen Gebiete typischen Konzepte erwachsen. Wir werden algorithmische Eigenschaften von modelltheoretischen und mengentheoretischen Objekten untersuchen, durch einen allgemeinen Begriff der Berechenbarkeit. Unter anderem werden wir folgende Gebiete untersuchen: 1. Berechenbarkeit von Strukturen und Komplexität von Klassen berechenbarer Modelle und Äquivalenzrelationen solcher Klassen; 2. Struktur und Komplexität verschiedener natürlicher Begriffe von Reduzierbarkeit topologischer Räume; 3. Berechenbarkeit über abstrakten Strukturen.

Die mathematische Logik erreichte die Moderne mit der Arbeit von Kurt Gödel an der Universität Wien, wo er in den dreißiger Jahren des vorigen Jahrhunderts seine berühmten Sätze zur Vollständigkeit und Unvollständigkeit der Logik erster Stufe bewies. Dieses Projekt, das beim Kurt Gödel Research Center durchgeführt wurde, konzentrierte sich an die Definierbarkeit und die Berechenbarkeit, zwei zentrale Aspekte der Arbeit Gödels. Die Themen des Projekts waren: Berechenbarkeit in der Analysis, die Metamathematik der Ordinalzahl-Berechenbarkeit, definierbare Strukturen und die Komplexität von Berechnungen in der Mengenlehre.