German Title: Kolmogorovkomplexität

Preview

PDF, English Download (627kB) | Terms of use

Abstract

In dieser Dissertation werden neue Ergebnisse über Kolmogorovkomplexität diskutiert. Ihr erster Teil konzentriert sich auf das Studium von Kolmogorovkomplexität ohne Zeitschranken. Hier beschäftigen wir uns mit dem Konzept nicht-monotoner Zufälligkeit, d.h. Zufälligkeit, die von Martingalen charakterisiert wird, die in nicht-monotoner Reihenfolge wetten dürfen. Wir werden in diesem Zusammenhang eine Reihe von Zufälligkeitsklassen einführen, und diese dann von einander separieren. Wir präsentieren auß erdem einen systematischen überblick über verschiedene Traceability-Begriffe und charakterisieren diese durch (Auto-)Komplexitätsbegriffe. Traceabilities sind eine Gruppe von Begriffen, die ausdrücken, dass eine Menge beinahe berechenbar ist. Der zweite Teil dieses Dokuments beschäftigt sich mit dem Thema zeitbeschränkter Kolmogorovkomplexität. Zunächst untersuchen wir den Unterschied zwischen zwei Arten, ein Wort zu beschreiben: Die Komplexität, es genau genug zu beschreiben, damit es von anderen Wörter unterschieden werden kann; sowie die Komplexität, es genau genug zu beschreiben, damit das Wort aus der Beschreibung tatsächlich generiert werden kann. Diese Unterscheidung ist im Falle zeitunbeschränkter Kolmogorovkomplexität nicht von Bedeutung; sobald wir jedoch Zeitschranken einführen, wird sie essentiell. Als nächstes führen wir den Begriff der Tiefe ein und beweisen ein ihn betreffendes Dichotomieresultat, das in seiner Struktur an Kummers bekanntes Gap-Theorem erinnert. Zu guter Letzt betrachten wir den wichtigen Begriff der Solovayfunktionen. Hierbei handelt es sich um berechenbare obere Schranken der Kolmogorovkomplexität, die unendlich oft scharf sind. Wir benutzen sie, um in einem gewissen Zusammenhang Martin-Löf-Zufälligkeit zu charakterisieren, und um eine Charakterisierung von Jump-Traceability anzugeben.

Translation of abstract (English)

This dissertation discusses new results on Kolmogorov complexity. Its first part focuses on the study of Kolmogorov complexity without time bounds. Here we deal with the concept of non-monotonic randomness, that is randomness characterized by martingales that bet non-monotonically. We will state the definitions of several different randomness classes and then separate them from each other. We also present a a systematic survey of a wide array of traceability notions and characterize them through (auto)complexity notions. Traceabilities are a group of notions that express that a set is not far away from being computable. The second part of the document deals with the topic of time bounded Kolmogorov complexity. First we investigate the difference between two ways of describing a word: the complexity of describing it well enough so that it can be distinguished from other words; and the complexity of describing it well enough so that the word can actually be produced from the description. While this difference is unimportant in the case of Kolmogorov complexity without time bounds it plays an essential role when time bounds are present. Next, we introduce the notion of computational depth and prove a dichotomy result about it that is reminiscent of Kummer's well-known gap theorem. Lastly, we look at the important notion of Solovay functions. Solovay functions are computable upper bounds of Kolmogorov complexity that are actually sharp infinitely often. We will use them, first, to characterize Martin-Loef randomness in a certain way and, second, to give a characterization of being jump-traceable.