Eine neue Turinggradklasse aus der Strukturtheorie

Wenn zwei Objekte unterschiedlich aussehen, aber eigentlich gleich sind wie kann ein Computer das erkennen? Betrachten wir die Aufgabe, eine Karte des österreichischen Eisenbahnnetzes zu zeichnen. Person A skizziert das Netz von Westen nach Osten, während Person B im Osten beginnt und im Westen endet. Beide Skizzen zeigen dieselben Informationen, präsentieren sie aber unterschiedlich. Würde man Bs Karte umdrehen, erhielte man As Karte. Eine Mathematiker:in würde sagen, dass die Karten isomorph sind. Für endliche Strukturen wie unsere Karten kann man Algorithmen entwerfen, die feststellen, ob zwei Strukturen isomorph sind. Es gibt nur endlich viele Isomorphismen also Abbildungen, die bezeugen, dass die Strukturen isomorph sind und daher findet ein einfacher guess-and-check Algorithmus den Isomorphismus oder läuft erfolglos durch alle Möglichkeiten. Für unendliche Strukturen, wie sie in der Mathematik üblicherweise vorkommen, existieren jedoch allgemein keine Algorithmen die Isomorphismen berechnen. Sind zwei unendliche Strukturen isomorph, so stellt sich die Frage: Wie kompliziert sind die Isomorphismen zwischen ihnen? Vereinfacht gesagt: Je einfacher die Isomorphismen, desto ähnlicher erscheinen die Strukturen aus der Sicht eines Computers. Die rechnerische Komplexität solcher Isomorphismen wird mithilfe von Turing-Graden gemessen. Zentral für diese Fragestellung ist das degree of categoricity einer berechenbaren Struktur A. Es ist der kleinste Turing-Grad, mit dem man Isomorphismen zwischen allen berechenbaren Strukturen berechnen kann, die zu A isomorph sind. Ein wichtiges offenes Problem besteht darin, genau zu verstehen, welche Turing- Grade auftreten können. Lassen sie sich mit Hilfe anderer, besser verstandenen Klassen von Turing- Graden klassifizieren? Kürzlich konnten wir zeigen, dass eine Unterklasse der degrees of categoricity denselben Turing- Grad wie sogenannte treeable functions besitzt die sogenannten treeable degrees. Dies liefert eine neue und überraschend einfache partielle kombinatorische Klassifizierung. Dieses Ergebnis gibt Anlass zur Hoffnung, eine komplette Klassifizierung der degrees of categoricity durch treeable degrees zu finden. Doch gegenwärtig wäre diese nur begrenzt hilfreich, da treeable degrees selbst noch kaum verstanden sind. Ziel dieses Projekts ist es, ein besseres Verständnis dieser Grade zu erlangen, indem ihre Beziehungen zu anderen Gradklassen untersucht werden. Dadurch wollen wir klären, ob sie tatsächlich eine vollständige Charakterisierung der degrees of categoricity liefern können. Auf diese Weise beleuchtet das Projekt den algorithmischen Gehalt der Isomorphiebeziehung einer der zentralsten Äquivalenzrelationen der gesamten Mathematik.