German Title: Algorithmische Zufälligkeit

Preview

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

Abstract

We consider algorithmic randomness in the Cantor space C of the infinite binary sequences. By an algorithmic randomness concept one specifies a set of elements of C, each of which is assigned the property of being random. Miscellaneous notions from computability theory are used in the definitions of randomness concepts that are essentially rooted in the following three intuitive randomness requirements: the initial segments of a random sequence should be effectively incompressible, no random sequence should be an element of an effective measure null set containing sequences with an “exceptional property”, and finally, considering betting games, in which the bits of a sequence are guessed successively, there should be no effective betting strategy that helps a player win an unbounded amount of capital on a random sequence. For various formalizations of these requirements one uses versions of Kolmogorov complexity, of tests, and of martingales, respectively. In case any of these notions is used in the definition of a randomness concept, one may ask in general for fundamental equivalent definitions in terms of the respective other two notions. This was a long-standing open question w.r.t. computable randomness, a central concept that had been introduced by Schnorr via martingales. In this thesis, we introduce bounded tests that we use to give a characterization of computable randomness in terms of tests. Our result was obtained independently of the prior test characterization of computable randomness due to Downey, Griffiths, and LaForte, who defined graded tests for their result. Based on bounded tests, we define bounded machines which give rise to a version of Kolmogorov complexity that we use to prove another characterization of computable randomness. This result, as in analog situations, allows for the introduction of interesting lowness and triviality properties that are, roughly speaking, “anti-randomness” properties. We define and study the notions lowness for bounded machines and bounded triviality. Using a theorem due to Nies, it can be shown that only the computable sequences are low for bounded machines. Further we show some interesting properties of bounded machines, and we demonstrate that every boundedly trivial sequence is K-trivial. Furthermore we define lowness for computable machines, a lowness notion in the setting of Schnorr randomness. We prove that a sequence is low for computable machines if and only if it is computably traceable. Gacs and independently Kucera proved a central theorem which states that every sequence is effectively decodable from a suitable Martin-Löf random sequence. We present a somewhat easier proof of this theorem, where we construct a sequence with the required property by diagonalizing against appropriate martingales. By a variant of that construction we prove that there exists a computably random sequence that is weak truth-table autoreducible. Further, we show that a sequence is computably enumerable self-reducible if and only if its associated real is computably enumerable. Finally we investigate interrelations between the Lebesgue measure and effective measures on C. We prove the following extension of a result due to Book, Lutz, and Wagner: A union of Pi-0-1 classes that is closed under finite variations has Lebesgue measure zero if and only if it contains no Kurtz random real. However we demonstrate that even a Sigma-0-2 class with Lebesgue measure zero need not be a Kurtz null class. Turning to Almost classes, we show among other things that every Almost class with respect to a bounded reducibility has computable packing dimension zero.

Translation of abstract (German)

Wir betrachten algorithmische Zufälligkeit im Cantorraum C der unendlichen Binärfolgen. Durch ein algorithmisches Zufälligkeitskonzept wird eine Menge von Elementen von C bestimmt, denen jeweils die Eigenschaft zugeordnet wird, zufällig zu sein. Solche Konzepte werden unter Verwendung von verschiedenen berechenbarkeitstheoretischen Begriffen definiert und gehen im Wesentlichen auf die folgenden drei intuitiven Anforderungen an zufällige Folgen zurück: Die Anfangsstücke einer zufälligen Folge sollen effektiv inkomprimierbar sein, keine zufällige Folge soll in einer effektiven Nullmenge von Folgen mit einer "Ausnahmeeigenschaft" enthalten sein, und schließlich soll für ein Wettspiel, in welchem die Bits einer Folge nacheinander geraten werden, bei einer zufälligen Folge keine effektive Strategie dem Spieler unbeschränkt viel Kapital verschaffen. Für verschiedene Formalisierungen dieser Anforderungen werden jeweils Versionen von Kolmogorov-Komplexität, Tests und Martingalen verwendet. Wird einer dieser drei Begriffe in der Definition eines Zufälligkeitskonzepts benutzt, so stellt sich generell die Frage nach grundlegenden äquivalenten Definitionen, in denen die jeweils anderen beiden Begriffe verwendet werden. Diese Frage blieb für das zentrale Konzept der berechenbaren Zufälligkeit, welches von Schnorr unter Verwendung von Martingalen eingeführt worden war, lange unbeantwortet. Wir geben in dieser Arbeit eine Charakterisierung der berechenbaren Zufälligkeit unter Verwendung von Tests an, wobei wir die von uns eingeführten beschränkten Tests benutzen. Unser Ergebnis wurde unabhängig von der zuvor von Downey, Griffiths und LaForte angegebenen Testcharakterisierung der berechenbaren Zufälligkeit durch die von ihnen eingeführten abgestuften Tests erzielt. Gestützt auf beschränkte Tests definieren wir beschränkte Maschinen und mit diesen eine Version der Kolmogorov-Komplexität, mit deren Hilfe wir eine weitere Charakterisierung der berechenbaren Zufälligkeit beweisen. Auf Grund dieses Ergebnisses ist es möglich, wie in analogen Fällen interessante Lowness- und Trivialitätseigenschaften einzuführen, die grob gesagt "Anti-Zufälligkeitseigenschaften" sind. Wir definieren und untersuchen die Begriffe Lowness für beschränkte Maschinen und beschränkte Trivialität. Mit Hilfe eines Satzes von Nies lässt sich zeigen, dass nur die berechenbaren Folgen low für beschränkte Maschinen sind. Ferner zeigen wir neben interessanten Eigenschaften der beschränkten Maschinen, dass die beschränkt trivialen Folgen K-trivial sind. Des Weiteren definieren wir Lowness für berechenbare Maschinen, einen Lowness-Begriff im Kontext der Schnorr-Zufälligkeit. Wir beweisen, dass eine Folge genau dann low für berechenbare Maschinen ist, wenn sie computably traceable ist. Nach einem zentralen Satz, den Gacs und Kucera unabhängig voneinander bewiesen haben, ist jede Folge effektiv aus einer geeigneten Martin-Löf zufälligen Folge dekodierbar. Wir geben einen etwas einfacheren Beweis dieses Satzes an, wobei wir eine zufällige Folge mit der geforderten Eigenschaft dadurch konstruieren, dass wir gegen geeignete Martingale diagonalisieren. Mit Hilfe einer Variante jener Konstruktion beweisen wir, dass eine berechenbar zufällige Folge existiert, die schwach truth-table autoreduzierbar ist. Ferner zeigen wir, dass eine Folge genau dann aufzählbar selbstreduzierbar ist, wenn die entsprechende reelle Zahl aufzählbar ist. Schließlich untersuchen wir Zusammenhänge zwischen dem Lebesguemaß und effektiven Maßen auf C. Wir beweisen die folgende Erweiterung eines Ergebnisses von Book, Lutz und Wagner: Eine gegen endliche Varianten abgeschlossene Vereinigung von Pi-0-1 Klassen hat genau dann Lebesguemaß null, wenn sie keine Kurtz-zufällige Folge enthält. Wir zeigen jedoch, dass sogar eine Sigma-0-2 Klasse mit Lebesguemaß null keine Kurtz-Nullklasse zu sein braucht. Anschließend wenden wir uns Almost-Klassen zu und beweisen unter anderem, dass bezüglich einer beschränkten Reduzierbarkeit jede Almost-Klasse berechenbare Packing Dimension null hat.