Titelaufnahme

Titel
Berechenbare Transformationen von Strukturklassen / von Dino Rossegger
Weitere Titel
Computable Transformations of Classes of Structures
VerfasserRossegger, Dino
Begutachter / BegutachterinFokina, Ekaterina
ErschienenWien, 2015
UmfangV, 47 Seiten : Diagramme
HochschulschriftTechnische Universität Wien, Diplomarbeit, 2015
Anmerkung
Text in englischer Sprache
Anmerkung
Zusammenfassung in deutscher Sprache
Parallelt. [Übers. des Autors]: Computable Transformations of Classes of Structures
SpracheEnglisch
DokumenttypDiplomarbeit
Schlagwörter (DE)Berechenbarkeitstheorie / berechenbare Strukturen / berechenbare Transformationen
Schlagwörter (EN)Computability theory / computable structures / effective transformations
URNurn:nbn:at:at-ubtuw:1-82229 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Berechenbare Transformationen von Strukturklassen [0.59 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

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.

Zusammenfassung (Englisch)

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.