Berechenbare Transformationen von Strukturklassen

Abstract

Die Arbeit befasst sich mit berechenbaren Transformationen von Strukturklassen. Wir geben einen Überblick über die vorhandenen berechenbaren Transformationen und deren Relationen. Der Fokus liegt hier auf effektiver Bi-Interpretierbarkeit. Wir zeigen, dass die Klassen der Graphen und partiellen Ordnungen bi-interpretierbar sind und befassen uns mit einem neuen Resultat über die Äquivalenz der effektiven Bi-Interpretierbarkeit von Klassen und berechenbaren Funktoren. Weiters untersuchen wir zwei kürzlich erforschte berechenbarkeitstheoretische Eigenschaften von Strukturen, Theorie spektra und - n - spectra im Kontext der effektiven Bi-Interpretierbarkeit. Wir zeigen, dass jedes mögliche - 1 - und - 2 -Spektrum in den Klassen der partiellen Ordnungen und Graphen existiert.

The work reviews different notions of computable transformations on elementary classes of structures. We review the most prominent computable transformations, effective reducibility, computable embeddings, Turing computable embeddings, effective bi-interpretability and computable functors, discussing the different ideas behind them and their relations. Recent results on the equivalence of effective bi-interpretability and computable functors are discussed in detail and we prove that graphs and partial orders are effectively bi-interpretable and therefore share many computability theoretic properties such as degree spectra and computable dimension. At last the two recently examined notions of theory spectra and - n -spectra and their relation in context of computable transformations are examined. We show that any existing - 1 - and - 2 -spectrum can be found in the classes of graphs and partial orders.