Zufällige Binärfolgen und zufällige reelle Zahlen.^{∗}

Frank Rosemeier

Meinem Doktorvater Prof. Dr. H. P. Petersson zu seinem 65. Geburtstag in Dankbarkeit gewidmet.

Abstract. This is a self-contained survey of a randomness theory for binary sequences and for real numbers, which is intended to be a first step to provide a formalization in (e. g. Bishop style) constructive mathematics. The notions of left-computable real number, Ω-number and Ω-like number are defined. For 0 < α < 1 we prove the following (well known) result:

α is random and left-computable ⟺ α is an Ω-number
⟺ α is Ω-like.

Einleitung

In diesem Beitrag befassen wir uns mit der Frage, wann eine unendliche Binärfolge zufällig ist. Zunächst scheint anschaulich klar zu sein:

10110010111011000111 … ist wohl zufällig,

10101010101010101010 … dagegen nicht.

Dass diese Unterscheidung noch nicht genau genug ist, zeigen Zweifelsfälle wie 10110101000001001111 …; hier könnte es sich um die Nachkommastellen der Binärdarstellung von \sqrt{2}/2 handeln.

∗Diese Ausarbeitung basiert auf Vorträgen, die ich im Sommersemester 2001 an der FernUniversität Hagen gehalten habe. Ich danke den Betreuern des Seminars ”Der algorithmische Zufallsbegriff“, Prof. Dr. Klaus Weihrauch und Dr. Peter Hertling, sowie den Teilnehmerinnen und Teilnehmern des Oberseminars Algebra/Topologie für ihre Unterstützung und ihr Interesse. Ferner bedanke ich mich bei Petra Dittmer für die Hilfe beim Setzen des Manuskriptes in L^{A}TEX, bei Manfred Schulte für Hinweise zum Erzeugen von Hyperlinks, bei Reinhard Börger für einige anregende Fragen und Anmerkungen, sowie schließlich bei meiner Schwiegermutter Thea Rosemeier für ihre Gastfreundschaft beim Korrigieren dieses Artikels.

Wir werden den Begriff der zufälligen unendlichen Binärfolge auf mehrere äquivalente Weisen präzise definieren (Martin-Löf-, Solovay- und Chaitin-Zufälligkeit). Eine reelle Zahl wird als zufällig bezeichnet, wenn sie eine Binärdarstellung besitzt, deren Nachkommastellen eine zufällige Binärfolge bilden. Da zufällige reelle Zahlen nicht berechenbar sein können (eine Berechnungsvorschrift würde die Konstruktion eines Martin-Löf-Zufallstests erlauben, der zeigt, dass die Zahl nicht zufällig ist), werden wir uns anschließend mit zufälligen reellen Zahlen befassen, die der schwächeren Bedingung der Linksberechenbarkeit genügen. Durch die Charakterisierung der linksberechenbaren reellen Zahlen als Ω-Zahlen nach Chaitin erhalten wir die Möglichkeit tatsächlich zufällige reelle Zahlen anzugeben.

Nach Einführung der Grundbegriffe (nämlich Binärwörter und Binärfolgen in Abschnitt 1, Zufälligkeit von Binärfolgen in Abschnitt 2, präfix-freie Mengen von Binärwörtern in Abschnitt 3, und Chaitin-Zufälligkeit in Abschnitt 4) wenden wir uns in Abschnitt 5 dem Begriff der Linksberechenbarkeit zu. Anschließend werden in Abschnitt 6 die Ω-Zahlen nach Chaitin sowie die Ω-ähnlichen Zahlen nach Solovay vorgestellt. Schließlich folgt in Abschnitt 7 der Nachweis, dass sich die linksberechenbaren zufälligen Zahlen einerseits als Ω-Zahlen und andererseits als Ω-ähnliche Zahlen kennzeichnen lassen.

1 Binärwörter und Binärfolgen

1.1 Notation

Sei Σ := {0, 1} das Binäralphabet. Dann bezeichne Σ^{∗} die Menge aller Binärwörter (endlicher Zeichenketten über Σ). Für w = w_{0} ⋯ w_{ℓ−1} ∈ Σ^{∗} (ℓ ∈ ℕ_{0} := {0, 1, 2, …}) sei l_{2}(w) := ℓ die Länge von w; weiter sei ⟨w⟩_{2}, der Wert von w, die rationale Zahl mit Binärdarstellung 0,w_{0} ⋯ w_{ℓ−1} , wir

setzen also ⟨w⟩_{2} := ∑_{k=0}^{ℓ−1} w_{k}2^{−(k+1)}. Das leere Wort ϵ hat die Länge l_{2}(ϵ) = 0

und den Wert ⟨ϵ⟩_{2} = 0.

Mit Σ^{ω} werde die Menge aller (unendlichen) Binärfolgen bezeichnet. Für s = (s_{0}, s_{1}, s_{2}, …) ∈ Σ^{ω} und n ≧ 0 sei s_{0:n} := s_{0} ⋯ s_{n} das Anfangsstück

der Länge n + 1 von s; wir setzen ⟨s⟩_{2} := ∑_{k=0}^{∞} s_{k}2^{−(k+1)}, so dass ⟨s⟩_{2} ∈ [0, 1],

der Wert von s, die reelle Zahl mit Binärdarstellung 0,s_{0}s_{1}s_{2} ⋯ ist.

Für die beiden konstanten Binärfolgen schreiben wir 0^{ω} := (0, 0, 0, …) und 1^{ω} := (1, 1, 1, …).

1.2 Bemerkungen

(1) Mit der Komposition (v_{0} ⋯ v_{m})(w_{0} ⋯ w_{n}) := v_{0} ⋯ v_{m}w_{0} ⋯ w_{n} und dem leeren Wort ϵ als neutralem Element ist die Menge Σ^{∗} ein Monoid: Für alle v, w, x ∈ Σ^{∗} gilt (i) (vw)x = v(wx), (ii) ϵw = w = wϵ.

(2) Durch (w_{0} ⋯ w_{n})(s_{0}, s_{1}, s_{2}, …) := (w_{0}, …, w_{n}, s_{0}, s_{1}, s_{2}, …) wird eine Operation von Σ^{∗} auf Σ^{ω} erklärt: Für alle v, w ∈ Σ^{∗} und alle s ∈ Σ^{ω} gilt

(i) (vw)s = v(ws), (ii) ϵs = s.

(3) Für alle w ∈ Σ^{∗}, s ∈ Σ^{ω}, n ≧ 0 gilt (ws)_{0:n} = w, falls l_{2}(w) = n + 1. Außerdem gilt ⟨s⟩_{2} = lim_{n→∞}⟨s_{0:n}⟩_{2}, und mit ι_{0} : Σ^{∗} → Σ^{ω}, w ↦ w0^{ω} haben wir ⟨ι_{0}(w)⟩_{2} = ⟨w⟩_{2}.

1.3 Notiz (Vgl. [1] Lemma 2.11) Die (bijektive) berechenbare Funktion σ_{2} : Σ^{∗} → ℕ_{0} mit σ_{2}(ϵ) := 0 und σ_{2}(w_{0}w_{1} ⋯ w_{n−1}w_{n}) := 2^{n}(w_{0}+1)+2^{n−1}(w_{1}+1)+…+2(w_{n−1}+1)+(w_{n}+1) induziert die durch

v ≤_{llex} w :⟺ σ_{2}(v) ≦ σ_{2}(w).

definierte längen-lexikographische Ordnung auf Σ^{∗}. Wir haben also v ≤_{llex} w, wenn l_{2}(v) < l_{2}(w) gilt, oder wenn l_{2}(v) = l_{2}(w) gilt und v im Lexikon vor w stünde (vorausgesetzt 0 steht vor 1): ϵ ≤_{llex} 0 ≤_{llex} 1 ≤_{llex} 00 ≤_{llex} 01 ≤_{llex} 10 ≤_{llex} 11 ≤_{llex} 000 ≤_{llex} 001 ≤_{llex} 010 ≤_{llex} 011 ≤_{llex} · · · .

1.4 Bezeichnungen Die Menge Σ^{ω} wird auch als Cantor-Raum bezeichnet. Sie lässt sich als cartesisches Produkt ∏_{i=0}^{∞} {0, 1} abzählbar unendlich vieler Kopien des Binäralphabetes Σ = {0, 1} auffassen.

(1) Versieht man Σ = {0, 1} mit der diskreten Topologie {∅, {0} , {1} , Σ}, so bilden die Mengen wΣ^{ω} := { ws |s ∈ Σ^{ω} } eine Basis der Produkttopologie auf Σ^{ω}. Für jede Teilmenge A ⊂ Σ^{∗} können wir daher folgende offene Teilmenge von Σ^{ω} definieren

AΣ^{ω} := { ws |w ∈ A, s ∈ Σ^{ω} }.

(2) Das vom Maß λ auf Σ = \{0, 1\} mit λ(\{0\}) = λ(\{1\}) = \frac{1}{2} induzierte Produktmaß μ auf Σ^{ω} hat die Eigenschaft

μ(wΣ^{ω}) = 2^{−l_{2}(w)} für alle w ∈ Σ^{∗}.

1.5 Hinweis (vgl. [1] 5.1–5.3) Als topologischer Raum ist Σ^{ω} separabel, metrisierbar und kompakt; Σ^{ω} ist die Vervollständigung von Σ^{∗}. (Die abzählbare Teilmenge ι_{0}[Σ^{∗}] = { w0^{ω} |w ∈ Σ^{∗} } ⊂ Σ^{ω} liegt dicht, und

d(s, s′) := \{ \begin{matrix}2^{− min\{ i≧0| s_{i}≠s′_{i} \}} & für s ≠ s′ \\ 0 & für s = s′ \end{matrix} (s, s′ ∈ Σ^{ω})

definiert eine Metrik auf Σ^{ω}.)

2 Zufällige Binärfolgen

2.1 Definition (Hertling [8] Definition 1) Sei ( V_{n} |n ≧ 1 ) eine Familie von (offenen) Teilmengen V_{n} ⊂ Σ^{ω}. Dann wird ( V_{n} |n ≧ 1 ) als gleichmäßig rekursiv aufzählbar bezeichnet, wenn es eine rekursiv aufzählbare Teilmenge A ⊂ ℕ × Σ^{∗} gibt mit

V_{n} = A_{n}Σ^{ω} für alle n ≧ 1,

wobei A_{n} := { w ∈ Σ^{∗} |(n, w) ∈ A }.

2.2 Definition (Martin-Löf [10])

(1) Eine gleichmäßig rekursiv aufzählbare Familie ( V_{n} |n ≧ 1 ) von offenen Teilmengen V_{n} ⊂ Σ^{ω} heißt Martin-Löf-Test, wenn

μ(V_{n}) ≤ 2^{−n} für alle n ≧ 1.

(2) Wir sagen, dass eine Binärfolge s ∈ Σ^{ω} den Martin-Löf-Test ( V_{n} |n ≧ 1 ) besteht, wenn es ein n ≧ 1 gibt mit s ∉ V_{n}.

(3) Eine Binärfolge s ∈ Σ^{ω} wird Martin-Löf-zufällig genannt, wenn sie jeden Martin-Löf-Test besteht.

2.3 Bemerkungen

(1) Für jedes Binärwort w = w_{0} ⋯ w_{n} ∈ Σ^{∗} ist die Binärfolge

w^{ω} := (w_{0}, …, w_{n}, w_{0}, …, w_{n}, …) nicht Martin-Löf-zufällig.

(2) Allgemeiner können berechenbare Binärfolgen nicht Martin-Löf-zufällig sein, denn aus jeder Berechnungsvorschrift läßt sich ein Martin-Löf-Test konstruieren, den die Folge nicht besteht.

2.4 Definition (Solovay [12])

(1) Eine gleichmäßig rekursiv aufzählbare Familie ( W_{n} |n ≧ 1 ) von offenen

Teilmengen W_{n} ⊂ Σ^{ω} heißt Solovay-Test, wenn die Reihe ∑_{n=1}^{∞} μ(W_{n})

konvergiert.

(2) Wir sagen, dass eine Binärfolge s ∈ Σ^{ω} den Solovay-Test ( W_{n} |n ≧ 1 ) besteht, wenn es ein n_{0} ≧ 1 gibt mit s ∉ W_{n} für alle n ≧ n_{0}.

(3) Eine Binärfolge s ∈ Σ^{ω} wird Solovay-zufällig genannt, wenn sie jeden Solovay-Test besteht.

2.5 Lemma (Hertling [8] Lemma 20)

Sei ( X_{n} |n ≧ 1 ) eine Familie von μ-messbaren Teilmengen X_{n} ⊂ Σ^{ω}, für

die ∑_{n=1}^{∞} μ(X_{n}) konvergiert. Ferner sei m ≧ 0 eine natürliche Zahl und es

sei Y ⊂ Σ^{ω} eine μ-messbare Teilmenge mit der Eigenschaft, dass es für jedes s ∈ Y mindestens m verschiedene Zahlen n ≧ 1 mit s ∈ X_{n} gibt.

Dann gilt m · μ(Y) ≤ ∑_{n=1}^{∞} μ(X_{n}).

Beweis:

Vollständige Induktion nach m:

Für m = 0 ist nichts zu zeigen.

m − 1 → m: Definiere eine Familie ( Z_{n} |n ≧ 1 ) von μ-messbaren Teilmengen Z_{n} ⊆ Y durch

Z_{n} := X_{n} ∩ Y \ ⋃_{k=0}^{n−1} Z_{k} für alle n ≧ 1.

Dann gibt es für jedes s ∈ Y genau ein n ≧ 1 mit s ∈ Z_{n}, daher gilt

μ(Y) = ∑_{n=1}^{∞} μ(Z_{n}). Außerdem haben die μ-messbaren Teilmengen X_{n} \Z_{n} die

Eigenschaft, dass es für jedes s ∈ Y mindestens m − 1 verschiedene Zahlen n ≧ 1 mit s ∈ X_{n} \ Z_{n} gibt. Die Induktionsannahme liefert nun

(m − 1) · μ(Y) ≤ ∑_{n=1}^{∞} μ(X_{n} \ Z_{n}),

woraus sich wegen μ(X_{n}\Z_{n})+μ(Z_{n}) = μ(X_{n}) für alle n ≧ 1 die Behauptung ergibt. □

2.6 Satz (cf. Solovay [12])

Eine Binärfolge s ∈ Σ^{ω} ist genau dann Martin-Löf-zufällig, wenn sie Solovayzufällig ist.

Beweis:

Da jeder Martin-Löf-Test auch ein Solovay-Test ist, ist jede Solovay-zufällige Binärfolge auch Martin-Löf-zufällig.

Sei s ∈ Σ^{ω} eine Martin-Löf-zufällige Binärfolge und sei ( W_{n} |n ≧ 1 ) ein Solovay-Test. Wir haben zu zeigen, dass es ein n_{0} ≧ 1 gibt mit s ∉ W_{n} für alle n ≧ n_{0}.

Sei dazu A ⊂ ℕ × Σ^{∗} eine rekursiv aufzählbare Teilmenge mit W_{n} = A_{n}Σ^{ω}, A_{n} := { w ∈ Σ^{∗} |(n, w) ∈ A } für alle n ≧ 1.

Wähle eine natürliche Zahl m ∈ ℕ mit ∑_{n=1}^{∞} μ(W_{n}) < 2^{m}.

Nun definieren wir eine rekursiv aufzählbare Teilmenge B ⊂ ℕ × Σ^{∗} durch

B_{n} := ⋃_{1≦k_{1}<···<k_{2^{m+n}}} ⋂_{i=1}^{2^{m+n}} A_{k_{i}}Σ^{∗} für alle n ≧ 1

und B := ⋃_{n=1}^{∞}({n} × B_{n}). Nach Lemma 2.5 gilt

2^{m+k} · μ(B_{k}Σ^{ω}) ≤ ∑_{n=1}^{∞} μ(W_{n}) < 2^{m} für jedes k ≧ 1,

also μ(B_{k}Σ^{ω}) < 2^{−k}.

Durch V_{n} := B_{n}Σ^{ω} für alle n ≧ 1 wird somit ein Martin-Löf-Test ( V_{n} |n ≧ 1 ) definiert. Weil s Martin-Löf-zufällig ist, gibt es ein n ≧ 1 mit s ∉ V_{n}, also s ∉ B_{n}Σ^{ω}. Aufgrund der Definition von B_{n} ist s in höchstens 2^{m+n} − 1 verschiedenen der Mengen A_{k}Σ^{ω} = W_{k} enthalten, das heißt es gibt ein n_{0} ≧ 1 mit s ∉ W_{n} für alle n ≧ n_{0}. □

2.7 Vereinbarung

Als zufällig wollen wir Binärfolgen bezeichnen, die Martin-Löf-zufällig sind (und damit nach Satz 2.6 auch Solovay-zufällig).

2.8 Hinweis

Beispiele für zufällige Binärfolgen lassen sich nicht ohne weiteres angeben. Die in 6.1 definierten Ω-Zahlen werden sich in Satz 7.3 als zufällig erweisen.

3 Präfix-freie Mengen

3.1 Beobachtung

Es gibt eine berechenbare Funktion h : Σ^{∗} × Σ^{∗} → ℕ_{0} mit der Eigenschaft, dass für alle v, w ∈ Σ^{∗} gilt

(0) h(v, w) = 0 ⟺ vΣ^{ω} ∩ wΣ^{ω} = ∅ (keine Anfangsstücke voneinander),
(1) h(v, w) = 1 ⟺ vΣ^{ω} ⊊ wΣ^{ω}  (w ist echtes Anfangsstück von v),
(2) h(v, w) = 2 ⟺ wΣ^{ω} ⊊ vΣ^{ω}  (v ist echtes Anfangsstück von w),
(3) h(v, w) = 3 ⟺ vΣ^{ω} = wΣ^{ω}  (v ist gleich w).

(Stelle fest, ob eine Stelle 0 ≦ i ≦ min(l_{2}(v), l_{2}(w)) existiert, an der sich v von w unterscheidet; wenn ja, setze h(v, w) := 0, anderenfalls setze h(v, w) := 1, falls l_{2}(v) > l_{2}(w) gilt, h(v, w) := 2, falls l_{2}(v) < l_{2}(w) gilt, und h(v, w) := 3, falls l_{2}(v) = l_{2}(w) gilt.)

3.2 Definition

(1) Ein Binärwort w ∈ Σ^{∗} wird als Präfix des Binärwortes v ∈ Σ^{∗} bezeichnet, wenn vΣ^{ω} ⊆ wΣ^{ω} gilt.

(2) Zwei Binärwörter v, w ∈ Σ^{∗} mögen präfix-fremd heißen, wenn vΣ^{ω} und wΣ^{ω} disjunkt sind.

(3) Eine Teilmenge A ⊂ Σ^{∗} wird präfix-frei genannt, wenn zwei verschiedene Elemente von A stets präfix-fremd sind.

(4) Eine Folge von Binärwörtern (w_{i})_{i≧0} heißt präfix-frei, wenn die Teilmenge { w_{i} |i ≧ 0 } ⊂ Σ^{∗} präfix-frei ist.

3.3 Lemma ([8] Lemma 10)

Für jede präfix-freie Teilmenge A ⊂ Σ^{∗} gilt die Kraft-Ungleichung

∑_{w∈A} 2^{−l_{2}(w)} = μ(AΣ^{ω}) ≤ 1.

Beweis: Für verschiedene Elemente v, w ∈ A sind vΣ^{ω} und wΣ^{ω} disjunkt. Daher gilt

∑_{w∈A} 2^{−l_{2}(w)} = ∑_{w∈A} μ(wΣ^{ω}) = μ( ⋃_{w∈A} wΣ^{ω}) = μ(AΣ^{ω})

mit μ(AΣ^{ω}) ≤ μ(Σ^{ω}) = 1. □

3.4 Bezeichnung Für jede präfix-freie Teilmenge A ⊂ Σ^{∗} setzen wir

2^{−A} := ∑_{w∈A} 2^{−l_{2}(w)}.

3.5 Bemerkung Zu jeder endlichen Teilmenge E ⊂ Σ^{∗} lassen sich paarweise präfix-fremde Binärwörter w_{1}, …, w_{n} ∈ E berechnen mit

EΣ^{ω} = ⋃_{i=1}^{n} w_{i}Σ^{ω};

dabei gilt E = {w_{1}, …, w_{n}}, falls E präfix-frei ist.

(Setze S_{0} := ∅, w_{i} := min_{llex} { w ∈ E \ {w_{1}, …, w_{i−1}} |wΣ^{ω} ∩ S_{i−1}Σ^{ω} = ∅ } und

S_{i} := S_{i−1} ∪ {w_{i}} für alle i ≧ 1.)

3.6 Satz (Effektives Kraft-Chaitin-Theorem, [8] Theorem 11) Sei (n_{k})_{k≧0} eine berechenbare Folge natürlicher Zahlen, für die ∑_{k=0}^{∞} 2^{−n_{k}} kon-

vergiert mit ∑_{k=0}^{∞} 2^{−n_{k}} ≤ 1.

Dann gibt es eine präfix-freie, berechenbare Folge von Binärwörtern (w_{k})_{k≧0} mit l_{2}(w_{k}) = n_{k} für alle k ≧ 0.

Beweis:

Konstruiert wird eine berechenbare Folge von Binärwörtern (w_{k})_{k≧0} mit den folgenden beiden Eigenschaften (m ≧ 0):

(A_{m}) l_{2}(w_{k}) = n_{k} für alle 0 ≦ k < m.

(B_{m}) Sei I_{m} ⊂ ℕ_{0} die eindeutige endliche Menge mit ∑_{i∈I_{m}} 2^{−i} = 1− ∑_{k=0}^{m−1} 2^{−n_{k}}.

Es gibt v_{i}^{(m)} ∈ Σ^{∗} mit l_{2}(v_{i}^{(m)}) = i für alle i ∈ I_{m}, derart dass die Menge {w_{0}, …, w_{m−1}} ∪ { v_{i}^{(m)} |i ∈ I_{m} } präfix-frei ist.

Vollständige Induktion nach m:

m = 0: Trivialerweise ist (A_{0}) erfüllt. Es gilt I_{0} = {0}; wähle v_{0}^{(0)} ∈ Σ^{∗} mit l_{2}(v_{0}^{(0)}) = n_{0}, dann ist {v_{0}^{(0)}} präfix-frei und damit auch (B_{0}) erfüllt.

m → m + 1: Die Binärwörter w_{0}, …, w_{m−1} ∈ Σ^{∗} mögen (A_{m}) und (B_{m})

erfüllen. Wir bemerken ∑_{k=0}^{m−1} 2^{−n_{k}} + 2^{−n_{m}} ≤ ∑_{k=0}^{∞} 2^{−n_{k}} ≤ 1 und erhalten

2^{−n_{m}} ≤ 1 − ∑_{k=0}^{m−1} 2^{−n_{k}} = ∑_{i∈I_{m}} 2^{−i} nach Wahl von I_{m}, also gibt es ein

i ∈ I_{m} mit i ≦ n_{m}. Setze i_{m} := max { i ∈ I_{m} |i ≦ n_{m} }, das heißt es gilt i_{m} ≦ n_{m}, i_{m} ∈ I_{m} und i_{m} + 1, …, m_{n} ∉ I_{m}.

Mit einer disjunkten Zerlegung v_{i_{m}}^{(m)}Σ^{ω} = w_{m}Σ^{ω} ∪ ⋃_{i=i_{m}+1}^{n_{m}} v_{i}^{(m+1)}Σ^{ω},

wobei l_{2}(w_{m}) = n_{m} (so dass (A_{m}) erfüllt ist) und l_{2}(v_{i}^{(m+1)}) = i für alle i_{m} + 1 ≦ i ≦ n_{m} gelte, erhalten wir die präfix-freie Menge {w_{0}, …, w_{m}} ∪ {v_{i_{m}+1}^{(m+1)}, …, v_{m_{n}}^{(m+1)}} und es gilt

1 − ∑_{k=0}^{m} 2^{−n_{k}} = ∑_{i∈I_{m}} 2^{−i} − 2^{−n_{m}} = ∑_{i∈I_{m+1}} 2^{−i}

mit I_{m+1} := (I_{m} \ {i_{m}}) ∪ {i_{m} + 1, …, n_{m}}. Setze v_{i}^{(m+1)} := v_{i}^{(m)} für

i ∈ I_{m} \ {i_{m}}. □

3.7 Lemma (Hertling [8] Lemma 15)

Sei A ⊂ Σ^{∗} eine rekursiv aufzählbaren Teilmenge.

(1) Es lässt sich eine präfix-freie rekursiv aufzählbare Teilmenge B ⊆ A berechnen, wobei A = B gilt, wenn A bereits präfix-frei ist.

(2) Es lässt sich eine präfix-freie rekursiv aufzählbare Teilmenge B′ ⊂ Σ^{∗} berechnen mit AΣ^{ω} = B′Σ^{ω}, wobei A = B′ gilt, wenn A bereits präfixfrei ist.

Beweis:

Sei (w_{i})_{i≧0} eine berechenbare Folge von Binärwörtern mit A = { w_{i} |i ≧ 0 }.

(1) Sei B_{0} := {w_{0}}. Für n ≧ 1 definieren wir B_{n} := B_{n−1} ∪ {w_{n}}, falls w_{n}Σ^{ω} ∩ B_{n−1}Σ^{ω} = ∅ gilt, anderenfalls B_{n} := B_{n−1}. Dann ist B_{n} ⊆ A für

jedes n ≧ 0 präfix-frei. Nun hat B := ⋃_{n=0}^{∞} B_{n} die gewünschten Eigenschaften.

(2) Wir setzen A_{n} := {w_{0}, …, w_{n}}, l_{n} := max { l_{2}(w) |w ∈ A_{n}) } für alle n ≧ 0 und definieren B′_{0} := {w_{0}} sowie

B′_{n} := { v ∈ Σ^{∗} | l_{2}(v) ≦ l_{n}, vΣ^{ω} ∩ A_{n}Σ^{ω} ≠ ∅, vΣ^{ω} ∩ A_{n−1}Σ^{ω} = ∅ }

für alle n ≧ 1. Dann ist B′ := ⋃_{n=0}^{∞} B′_{n} präfix-frei, und es gilt B′_{n}Σ^{ω} = A_{n}Σ^{ω}

für alle n ≧ 0, also B′Σ^{ω} = ⋃_{i=0}^{∞} A_{n}Σ^{ω} = AΣ^{ω}. Wenn A präfix-frei ist, gilt

B′_{n} = A_{n} für alle n ≧ 0 und wir haben A = B′. □

4 Chaitin-Zufälligkeit

4.1 Definition

Sei f : Σ^{∗} ⇀ Σ^{∗} eine berechenbare partielle Funktion mit Definitionsbereich Def(f) := { w ∈ Σ^{∗} |f(w) ist definiert }.

Dann heißt f selbstbegrenzend, wenn Def(f) präfix-frei ist.

(Diese Definition wird durch das Turingmaschinen-Modell von Chaitin motiviert, das neben dem unendlichen Arbeitsband noch ein endliches Programm-Leseband besitzt. Beendet eine derartige Turingmaschine ihre Berechnung, nachdem sie ein gegebenes Programm vollständig abgearbeitet hat, so hält sie bei keinem echten Anfangsstück dieses Programmes an, und kann auch kein längeres Programm vollständig abarbeiten, wenn dieses das Ausgangsprogramm als Anfangsstück enthält.)

4.2 Definition (Chaitin [4])

Sei f : Σ^{∗} ⇀ Σ^{∗} eine selbstbegrenzende Funktion.

Die Kolmogorov-Komplexität (bezüglich f) eines Binärwortes w ∈ Σ^{∗} wird definiert als

K_{f}(w) := \{ \begin{matrix}min \{ l_{2}(v) |f(v) = w \} & für w ∈ f[Σ^{∗}], \\ ∞ & für w ∉ f[Σ^{∗}]. \end{matrix}

4.3 Definition (Chaitin [4])

Eine berechenbare partielle Funktion u : Σ^{∗} ⇀ Σ^{∗} wird Chaitin-universell genannt, wenn sie selbstbegrenzend ist und für jede selbstbegrenzende Funktion f : Σ^{∗} ⇀ Σ^{∗} eine Konstante c ∈ ℕ existiert mit

K_{u}(w) ≤ K_{f}(w) + c für alle w ∈ Σ^{∗}.

4.4 Bemerkung

Eine Chaitin-universelle Funktion u : Σ^{∗} ⇀ Σ^{∗} ist surjektiv, daher ist ihr Definionsbereich Def(u) unendlich.

(Für jedes w ∈ Σ^{∗} ist die Funktion f_{w} : Σ^{∗} ⇀ Σ^{∗} mit Def(f_{w}) = {ϵ} und f_{w}(ϵ) := w selbstbegrenzend, und es gilt K_{f_{w}}(w) = 0. Daraus folgt K_{u}(w) ≤ c, also w ∈ u[Σ^{∗}].)

4.5 Proposition Es gibt eine Chaitin-universelle berechenbare Funktion u : Σ^{∗} ⇀ Σ^{∗}.

Beweis: (cf. Chaitin [4] p. 46, Proof of Proposition 14 in Hertling [8]) Sei ψ : ℕ_{0} → { f : Σ^{∗} ⇀ Σ^{∗} |f ist berechenbar } eine Aufzählung aller berechenbaren Funktionen. Daraus erhalten wir eine Aufzählung

ϕ : ℕ_{0} → { f : Σ^{∗} ⇀ Σ^{∗} |f ist selbstbegrenzend }

aller selbstbegrenzenden Funktionen, indem wir den Definitionsbereich jeder berechenbaren Funktion f : Σ^{∗} ⇀ Σ^{∗} wie in Lemma 3.7 (1) präfix-frei machen. Definiere nun u : Σ^{∗} ⇀ Σ^{∗} durch

u(0^{m}1v) := ϕ_{m}(v) für alle m ≧ 0 und alle v ∈ Σ^{∗}.

Diese Funktion ist Chaitin-universell, denn

Def(u) = ⋃_{m=0}^{∞} { 0^{m}1v |v ∈ Def(ϕ_{m}) }

ist präfix-frei (0^{m}1v ≠ 0^{n}1w ⟹ m ≠ n oder m = n, v ≠ w) und für jede selbstbegrenzende Funktion f : Σ^{∗} ⇀ Σ^{∗} gibt es ein n ≧ 0 mit f = ϕ_{n}, also

K_{u}(w) = min { l_{2}(0^{m}1v) |m ≧ 0, v ∈ Σ^{∗}, u(0^{m}1v) = w }
≤ min { l_{2}(v) |v ∈ Σ^{∗}, ϕ_{m}(v) = w } + (m + 1) = K_{f}(w) + c

mit c = m + 1. □

4.6 Lemma Sei u : Σ^{∗} ⇀ Σ^{∗} eine Chaitin-universelle Funktion und sei f : Σ^{∗} ⇀ Σ^{∗} eine beliebige berechenbare partielle Funktion. Dann gibt es eine Konstante c ∈ ℕ mit

K_{u}(f(w)) ≤ K_{u}(w) + c für alle w ∈ Def(f).

Beweis:

Die Funktion f ∘ u ist selbstbegrenzend (Def(f ∘ u) ⊆ Def(u) ist präfix-frei). Für alle w ∈ Def(f) gilt K_{f∘u}(f(w)) ≤ K_{u}(w). Weil u Chaitin-universell ist, gibt es eine Konstante c ∈ ℕ mit K_{u}(w) ≤ K_{f∘u}(w) + c für alle w ∈ Σ^{∗}. Insgesamt erhalten wir

K_{u}(f(w)) ≤ K_{f∘u}(f(w)) + c ≤ K_{u}(w) + c für alle w ∈ Def(f).
□

4.7 Feststellung

Seien u, u′ : Σ^{∗} ⇀ Σ^{∗} Chaitin-universelle Funktionen.

Dann gibt es eine Konstante c ∈ ℕ mit

|K_{u}(w) − K_{u′}(w)| ≤ c für alle w ∈ Σ^{∗}.

(Gilt K_{u}(w) ≤ K_{u′}(w) + c_{1} und K_{u′}(w) ≤ K_{u}(w) + c_{2} für alle w ∈ Σ^{∗}, so setze c := max(c_{1}, c_{2}).)

4.8 Definition (Hertling [8] Definition 18)

Sei u : Σ^{∗} ⇀ Σ^{∗} eine Chaitin-universelle Funktion.

(1) Eine Binärfolge s ∈ Σ^{ω} heißt Chaitin-zufällig, wenn es eine Konstante c_{0} ∈ ℕ gibt mit K_{u}(s_{0:i}) ≥ i − c_{0} für alle i ≧ 0.

(2) Eine Binärfolge s ∈ Σ^{ω} heißt stark Chaitin-zufällig, wenn die Folge (K_{u}(s_{0:i}) − i)_{i≧0} über alle Schranken wächst, also lim_{i→∞}(K_{u}(s_{0:i}) − i) = ∞ gilt.

(Wegen Feststellung 4.7 ist diese Definition unabhängig von der Wahl der Chaitin-universellen Funktion u.)

4.9 Satz

Für eine Binärfolge s ∈ Σ^{ω} sind folgende Aussagen äquivalent.

(a) s ist zufällig.

(b) s ist Chaitin-zufällig.

(c) s ist stark Chaitin-zufällig.

Beweis:

Wir zeigen (a) ⇒ (c) ⇒ (b) ⇒ (a). Zusätzlich geben wir einen direkten Beweis von (a) ⇒ (b).

(a) ⇒ (c):

Sei u : Σ^{∗} ⇀ Σ^{∗} eine Chaitin-universelle Funktion und k ≧ 1 fest. Wir definieren eine rekursiv aufzählbare Teilmenge B ⊂ ℕ × Σ^{∗} durch

B_{n} := { w ∈ Σ^{∗} |l_{2}(w) = n, K_{u}(w) ≤ n + k } für alle n ≧ 1

und B := ⋃_{n=1}^{∞}({n} × B_{n}).

Wir weisen nun nach, dass die Familie ( W_{n} |n ≧ 1 ) mit W_{n} := B_{n}Σ^{ω} für alle n ≧ 1 ein Solovay-Test ist.

Wähle für jedes w ∈ Σ^{∗} ein v_{w} ∈ Σ^{∗} mit u(v_{w}) = w und K_{u}(w) = l_{2}(v_{w}). Dann gilt

∑_{n=0}^{∞} μ(W_{n}) = ∑_{n=0}^{∞} ∑_{w∈B_{n}} 2^{−n}

≤ ∑_{n=0}^{∞} ∑_{w∈B_{n}} 2^{k−l_{2}(v_{w})}

= 2^{k} · ∑_{v∈Def(u)} 2^{−l_{2}(v)}

≤ 2^{k}  (Kraft-Ungleichung 3.3).

Sei nun s ∈ Σ^{ω} eine Solovay-zufällige Binärfolge. Dann gibt es ein n ≧ 1 mit s ∉ W_{n+1} = B_{n+1}Σ^{ω} für alle i ≧ n. Nun gilt K_{u}(s_{0:i}) > i + 1 + k für alle i ≧ n, das heißt s ist stark Chaitin-zufällig.

(c) ⇒ (b):

Sei s ∈ Σ^{ω} stark Chaitin-zufällig. Dann wächst die Folge (K_{u}(s_{0:i}) − i)_{i≧0} über alle Schranken, ist also insbesondere nach unten beschränkt.

(b) ⇒ (a):

Sei s ∈ Σ^{ω} Chaitin-zufällig und sei ( V_{n} |n ≧ 1 ) ein Martin-Löf-Test. Dann ist auch ( V′_{n} |n ≧ 1 ) mit V′_{n} := V_{2n+1} für alle n ≧ 1 ein Martin-Löf-Test. Lemma 3.7 (2) liefert eine rekursiv aufzählbare Teilmenge A′ ⊂ ℕ×Σ^{∗} mit präfixfreien Mengen A′_{n} := { w ∈ Σ^{∗} |(n, w) ∈ A′ } und V′_{n} = A′_{n}Σ^{ω} für alle n ≧ 1.

Seien (n_{i})_{i≧0} und (w_{i})_{i≧0} berechenbare Folgen mit A′ = { (n_{i}, w_{i}) |i ≧ 0 }, also

A′_{n} = { w_{i} ∈ Σ^{∗} |i ≧ 0, n_{i} = n } für alle n ≧ 1.

Wegen μ(V′_{n}) ≤ 2^{−(2n+1)} für alle n ≧ 1 gilt

2^{−l_{2}(w_{i})} = μ(w_{i}Σ^{ω}) ≤ μ(A′_{n_{i}}Σ^{ω}) = μ(V′_{n_{i}}) ≤ 2^{−(2n_{i}+1)}

für alle i ≧ 0, also l_{2}(w) ≥ 2n + 1 für alle w ∈ A′_{n}. Wir setzen m_{i} := l_{2}(w_{i}) − n_{i} für alle i ≧ 1 und erhalten

∑_{i=0}^{∞} 2^{−m_{i}} = ∑_{i=0}^{∞} 2^{−l_{2}(w_{i})+n_{i}}

≤ ∑_{n=0}^{∞} 2^{n} ∑_{{ i≧0| n_{i}=n }} 2^{−l_{2}(w_{i})}

= ∑_{n=0}^{∞} 2^{n} ∑_{w∈A′_{n}} 2^{−l_{2}(w)}

= ∑_{n=0}^{∞} 2^{n}μ(V′_{n})

≤ 1  (wegen μ(V′_{n}) ≤ 2^{−(2n+1)}).

Nach dem effektiven Kraft-Chaitin-Theorem 3.6 gibt es nun eine präfix-freie berechenbare Folge (v_{i})_{i≧0} mit l_{2}(v_{i}) = m_{i} für alle i ≧ 0. Durch g(v_{i}) := w_{i} für alle i ≧ 0 definieren wir nun eine selbstbegrenzende Funktion g : Σ^{∗} ⇀ Σ^{∗} mit Def(g) = { v_{i} |i ≧ 0 }. Wir erhalten dann

K_{g}(w) ≤ l_{2}(w) − n für alle w ∈ A′_{n}, n ≧ 1.

Sei u : Σ^{∗} ⇀ Σ^{∗} eine Chaitin-universelle Funktion. Dann existiert eine Konstante c ∈ ℕ mit K_{u}(w) ≤ K_{g}(w) + c für alle w ∈ Σ^{∗}, also haben wir

K_{u}(w) ≤ l_{2}(w) − n + c für alle w ∈ A′_{n}, n ≧ 1.

Da s ∈ Σ^{ω} Chaitin-zufällig ist, gibt es ein c_{0} ∈ ℕ mit K_{u}(s_{0:n}) ≥ n − c_{0} für alle n ≧ 0. Setze n_{0} := c + c_{0} + 2. Wäre s_{0:i} ∈ A′_{n_{0}} für ein i ≧ 0, so folgte i − c_{0} ≤ K_{u}(s_{0:k}) ≤ i + 1 − n_{0} + c, also n_{0} ≦ c + c_{0} + 1, in Widerspruch zur Wahl von n_{0}. Folglich gilt s_{0:i} ∉ A′_{n_{0}} für alle i ≧ 0, also

s ∉ A′_{n_{0}}Σ^{ω} = V′_{n_{0}} = V_{2n_{0}+1},

das heißt s besteht den Martin-Löf-Test ( V_{n} |n ≧ 1 ).

(a) ⇒ (b):

Sei u : Σ^{∗} ⇀ Σ^{∗} eine Chaitin-universelle Funktion. Wir definieren eine rekursiv aufzählbare Teilmenge A ⊂ ℕ × Σ^{∗} durch

A_{n} := { w ∈ Σ^{∗} |K_{u}(w) ≤ l_{2}(w) − n } für alle n ≧ 1

und A := ⋃_{n=1}^{∞}({n} × A_{n}).

Wir weisen nun nach, dass die Familie ( U_{n} |n ≧ 1 ) mit U_{n} := A_{n}Σ^{ω} für alle n ≧ 1 ein Martin-Löf-Test ist.

Wähle für jedes w ∈ Σ^{∗} ein v_{w} ∈ Σ^{∗} mit u(v_{w}) = w und K_{u}(w) = l_{2}(v_{w}). Dann gilt

μ(U_{n}) ≤ ∑_{w∈A_{n}} μ(wΣ^{ω})

= ∑_{w∈A_{n}} 2^{−l_{2}(w)}

≤ ∑_{w∈A_{n}} 2^{−n−K_{u}(w)}

= 2^{−n} · ∑_{w∈A_{n}} 2^{−l_{2}(v_{w})}

≤ 2^{−n} · ∑_{v∈Def(u)} 2^{−l_{2}(v)}

≤ 2^{−n}  (Kraft-Ungleichung 3.3).

Sei nun s ∈ Σ^{ω} eine Martin-Löf-zufällige Binärfolge. Dann gibt es ein n ≧ 1 mit s ∉ V_{n} = A_{n}Σ^{ω}, also K_{u}(s_{0:i}) > i + 1 − n für alle i ≧ 1, das heißt s ist Chaitin-zufällig. □

4.10 Zusatz

Es gibt einen Martin-Löf-Test ( U_{n} |n ≧ 1 ) mit der Eigenschaft, dass jede Binärfolge, die den Test ( U_{n} |n ≧ 1 ) besteht, auch jeden anderen Martin-Löf-Test ( V_{n} |n ≧ 1 ) besteht (universeller Martin-Löf-Test).

(Der Test ( U_{n} |n ≧ 1 ) aus (a) ⇒ (b) im Beweis von Satz 4.9 hat diese Eigenschaft, denn jede Binärfolge die ihn besteht ist Chaitin-zufällig.)

5 Linksberechenbarkeit

5.1 Definition

Sei α eine reelle Zahl.

(1) α wird berechenbar genannt, wenn es eine berechenbare Folge rationaler Zahlen (a_{n})_{n≧0} gibt mit |α − a_{n}| < 2^{−n} für alle n ≧ 0.

(Dabei heißt eine Folge rationaler Zahlen (a_{n})_{n≧1} berechenbar, wenn es berechenbare Folgen natürlicher Zahlen (i_{n})_{n≧0}, (j_{n})_{n≧0} und (k_{n})_{n≧0} gibt mit a_{n} = \frac{i_{n}−j_{n}}{1+k_{n}} für alle n ≧ 0.)

(2) Unter einer aufsteigenden Approximation von α wollen wir eine streng monoton wachsende berechenbare Folge rationaler Zahlen verstehen, die gegen α konvergiert.

(3) Eine reelle Zahl α heißt linksberechenbar, wenn es eine aufsteigende Approximation von α gibt.

5.2 Beispiel

Jede rationale Zahl ist berechenbar.

(Für α = q ∈ ℚ hat die Folge (q_{n})_{n≧0} mit q_{n} := q − 2^{−(n+1)} für alle n ≧ 0 die gewünschte Eigenschaft.)

5.3 Bemerkungen

Sei α eine reelle Zahl.

(1) α ist genau dann berechenbar, wenn es eine berechenbare Folge von Binärwörtern (w_{n})_{n≧0} gibt mit |α − ⟨w_{n}⟩_{2}| < 2^{−n} für alle n ≧ 0.

(Wähle w_{n} ∈ Σ^{∗} mit |a_{n+1} − ⟨w_{n}⟩_{2}| < 2^{−(n+1)} für alle n ≧ 0.)

(2) α ist genau dann berechenbar, wenn sowohl α als auch −α linksberechenbar sind.

(Vgl. [1] Lemma 4.31.)

5.4 Proposition (vgl. [2] Theorem 4.1)

Für eine reelle Zahl 0 < α ≤ 1 sind folgende Aussagen äquivalent:

(a) α ist linksberechenbar.

(b) Es gibt eine berechenbare Folge von Binärwörtern (w_{n})_{n≧0} mit der Eigenschaft, dass (⟨w_{n}⟩_{2})_{n≧0} eine aufsteigende Approximation von α ist.

(c) Es gibt eine monoton wachsende berechenbare Folge rationaler Zahlen, die gegen α konvergiert.

(d) Es gilt α = 2^{−A} mit einer unendlichen präfix-freien rekursiv aufzählbaren Teilmenge A ⊂ Σ^{∗}.

(e) Es gilt α = 2^{−A} mit einer unendlichen präfix-freien rekursiv entscheidbaren Teilmenge A ⊂ Σ^{∗}.

Beweis:

(a) ⇒ (b): Berechne w_{n} ∈ Σ^{∗} mit a_{n} < ⟨w_{n}⟩_{2} < a_{n+1} für alle n ≧ 0.

(b) ⇒ (c) ist klar.

(c) ⇒ (a):

Sei (a_{n})_{n≧0} eine monoton wachsende berechenbare Folge rationaler Zahlen, die gegen α konvergiert. Setze a′_{n} := \frac{a_{0}+···+a_{n}}{n+1} − \frac{1}{n+1} für alle n ≧ 0. Wegen a_{0} + ⋯ + a_{n} − 1 < (n + 1)a_{n+1} für alle n ≧ 0 ist (a′_{n})_{n≧0} streng monoton wachsend und wegen lim_{n→∞} \frac{a_{0}+···+a_{n}}{n+1} = α konvergiert auch (a′_{n})_{n≧0} gegen α.

(a) ⇒ (e):

Sei (a_{n})_{n≧0} eine aufsteigende Approximation von α mit 0 < a_{n} < α ≤ 1 für alle n ≧ 0. (Gilt nicht a_{0} > 0, so setze m := min { n ≧ 0 |a_{n} > 0 } und betrachte (a_{m+n})_{n≧0}.)

Konstruiere eine monoton über alle Schranken wachsende berechenbare Folge (n_{k})_{k≧0} und eine streng monoton wachsende berechenbare Folge (m_{k})_{k≧0} mit

∑_{k=0}^{m_{j}} 2^{−n_{k}} < a_{j} < 2^{−j} + ∑_{k=0}^{m_{j}} 2^{−n_{k}} für alle j ≧ 0,

insbesondere also ∑_{k=0}^{∞} 2^{−n_{k}} = α. Das Effektive Kraft-Chaitin-Theorem 3.6 liefert nun eine berechenbare Folge (w_{k})_{k≧0} mit l_{2}(w_{k}) = n_{k} für alle k ≧ 0. Für die präfix-freie Menge A := { w_{k} |k ≧ 0 } gilt 2^{−A} = ∑_{k=0}^{∞} 2^{−n_{k}} = α. Sie ist rekursiv entscheidbar und unendlich, weil die Folge (l_{2}(w_{k}))_{k≧0} monoton über alle Schranken wachsend ist.

(e) ⇒ (d) ist klar.

(d) ⇒ (a): Sei (v_{k})_{k≧0} eine injektive berechenbare Aufzählung von A. Dann liefert

a_{n} := ∑_{k=0}^{n} 2^{−l_{2}(v_{k})} für alle n ≧ 0

eine aufsteigende Approximation von α = 2^{−A}. □

6 Ω-Zahlen und Ω-ähnliche Zahlen

6.1 Bezeichnungen (Chaitin [4] p. 48)

(1) Sei f : Σ^{∗} ⇀ Σ^{∗} eine selbstbegrenzende Funktion.

Unter einer Haltewahrscheinlichkeit von f versteht man die reelle Zahl μ(Def(f)Σ^{ω}) = ∑_{w∈Def(f)} 2^{−l_{2}(w)} = 2^{−Def(f)}.

(2) Als Ω-Zahl bezeichnet man die Haltewahrscheinlichkeit einer Chaitin-

universellen (siehe 4.3) Funktion u : Σ^{∗} ⇀ Σ^{∗}, also Ω_{u} := 2^{−Def(u)}.

6.2 Definition (cf. Kučera/Slaman [11] Def. 1.13, Hertling [8] Def. 22) Seien α und β linksberechenbare reelle Zahlen.

(1) Seien (a_{n})_{n≧0} und (b_{n})_{n≧0} aufsteigende Approximationen von α beziehungsweise β (vgl. 5.1 (2)). (a_{n})_{n≧0} dominiert (b_{n})_{n≧0}, wenn es eine Konstante c ∈ ℕ gibt mit

c(α − a_{n}) ≥ (β − b_{n}) für alle n ≧ 0.

(2) α dominiert β, wenn es aufsteigende Approximationen (a_{n})_{n≧0} von α und (b_{n})_{n≧0} von β gibt mit (a_{n})_{n≧0} dominiert (b_{n})_{n≧0}.

Wir schreiben dann α ≥_{dom} β.

6.3 Beobachtung Seien (a_{n})_{n≧0}, (b_{n})_{n≧0} und (c_{n})_{n≧0} aufsteigende Approximationen von linksberechenbaren reellen Zahlen α, β beziehungsweise γ.

(1) Es gilt (a_{n})_{n≧0} dominiert (a_{n})_{n≧0}.

(2) Gilt (a_{n})_{n≧0} dominiert (b_{n})_{n≧0} und (b_{n})_{n≧0} dominiert (c_{n})_{n≧0}, so auch (a_{n})_{n≧0} dominiert (c_{n})_{n≧0}.

(Für (1) wähle c = 1; für (2) bemerke, dass aus c(α − a_{n}) ≥ (β − b_{n}) und c′(β − b_{n}) ≥ (γ − c_{n}) folgt cc′(α − a_{n}) ≥ (γ − c_{n}).)

6.4 Feststellung Ist α eine linksberechenbare reelle Zahl, und sind (a_{n})_{n≧0} und (a′_{n})_{n≧0} aufsteigende Approximationen von α, so gibt es eine streng monoton wachsende berechenbare Folge natürlicher Zahlen (m_{n})_{n≧0}, so dass (a_{n})_{n≧0} die Teilfolge (a′_{m_{n}})_{n≧0} dominiert. (Durch m_{0} := min { k ≧ 0 |a′_{k} > a_{0} } und m_{n} := min { k > m_{n−1} |a′_{k} > a_{n} } für alle n ≧ 0 wird eine streng monoton wachsende berechenbare Folge natürlicher Zahlen (m_{n})_{n≧0} definiert. Dann gilt (α − a_{n}) > (α − a′_{m_{n}}) für alle n ≧ 0.)

6.5 Folgerung (Hertling [8] Lemma 24) Die Relation ≥_{dom} ist reflexiv und transitiv.

Beweis: Reflexivität ist klar nach 6.3 (1). Für die Transitivität seien α, β und γ linksberechenbare reelle Zahlen mit α ≥_{dom} β und β ≥_{dom} γ. Weiter seien (a_{n})_{n≧0}, (b_{n})_{n≧0}, (b′_{n})_{n≧0} und (c_{n})_{n≧0} aufsteigende Approximationen von α, β, β beziehungsweise γ, (a_{n})_{n≧0} dominiere (b_{n})_{n≧0} und (b′_{n})_{n≧0} dominiere (c_{n})_{n≧0}. Nach 6.4 gibt es eine Teilfolge (b′_{m_{n}})_{n≧0}, die von (b_{n})_{n≧0} dominiert wird. Dann ist (b′_{m_{n}})_{n≧0} eine aufsteigende Approximation von β, und (b′_{m_{n}})_{n≧0} dominiert die aufsteigende Approximation (c_{m_{n}})_{n≧0} von γ. Wegen (a_{n})_{n≧0} dominiert (c_{m_{n}})_{n≧0} (nach Beobachtung 6.3 (2)) folgt α ≥_{dom} γ. □

6.6 Definition (cf. Kučera/Slaman [11] Def. 1.13, Hertling [8] Def. 22)

(1) Sei (a_{n})_{n≧0} eine aufsteigende Approximation (einer linksberechenbaren reellen Zahl α), also eine konvergente streng monoton wachsende berechenbare Folge rationaler Zahlen.

Dann heiße (a_{n})_{n≧0} universell, wenn (a_{n})_{n≧0} jede aufsteigende Approximation (b_{n})_{n≧0} (einer rellen Zahl β) dominiert.

(2) Sei α eine reelle Zahl mit 0 < α < 1.

Dann wird α als Ω-ähnlich bezeichnet, wenn es eine universelle aufsteigende Approximation (a_{n})_{n≧0} gibt, die gegen α konvergiert.

6.7 Lemma (cf. Hertling [8] Lemma 26)

Seien (a_{n})_{n≧0} und (b_{n})_{n≧0} aufsteigende Approximationen von linksberechenbaen reellen Zahlen α beziehungsweise β, es gelte α > 0 und (a_{n})_{n≧0} dominiere (b_{n})_{n≧0}.

Dann gibt es eine berechenbare Folge natürlicher Zahlen (n_{k})_{k≧0} und eine

Konstante c_{0} ∈ ℕ mit ∑_{k=0}^{∞} 2^{−n_{k}} = α und

2^{c_{0}} · 2^{−n_{k}} > (b_{k} − b_{k−1}) für alle k ≧ 1.

Beweis:

Ohne Beschränkung der Allgemeinheit gelte a_{0} > 0. (Gilt a_{0} ≤ 0, so setze m := min { n ≧ 0 |a_{n} > 0 }. Dann wird (b_{m+n})_{n≧0} von (a_{m+n})_{n≧0} dominiert, und ist c′_{0} ∈ ℕ mit 2^{c′_{0}} · 2^{−n_{k}} > (b_{k+1} − b_{k}) für alle k ≧ m, so wähle c_{0} ≧ c′_{0} mit 2^{c_{0}} > max { 2^{n_{k}}(b_{k+1} − b_{k}) |0 ≦ k < m }.)

Sei c ∈ ℕ mit c(α − a_{n}) ≥ (β − b_{n}) für alle n ≧ 0. Wähle ein c_{0} ∈ ℕ mit 2^{c_{0}−1} > c, also

(∗) 2^{c_{0}−1}(α − a_{n}) > (β − b_{n}) für alle n ≧ 0.

Zunächst definieren wir rekursiv eine streng monoton wachsende Folge natürlicher Zahlen (m_{k})_{k≧0} mit m_{0} := 0 und

m_{k+1} := min { m > m_{k} |2^{c_{0}−1}(a_{m} − a_{m_{k}}) > (b_{m} − b_{m_{k}}) }.

(Wegen (∗) ist die Menge nicht leer.)

Weiter definieren wir eine berechenbare Folge positiver rationaler Zahlen (q_{i})_{i≧0} durch q_{0} := a_{0} und für jedes i ≧ 0

q_{i+1} := (b_{i+1} − b_{i})\frac{a_{m_{k+1}} − a_{m_{k}}}{b_{m_{k+1}} − b_{m_{k}}}, falls m_{k} ≦ i < m_{k+1} (k ≧ 0).

Dann gilt ∑_{i=m_{k}}^{m_{k+1}−1} q_{i+1} = a_{m_{k+1}} − a_{m_{k}} für alle k ≧ 0, also ∑_{i=0}^{∞} q_{i} = α und

2^{c_{0}−1}q_{i+1} > (b_{i+1} − b_{i}) für alle i ≧ 0.

Schließlich definieren wir die berechenbare Folge (n_{k})_{k≧0} durch

n_{k} := min { j ≧ 0 |2^{−j} ≤ ∑_{i=0}^{k} q_{i} − ∑_{i=0}^{k−1} 2^{−n_{i}} } für alle k ≧ 0.

Nach Konstruktion haben wir

∑_{i=0}^{k} 2^{−n_{i}} ≤ ∑_{i=0}^{k} q_{i} < ∑_{i=0}^{k} 2^{−n_{i}} + 2^{−n_{k}} für alle k ≧ 0

und 2^{−(n_{i}−1)} ≥ q_{i} für alle i ≧ 0 (vollständige Induktion), also ∑_{k=0}^{∞} 2^{−n_{k}} = α

(wegen ∑_{i=0}^{k} 2^{−n_{i}} ≤ α für alle k ≥ 0 ist (n_{k})_{k≧0} eine Nullfolge) und

2^{c_{0}} · 2^{−n_{i+1}} > (b_{i+1} − b_{i}) für alle i ≧ 0. □

7 Linksberechenbare zufällige Zahlen

7.1 Definition Eine reelle Zahl α ≥ 0 heiße zufällig, wenn es eine ganze Zahl k ≧ 0 und eine zufällige Binärfolge s ∈ Σ^{ω} gibt mit α = k + ⟨s⟩_{2}, wenn sie also eine Binärdarstellung besitzt, deren Nachkommastellen eine zufällige Binärfolge bilden.

7.2 Feststellung Eine berechenbare reelle Zahl α kann nicht zufällig sein. (Mit Hilfe von Hinweis 5.3 (1) erhalten wir eine Folge von Binärwörtern (w_{n})_{n≧0} mit |α − ⟨w_{n}⟩_{2}| < 2^{−n} für alle n ≧ 0. Nun definiert

V_{n} := { s ∈ Σ^{ω} |d(s_{0:n}, w_{n}) < 2^{−n} } für alle n ≧ 1

einen Martin-Löf-Test, den die Nachkommastellen einer Binärdarstellung von α nicht bestehen können.)

7.3 Satz (Calude et al. [2] Theorem 6.6, Kučera/Slaman [11] Theorem 2.1)

Für eine reelle Zahl α mit 0 < α < 1 sind folgende Aussagen äquivalent.

(a) α ist linksberechenbar und zufällig.

(b) α ist linksberechenbar und jede aufsteigende Approximation von α ist universell.

(c) α ist Ω-ähnlich.

(d) α ist eine Ω-Zahl.

(e) α ist ≥_{dom} -maximal, das heißt α ist linksberechenbar mit α ≥_{dom} β für alle linksberechenbaren reellen Zahlen β.

Beweis:

(a) ⇒ (b):

Sei (a_{n})_{n≧0} eine aufsteigende Approximation von α. Um nachzuweisen, dass (a_{n})_{n≧0} universell ist, betrachten wir eine beliebige aufsteigende Approximation (b_{n})_{n≧0} (einer reellen Zahl β) und zeigen: (a_{n})_{n≧0} dominiert (b_{n})_{n≧0}.

Wir dürfen ohne Beschränkung der Allgemeinheit annehmen, dass sämtliche Zahlen a_{n} und b_{n} dyadisch sind, also die Form z/2^{k} haben mit einer ganzen Zahl z und einer natürlichen Zahl k.

(Berechne dyadische Zahlen a′_{n} und b′_{n} mit a_{n} < a′_{n} < a_{n+1}, b′_{0} < b_{0} und b_{n} < b′_{n+1} < b_{n+1} für alle n ≧ 0. Dann sind (a′_{n})_{n≧0} und (b′_{n})_{n≧0} streng monoton wachsend mit lim_{n→∞} a′_{n} = α und lim_{n→∞} b′_{n} = β. Weisen wir (a′_{n})_{n≧0} dominiert (b′_{n})_{n≧0} nach, so folgt auch (a_{n})_{n≧0} dominiert (b_{n})_{n≧0}. )

Weiter dürfen wir 0 = a_{0} < a_{1} < ⋯ < α < 1 und 0 = b_{0} < b_{1} < ⋯ < β < 1 annehmen.

(Für m ≧ 0 mit 2^{m} > max(α − a_{0}, β − b_{0}) betrachte ã_{n} := \frac{a_{n} − a_{0}}{2^{m}} und

b̃_{n} := \frac{b_{n} − b_{0}}{2^{m}} für alle n ≧ 0. Dann gilt α̃ := lim_{n→∞} ã_{n} = \frac{α − a_{0}}{2^{m}} < 1 und

β̃ := lim_{n→∞} b̃_{n} = \frac{β − b_{0}}{2^{m}} < 1. )

Zunächst konstruieren wir eine Familie ( A_{n} |n ≧ 1 ) von rekursiv aufzählbaren Teilmengen A_{n} ⊆ Σ^{∗}, dann durch V_{n} := A_{n}Σ^{ω} für alle n ≧ 1 einen Martin-Löf-Test.

Sei n ≧ 1 fest. Wir definieren rekursiv eine aufsteigende Folge von Teilmengen A_{n}^{(i)} ⊂ Σ^{∗} für alle i ≧ 0. Parallel dazu definieren wir eine aufsteigende Folge von Teilmengen C_{n}^{(i)} ⊂ [0, 1] mit C_{n}^{(i)} = { ⟨s⟩_{2} |s ∈ A_{n}^{(i)}Σ^{ω} } für alle i ≧ 0. Außerdem konstruieren wir eine (von n abhängige) Folge (m_{i})_{i≧0}, die angibt, in wievielen der Schritte, die zur Berechnung von A_{n}^{(i)} geführt haben, Elemente zur vorhergehenden Menge hinzugefügt worden sind. Schließlich definieren wir eine (von n abhängige) Funktion f : ℕ_{0} ⇀ ℕ_{0}, m ↦ f(m), die angibt, bei welchem Index i = f(m) zum m-ten Male Elemente zur vorhergehenden Menge hinzugefügt wurden.

Wir setzen A_{n}^{(0)} := ∅, C_{n}^{(0)} := ∅, m_{0} := 0 und f(0) := 0. Für i ≧ 1 setzen wir A_{n}^{(i)} := A_{n}^{(i−1)} und m_{i} := m_{i−1}, falls a_{i} im Inneren von C_{n}^{(i−1)} liegt; anderenfalls bestimmen wir eine endliche präfix-freie Teilmenge B_{n}^{(i)} ⊂ Σ^{∗} mit

{ ⟨s⟩_{2} |s ∈ B_{n}^{(i)}Σ^{ω} } = [a_{n}, a_{n} + 2^{−n}(b_{n} − b_{f(m_{i−1})})]

und setzen A_{n}^{(i)} := A_{n}^{(i−1)} ∪ B_{n}^{(i)}, C_{n}^{(i)} := C_{n}^{(i−1)} ∪ [a_{n}, a_{n} + 2^{−n}(b_{n} − b_{f(m_{i−1})})], m_{i} := m_{i−1} + 1 sowie f(m_{i}) := i.

Ist n ≧ 1, so gilt für A_{n} := ⋃_{k=0}^{∞} A_{n}^{(k)} die folgende Abschätzung

μ(A_{n}Σ^{ω}) = ∑_{0<m∈Def(f)} \frac{b_{f(m)} − b_{f(m−1)}}{2^{n}} ≤ \frac{β − b_{0}}{2^{n}} ≤ 2^{−n}.

Durch V_{n} := A_{n}Σ^{ω} für alle n ≧ 1 erhalten wir daher einen Martin-Löf-Test ( V_{n} |n ≧ 1 ). Weil α eine zufällige reelle Zahl ist, gibt es eine zufällige Binärfolge s ∈ Σ^{ω} mit ⟨s⟩_{2} = α und ein n ≧ 1 mit s ∉ V_{n}, also

α = ⟨s⟩_{2} ∉ C_{n} := ⋃_{i=0}^{∞} C_{n}^{(i)}.

Nun zeigen wir (a_{n})_{n≧0} dominiert (b_{n})_{n≧0} durch Nachweis der Abschätzung 2^{n}(α − a_{k}) ≥ (β − b_{k}) für alle k ≧ 0.

Wegen α ∉ C_{n} gibt es zu jedem i ≧ 0 ein i′ > i mit a_{i′} ∉ C_{n}. Nach Konstruktion gilt daher Def(f_{n}) = ℕ_{0}, das heißt bei der Konstruktion der A_{n}^{(i)} sind unendlich oft Elemente hinzugefügt worden. Daher ist die Folge (f(j))_{j≧0} streng monoton wachsend und es gilt a_{f(j+2)} ≥ a_{f(j+1)} + 2^{−n} · (b_{f(j+1)} − b_{f(j)}) für alle j ≧ 0, also

\begin{aligned}2^{n} · (α − a_{f(m+1)}) & = & 2^{n} · ∑_{j=m}^{∞}(a_{f(j+2)} − a_{f(j+1)}) \\ & ≥ & ∑_{j=m}^{∞}(b_{f(j+1)} − b_{f(j)}) = (β − b_{f(m)}) \end{aligned}

für alle m ≧ 0. Ist nun k ≧ 0 gegeben, so haben wir f(j_{k}) ≦ k < f(j_{k} + 1) mit j_{k} := max { j ≧ 0 |f(j) ≦ k }, also

2^{n} · (α − a_{k}) ≥ 2^{n} · (α − a_{f(j_{k}+1)}) ≥ (β − b_{f(j_{k})}) ≥ (β − b_{k}).

(b) ⇒ (c) ist klar.

(c) ⇒ (d):

Sei (a_{n})_{n≧0} eine universelle aufsteigende Approximation von α. Weiter sei u : Σ^{∗} ⇀ Σ^{∗} eine Chaitin-universelle Funktion und Ω_{u} := 2^{−Def(u)} sei ihre Ω-Zahl.

Sei (v_{k})_{k≧0} eine berechenbare Folge von Binärwörtern, in der jedes Element von Def(u) genau einmal vorkommt. Wegen der Universalität von (a_{n})_{n≧0}

dominiert (a_{n})_{n≧0} die Folge (b_{n})_{n≧0} mit b_{n} := ∑_{k=0}^{n} 2^{−l_{2}(v_{k})} für alle n ≧ 0.

Lemma 6.7 liefert nun eine berechenbare Folge (n_{k})_{k≧0} mit ∑_{k=0}^{∞} 2^{−n_{k}} = α und

eine Konstante c_{0} ∈ ℕ mit 2^{c_{0}} · 2^{−n_{k}} > 2^{−l_{2}(v_{k})} für alle k ≧ 1, also gibt es ein c ∈ ℕ mit

c − n_{k} > −l_{2}(v_{k}) für alle k ≧ 0.

Das Effektive Kraft-Chaitin-Theorem 3.6 liefert eine berechenbare Folge von Binärwörtern (w_{k})_{k≧0} mit l_{2}(w_{k}) = n_{k} für alle k ≧ 0, derart dass { w_{k} |k ≧ 0 } präfix-frei ist. Wir definieren nun eine berechenbare Funktion ũ : Σ^{∗} ⇀ Σ^{∗} mit Def(ũ) = { w_{k} |k ≧ 0 } durch ũ(w_{k}) := u(v_{k}) für alle k ≧ 0. Die Funktion ũ ist selbstbegrenzend, und wegen l_{2}(w_{k}) < l_{2}(v_{k}) + c für alle k ≧ 0 gilt

Kũ(w) ≤ K_{u}(w) + c für alle w ∈ Σ^{∗},

also ist auch ũ Chaitin-universell. Schließlich gilt

Ωũ = 2^{−Def(ũ)} = ∑_{k=0}^{∞} 2^{−l_{2}(w_{k})} = ∑_{k=0}^{∞} 2^{−n_{k}} = α,

das heißt α ist eine Ω-Zahl.

(d) ⇒ (a): Sei u : Σ^{∗} ⇀ Σ^{∗} eine Chaitin-universelle Funktion und Ω_{u} := 2^{−Def(u)} sei ihre Ω-Zahl. Nach Proposition 5.4 ist Ω_{u} linksberechenbar. Wir zeigen nun, dass die Folge der Nachkommastellen s ∈ Σ^{ω} einer Binärdarstellung von Ω_{u} = ⟨s⟩_{2} Chaitinzufällig sind. Sei (v_{k})_{k≧0} eine injektive berechenbare Aufählung von Def(u). Dann liefert a_{n} := ∑_{k=0}^{n−1} 2^{−l_{2}(v_{k})} für alle n ≧ 0 eine aufsteigende Approximation von Ω_{u}.

Definiere nun eine berechenbare Funktion g : Σ^{∗} ⇀ Σ^{∗} mit Definitionsbereich Def(g) = { w ∈ Σ^{∗} |⟨w⟩_{2} < Ω_{u} } und Werten

g(w) := min_{llex}(Σ^{∗} \ {u(v_{0}), …, u(v_{ℓ_{w}})}, ℓ_{w} := min { n ≧ 0 |⟨w⟩_{2} ≤ a_{n} },

für alle w ∈ Σ^{∗} mit ⟨w⟩_{2} < Ω_{u}, wobei das Minimum min_{llex} bezüglich der längen-lexikographischen Ordnung (vgl. 1.3) zu bilden ist. Wir weisen nun folgende Abschätzung nach

K_{u}(g(s_{0:n})) ≥ n für alle n ≧ 0.

Mit m_{n} := min { m ≧ 0 |⟨s_{0:n}⟩_{2} ≤ a_{m} } gilt ℓ_{s_{0:n}} ≧ m_{n} und

⟨s_{0:n}⟩_{2} ≤ a_{m_{n}} < a_{m_{n}} + ∑_{k=m_{n}}^{∞} 2^{−l_{2}(v_{k})} = Ω_{u} ≤ ⟨s_{0:n}⟩_{2} + 2^{−n},

also l_{2}(v_{k}) ≧ n für alle k ≧ m_{n}, woraus sich nach Definition von g die behauptete Abschätzung der Kolmogorov-Komplexität ergibt. Lemma 4.6 liefert nun eine Konstante c ∈ ℕ mit

\begin{aligned}K_{u}(s_{0:n}) & ≥ & K_{u}(g(s_{0:n})) − c \\ & ≥ & n − c & für alle n ≧ 0. \end{aligned}

Die Binärfolge s ist also (Chaitin-)zufällig.

(b) ⇒ (e) ist klar.

(e) ⇒ (c): Die linksberechenbare reelle Zahl α sei ≥_{dom} -maximal. Sei u : Σ^{∗} ⇀ Σ^{∗} eine Chaitin-universelle Funktion mit Ω-Zahl Ω_{u} := 2^{−Def(u)}. Wegen (d) ⇒ (a) ist Ω_{u} linksberechenbar, daher gilt α ≥_{dom} Ω_{u}. Seien (a_{n})_{n≧0} und (b_{n})_{n≧0} aufsteigende Approximationen von α beziehungsweise Ω_{u}, und (a_{n})_{n≧0} dominiere (b_{n})_{n≧0}. Wegen (d) ⇒ (b) ist (b_{n})_{n≧0} und damit auch (a_{n})_{n≧0} universell. □

7.4 Ausblick

Kučera und Slaman geben eine weitere Bedingung an, die zu denen aus 7.3 äquivalent ist (Theorem 3.3 in [11]):

(f) Es gibt einen universellen Martin-Löf-Test ( U_{n} |n ≧ 1 ) mit

α = ∑_{n=1}^{∞} μ(U_{n}).

Literatur

[1] Vasco Brattka, Peter Hertling, Klaus Weihrauch: Einführung in die Berechenbare Analysis. Kurs 01681 der FernUniversität: Hagen, Wintersemester 1999/2000.

[2] Christian S. Calude, Peter H. Hertling, Bakhadyr Khoussainov, Yongge Wang: Recursively Enumerable Reals and Chaitin Ω-Numbers. Theor. Comp. Sci. 225 (2001) 125-149.

[3] Gregory J. Chaitin: A theory of program size formally identical to information theory. Journal of the ACM 22 (1975) 329–340. (Reprinted in [5] 107–122.)

[4] Gregory J. Chaitin: Algorithmic Information Theory.

IBM Journal of Research and Development 21 (1977) 350–359, 496. (Reprinted in [5] 38–52.)

[5] Gregory J. Chaitin: Information, Randomness and Incompleteness. Papers on Algorithmic Information Theory. World Scientific: Signapore, 1987.

[6] Richard L. Epstein, Walter A. Carnielli: Computability.

Computable Functions, Logic, and the Foundations of Mathematics. Wadsworth&Brooks: Pacific Grove, California, 1989.

[7] Hans Hermes: Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. Springer: Berlin, Göttingen, Heidelberg, 1961.

[8] Peter Hertling: Characterizations of Effectively Random Sequences and of Omega Numbers. Preprint, preliminary, incomplete version. FernUniversität: Hagen, 8. Mai 2001.

[9] Ming Li, Paul Vitányi: An Introduction to Kolmogorov Complexity and Its Applications. 2nd ed. Springer: New York, 1997.

[10] Per Martin-Löf: The Definition of Random Sequences.

Information and Control 9 (1966) 602–619.

[11] Antonín Kučera, Theodore A. Slaman: Randomness and Recursive Enumerability. Preprint, April 2001.

http://math.berkeley.edu/~slaman/papers/random.pdf

[12] Robert M. Solovay: Draft of a paper (or series of papers) on Chaitin’s work … done for the most part during the period of Sept.–Dec. 1974. Unpublished manuscript, 215 pp. IBM Thomas J. Watson Research Center: Yorktown Heights, New York, May 1975.

[13] Ingrid Voigt: Der algorithmische Zufallsbegriff.

Ausarbeitung des ersten Vortrages im Seminar 01929, FernUniversität Hagen, Sommersemester 2001. Unveröffentlichtes Manuskript, 12 Seiten.