Nicht berechenbare reelle Zahlen
Turings Zahl: nicht berechenbar, aber komprimierbar
Wie man Turings Zahl komprimiert
Chaitins Zahl: nicht berechenbar und nicht komprimierbar
Chaitins Zahl und das Halteproblem
Chaitins Zahl und die Aussagekraft formaler Systeme
Chaitins Zahl ist die optimale Verschlüsselung von Information
Deshalb ist Chaitins Zahl nicht komprimierbar
Der tiefere Grund für die Unvollständigkeit formaler Systeme
Zufall und die Lösbarkeit mathematischer Probleme
Die ersten 64 Bit von Chaitins Zahl
Chaitins Zahlen sind maximal häufig
Zufallszahlen der Weisheit
Wir haben im letzten Kapitel die beiden Begriffe Zufallszahl und Komplexität einer Zahl kennengelernt. Die Komplexität einer Zahl war die Bitlänge des kürzesten Programms, das die Zahl ausgibt (wobei wir zuvor eine Programmiersprache, Compiler und Computer festlegen müssen), und eine Zufallszahl war eine Zahl, deren Komplexität ungefähr ihrer Bitlänge entspricht (bei Zahlen mit endlichem Binärstring ist diese Definition etwas unscharf, denn man muss sagen, um wieviel die Komplexität der Zahl unterhalb ihrer Bitlänge liegen darf, damit sie noch zufällig genannt werden soll; bei Zahlen mit unendlichem Binärstring dagegen ist die Definition präzise, vgl. Kapitel 3.3).
Normalerweise sind Zahlen, die in der Mathematik eine Rolle spielen, keine Zufallszahlen. Aus ihre mathematischen Definition kann man in den meisten Fällen eine Vorschrift zur Berechnung der Zahl ableiten, so dass man ein Programm schreiben kann, das die ersten n Binärstellen der Zahl berechnen kann und das dabei eine Länge deutlich unterhalb von n aufweist. Beispiele für solche Zahlen sind die Zahl \( \pi \) oder die Eulersche Zahl \( e = 2,7182818285...\) .
Andererseits haben wir bereits nicht-berechenbare Größen kennengelernt, die sich mathematisch durchaus definieren lassen. Ein Beispiel für eine solche nicht-berechenbare Größe ist die Komplexität einer Zahl. Eine mathematische Definition muss also nicht unbedingt eine Rechenvorschrift beinhalten. Es ist daher durchaus denkbar, dass man relle Zahlen mathematisch definieren kann, die nicht nur nicht-berechenbar sind, sondern die sogar Zufallszahlen sind (die also nicht komprimierbar sind).
Wir wollen uns dem Problem schrittweise nähern (siehe z.B. Gregory Chaitin: Randomness in Arithmetic and the Decline & Fall of Reductionism in Pure Mathematics und Gregory Chaitin: Paradoxes of Randomness) und noch einmal wiederholen, was wir über berechenbare Zahlen wissen.
In Kapitel 2.3 haben wir uns mit unendlichen Folgen natürlicher Zahlen beschäftigt wie z.B. die Folge \(3, 9, 27, 81, ... \). Diese Folge definiert eine mathematische Funktion in den natürlichen Zahlen. Das bedeutet, dass jeder natürlichen Zahl \(n\), für die die Funktion \(f\) definiert ist, durch die Funktion \(f\) der \(n\)-te Folgeneintrag \(f(n)\) zugeordnet wird.
Die Unlösbarkeit von Turings Halteproblem führt dazu, dass man Funktionen definieren kann, die nicht berechenbar sind. Das bedeutet, dass man keine allgemeine Rechenvorschrift angeben kann, mit der sich alle definierten Werte von \(f(n)\) berechnen lassen. In Kapitel 2.3 haben wir Beispiele dafür kennengelernt.
Statt über natürliche Zahlenfolgen und Funktionen zu sprechen, kann man genauso gut auch über reelle Zahlen reden, denn man kann aus jeder Zahlenfolge natürlicher Zahlen sehr einfach eine reelle Zahl machen. Aus der Folge \(3, 9, 27, 81, ... \) kann man beispielsweise die reelle Zahl \( 0,392781... \) konstruieren, indem man einfach die Zahlen der Folge als Dezimalstellen hintereinanderhängt. Umgekehrt kann man die Dezimalstellen einer reellen Zahl als Elemente einer Zahlenfolge auffassen.
Eine Rechenvorschrift, die eine natürliche Zahlenfolge (also eine Funktion \(f\) in den natürlichen Zahlen) berechnet, kann also leicht in eine Rechenvorschrift zur Berechnung einer reellen Zahl umgewandelt werden und umgekehrt. Statt von berechenbaren oder nicht-berechenbaren Funktionen bzw. Zahlenfolgen zu sprechen, kann man gleichwertig dazu über berechenbare und nicht-berechenbare reelle Zahlen reden. Also gilt:
Um eine Zufallszahl zu konstruieren, brauchen wir eine Zahl, die möglichst wenig berechenbar ist. Erinnern wir uns: Es ist durchaus möglich, bei einer nicht-berechenbaren Zahl einzelne Dezimalstellen mit Hilfe einer Rechenvorschrift zu berechnen. Nicht-Berechenbarkeit bedeutet nur, dass sich nicht alle Dezimalstellen mit einer einzigen Rechenvorschrift berechnen lassen. Auch zwei Rechenvorschriften reichen nicht, denn diese könnte man ja zu einer einzigen Rechenvorschrift zusammenfassen. Um alle Dezimalstellen einer nicht-berechenbaren reellen Zahl zu berechnen, benötigt man unendlich viele Rechenvorschriften.
Nun könnte es aber beispielsweise sein, dass man eine Rechenvorschrift findet, die 50% der Stellen einer nicht-berechenbaren reellen Zahl (wir schreiben sie als Binärzahl) ausgeben kann. Dann könnte man für die ersten \(n\) Binärstellen der Zahl ein Programm schreiben, das etwa 50% dieser Stellen berechnen kann und nur die anderen 50% explizit enthalten muss (z.B. als interne Programmtabelle zum nachschauen). Wenn \(n\) sehr groß wird, so wird dieses Programm deutlich weniger als \(n\) Bit benötigen (z.B. \( n/2 + \log n \) ). Damit ist die Zahl zwar nicht-berechenbar, aber dennoch nicht zufällig, denn die Teilstrings der Länge \(n\) lassen sich deutlich komprimieren. Eine reelle Zahl könnte also höchstens dann zufällig sein, wenn sich nur sehr wenige (genauer: endlich viele) Stellen der Zahl berechnen lassen, die Zahl aber unendlich viele Stellen hinter dem Komma besitzt.
Ein erster Versuch, eine möglichst wenig berechenbare und damit möglichst zufällige Zahl zu definieren, ist der Folgende:
Wenn Turings Zahl beispielsweise gleich \( 0,100... \) wäre, dann würde das erste Programm in der Liste anhalten, das zweite und dritte nicht usw.. Dass man eine vollständige (unendlich lange) Liste aller Programme in einer vorgegebenen Programmiersprache aufstellen kann, wissen wir aus Kapitel 2.3 .
Turings Zahl ist nicht berechenbar, denn es gibt keinen allgemeinen Algorithmus, der für jedes Programm die Frage beantworten kann, ob das Programm irgendwann anhält oder nicht (Turings Halteproblem). Für gewisse Programme wird man die Frage beantworten können und damit die entsprechenden Binärstellen in Turings Zahl angeben können. Die Mehrzahl der Binärstellen bleibt jedoch unbestimmt.
Ist Turings Zahl bereits eine Zufallszahl, oder lässt sie sich komprimieren?
Um das herauszufinden, betrachten wir die ersten \(n\) Bit von Turings Zahl, also die Binärstellen \(b_1\) bis \(b_n\). Wenn wir herausfinden können, ob die Programme 1 bis \(n\) anhalten oder nicht, so können wir diese n Binärstellen angeben. Die Frage ist nun: wieviel Bit an Information benötigen wir, um herauszufinden, welche dieser Programme anhalten?
Die Programme einfach zu starten und abzuwarten, reicht nicht aus, denn wir können ohne weitere Information nie sicher sein, dass nicht eines der noch laufenden Programme irgendwann anhalten wird. Die Situation ändert sich aber, wenn uns jemand sagt, wieviele der \(n\) Programme anhalten. Nehmen wir also an, wir wissen, dass \(k\) der \(n\) Programme anhalten. Nun brauchen wir lediglich zu warten, bis entsprechend viele Programme tatsächlich angehalten haben, denn wir können sicher sein, dass kein weiteres anhalten wird. Dies wird nur eine endliche Zeit dauern, denn wir wissen ja, dass \(k\) Programme nach endlicher Zeit anhalten müssen (wobei diese Zeit natürlich trotzdem sehr lang sein kann). Sobald die \(k\) Programme angehalten haben, brauchen wir nur noch nachzusehen, welche Programme dies sind, und können damit die \(n\) Bit von Turings Zahl festlegen.
Diese Vorgehensweise können wir nun in ein Programm umsetzen. Das Programm muss zunächst die ersten \(n\) Programme einer vollständigen, unendlich langen Programmliste erzeugen und in einer internen Tabelle abspeichern. Wie so etwas geht, haben wir in Kapitel 2.3 bereits gesehen. Weiterhin muss das Programm über eine interne Laufzeitumgebung verfügen, mit der es die \(n\) Programme aus der Liste ablaufen lassen kann. Und schließlich muss das Programm wissen, wie viele der \(n\) Programme insgesamt anhalten. Dieses Wissen kann in dem Programm z.B. als interne Konstante vorgegeben werden. Damit kann das Programm die \(n\) Programme erzeugen, laufen lassen und anhalten, wenn die vorgegebene Zahl der \(n\) Programme angehalten haben, und somit die ersten n Bit von Turings Zahl ermitteln.
Wie lang ist nun dieses Programm? Es wird über einen konstanten (oder maximal logarithmisch mit \(n\) wachsenden) Teil verfügen: den Programmgenerator für die \(n\) Programme und die Laufzeitumgebung. Außerdem enthält es als Konstante die Zahl der \(n\) Programme, die anhalten. Diese Konstante benötigt nur maximal \( \log_2 n \) Bit Speicherplatz, denn die Konstante kann im Programm als Binärzahl angegeben werden.
Wenn wir nun genügend viele Binärstellen von Turings Zahl betrachten (d.h. wenn \(n\) sehr groß wird), so wird das obige Programm, das diese \(n\) Stellen ausgibt, deutlich kleiner als \(n\) Bit sein. Die Programmgröße wächst nur ungefähr logarithmisch mit \(n\). Das aber bedeutet, dass die ersten \(n\) Binärstellen von Turings Zahl keine Zufallszahl bilden, und damit ist auch Turings Zahl selbst keine Zufallszahl, denn sie kann komprimiert werden.
Die Informationen, ob die einzelnen Programme der vollständigen Programmliste anhalten oder nicht, sind demnach nicht unabhängig voneinander. Anders ausgedrückt: Die verschiedenen Instanzen des Halteproblems sind nicht unabhängig voneinander.
Wie also können wir Turings Zahl verdichten und so die Redundanzen aus ihr entfernen, um eine nicht-komprimierbare Zahl zu erhalten?
Die Kernidee dazu haben wir oben bereits kennengelernt: Um die ersten \(n\) Bit von Turings Zahl zu ermitteln, benötigt man die \( \log_2 n \) Bit an Information, wieviele der ersten \(n\) Programme anhalten. Diese Information ist dann möglicherweise nicht weiter komprimierbar. Wir müssen also die nicht-anhaltenden Programme zählen.
Damit diese Zahl nicht beliebig groß wird, je mehr Programme wir betrachten, müssen wir sie geeignet normieren. Die genaue Vorgehensweise ist folgende:
Statt der Liste aller Programme betrachten wir alle Binärstrings \(p\) einer gewissen Länge \(m\) (die Liste aller Binärstrings enthält ja auch alle Programme). Davon gibt es \( 2^m \) Stück.
Einige dieser Strings repräsentieren gültige Programme. Wir zählen nun alle diejenigen Programme darunter, die anhalten, und dividieren diese Anzahl durch die Gesamtzahl \( 2^m \) der betrachteten Binärstrings mit Länge \(m\). Diese Zahl ergibt dann gleichsam die Dichte der anhaltenden Programme unter den Binärstrings mit Bitlänge \(m\). Sie entspricht der Wahrscheinlichkeit (nennen wir sie \(P(m)\) ), dass ein willkürlich herausgegriffener Binärstring mit \(m\) Bit Länge ein anhaltendes Programm darstellt. Es ist also \begin{equation} P(m) = \sum_{p: \, |p| = m, \, U(p) \, \mathrm{hält}} \left( \frac{1}{2} \right)^{|p|} \end{equation} Die Summe \( \sum \) geht dabei über alle Binärstrings \(p\) der Länge \(m\) Bit, die ein anhaltendes Programm darstellen. Zur Notation: mit \( |p| \) bezeichnen wir die Länge des Binärstrings \(p\) in Bit, und mit \( U(p) \) bezeichnen wir den Computer, der den Binärstring \(p\) als Programm interpretiert und dieses Programm abarbeitet. Jeder Binärstring der Länge \(m\) Bit, der auf dem Computer \(U\) ein anhaltendes Programm darstellt, trägt also einen Summanden \( (1/2)^m \) zur Summe bei.
Nun gehen wir einen Schritt weiter: Wir greifen uns einen beliebigen Binärstring mit \(n\) Bit Länge heraus und fragen nach der Wahrscheinlichkeit (nennen wir sie \( \Omega_n \) ), dass irgendein Teilstring, der die ersten \(m\) Bit unseres \(n\)-Bit-Binärstrings umfasst, ein anhaltendes Programm darstellt. Dabei sind alle Werte von \( m = 1 \) bis \( m = n \) erlaubt, d.h. der Teilstring darf ein bis \(n\) Bit lang sein.
Zunächst einmal ist klar, dass maximal ein einziger Teilstring überhaupt ein Programm sein kann, denn wir hatten ja oben gesagt, dass keine Verlängerung eines Programm-Binärstrings ein Programm repräsentieren kann. Wir haben also verschiedene, einander ausschließende Alternativen: Entweder, das erste Zeichen ist bereits ein (anhaltendes) Programm, oder der Teilstring aus den ersten beiden Zeichen, oder der aus den ersten drei Zeichen, usw.. Jede dieser Alternativen tritt jeweils mit der Wahrscheinlichkeit \( P(m) \) ein. Die Regeln der Wahrscheinlichkeitsrechnung sagen nun, dass sich die einzelnen Wahrscheinlichkeiten \( P(m) \) für die einander ausschließenden Alternativen zur Gesamtwahrscheinlichkeit \( \Omega_n \) addieren, d.h. \begin{align} \Omega_n &= P(1) + P(2) + \, ... \, + P(n) = \\ & \\ &= \sum_{p: \, |p| \leq n, \, U(p) \, \mathrm{hält}} \left( \frac{1}{2} \right)^{|p|} \end{align} Angenommen, irgend jemand würde uns den Wert eines \( \Omega_n \) mitteilen. Was bedeutet das dann für die Lösung von Turings Halteproblems? \( \Omega_n \) war die Wahrscheinlichkeit, dass ein beliebiger \(n\)-Bit-Binärstring in seinen ersten \(m\) Bit ein anhaltendes Programm enthält (wobei \(m\) irgendeinen Wert von 1 bis \(n\) haben darf). Dabei kann der \(n\)-Bit-Binärstring nur höchstens ein anhaltendes Programm enthalten, denn Verlängerungen von Programmstrings sind keine Programme. \( \Omega_n \) ist also die Zahl der Binärstrings der Länge \(n\), die in ihren ersten \(m\) Bit ein anhaltendes Programm enthalten, dividiert durch die Gesamtzahl aller Binärstrings der Länge \(n\) (also \( 2^n \) ).
Nun ist aber die Zahl der Binärstrings der Länge \(n\) Bit, die in ihren ersten \(m\) Bit ein anhaltendes Programm enthalten, dasselbe wie die Zahl der anhaltenden Programm-Binärstrings mit einer Länge von maximal \(n\) Bit. \( \Omega_n \) ist gleich dieser Zahl, dividiert durch \( 2^n \). Daher ist die Zahl der anhaltenden Programm-Binärstrings mit einer Länge von maximal \(n\) Bit gleich \( \Omega_n \cdot 2^n \). Aus \( \Omega_n \) können wir also die Zahl der Programme ermitteln, die maximal \(n\) Bit aufweisen und die anhalten. Mit dem weiter oben beschriebenen Algorithmus können wir damit Turings Halteproblem für alle Programme mit maximal \(n\) Bit lösen:
Wir sehen also, dass \( \Omega_n \) sehr viele Informationen enthält, insbesondere bei großen Werten von \(n\).
Wir können die Wahrscheinlichkeit \( \Omega_n \) auch noch etwas anders veranschaulichen: Wir würfeln ein erstes Bit und fragen, ob dieser 1-Bit-String ein anhaltendes Programm ist. Falls nicht, würfeln wir ein zweites Bit dazu und fragen erneut, ob dieser 2-Bit-String ein anhaltendes Programm ist. Und so machen wir weiter, bis wir entweder beim \(n\)-ten Bit angekommen sind oder bis wir auf ein anhaltendes Programm gestoßen sind. Dann ist \( \Omega_n \) die Wahrscheinlichkeit, auf diese Weise in irgendeinem Schritt ein anhaltendes Programm (als Binärstring) zu erwürfeln.
Was passiert nun im Grenzfall, dass \(n\) gegen Unendlich strebt? Das bedeutet, dass wir ewig weitere Bits würfeln und damit den Binärstring beliebig verlängern dürfen. Wie groß ist die Wahrscheinlichkeit (nennen wir sie \( \Omega \), d.h. ohne den Index \(n\) ), auf diese Weise irgendwann einen Binärstring zu erzeugen, der einem anhaltenden Programm entspricht?
Die obige Formel für \( \Omega_n \) erlaubt es uns leicht, diesen Grenzfall zu beschreiben. Wir müssen nur die Summe über alle Binärstrings \(p\) laufen lassen und für jeden Binärstring, der einem anhaltenden Programm entspricht (d.h. \(U(p)\) hält), einen Summanden \( (1/2)^{|p|} \) hinzufügen (wobei \( |p| \) wieder die Länge des Binärstrings \(p\) ist): \begin{align} \Omega &= P(1) + P(2) + P(3) + \, ... \, = \\ & \\ &= \sum_{p: \, U(p) \, \mathrm{hält}} \left( \frac{1}{2} \right)^{|p|} \end{align} Man nennt diese Zahl zu Ehren ihres Entdeckers auch Chaitins Zahl.
Die obige Formel kann man sich sehr einfach veranschaulichen, denn sie zählt einfach nur die einzelnen Bits von \( \Omega \) hoch. Genauer tut sie folgendes:
Für jedes anhaltende Programm der Länge \(m\) Bit wird also das \(m\)-te Bit von \( \Omega \) um 1 hochgezählt (wobei wir \( \Omega \) natürlich als Binärstring schreiben, also z.B. \( \Omega = 0,0001011010001... \) ). Ist dieses Bit gleich \(0\), so wird also eine \(1\) daraus, und ist es schon gleich \(1\), so wird es wieder auf \(0\) gesetzt und das nächsthöhere Bit (also das \( (m - 1) \) -te Bit) wird um \(1\) hochgezählt. Im Prinzip kann daher ein anhaltendes Programm der Länge \(m\) neben dem \(m\)-ten Bit auch alle Bits von \( \Omega \) links vom \(m\)-ten Bit beeinflussen (je nachdem wieviele Überträge zu höheren Bits erforderlich sind). Daher hat ein einzelnes Bit von \( \Omega \) auch keine unmittelbare anschauliche Bedeutung, anders als bei Turings Zahl oben.
Man kann beweisen, dass \( \Omega \) einen Wert zwischen Null und Eins besitzt, so wie das bei einer Wahrscheinlichkeit sein muss. Die unendlich vielen Summanden ergeben zusammen also eine endliche Zahl (so etwas geht, wie beispielsweise die Summe \( 1/2 + 1/4 + 1/8 + 1/16 + \, ... \, \) zeigt). Es kann also vorkommen, dass man einen Binärstring ewig verlängert, ohne jemals ein anhaltendes Programm zu erzeugen. Dieser Fall wird sogar sehr häufig sein, denn wenn die ersten hundert Bit schon programmtechnischer Unsinn sind, wird das durch weitere Bit meistens nicht besser. Vermutlich ist \( \Omega \) also eine recht kleine Zahl.
Wie groß genau ist \( \Omega \) also? Kann man \( \Omega \) irgendwie berechnen?
Zunächst einmal hängt der Wert von \( \Omega \) natürlich von der verwendeten Programmiersprache ab, also davon, welche Binärstrings als Programme in Frage kommen. Also legen wir uns auf irgendeine Programmiersprache und Codierungsart fest (z.B. auf Turingprogramme).
Wenn wir die Definition von \( \Omega \) betrachten, so müssen wir leider feststellen, dass sich damit \( \Omega \) nicht berechnen lässt, denn dazu müssten wir Turings Halteproblem lösen, um zu bestimmen, wieviele Programme mit \(m\) Bit Länge jeweils anhalten (wie wir unten noch sehen werden, ist es jedoch möglich, endlich viele der ersten Bit von \( \Omega \) zu berechnen).
Es ist sogar noch schlimmer: \( \Omega \) ist nicht nur nicht-berechenbar – man kann beweisen, dass \( \Omega \) sogar eine Zufallszahl ist, d.h. \( \Omega \) ist nicht weiter komprimierbar! Wir werden uns diesen Beweis etwas weiter unten ansehen.
Es ist uns also gelungen, durch geschicktes Abzählen der anhaltenden Programme tatsächlich jede Redundanz aus Turings Zahl zu entfernen und eine neue Zahl zu definieren, die keine weitere Verdichtung mehr zulässt. Jedes einzelne Bit von \( \Omega \) ist vollkommen unabhängig von jedem anderen Bit. Anders ausgedrückt: \( \Omega \) ist die maximal verdichtete Information, die man über Turings Halteproblem angeben kann. Die einzelnen Bits verhalten sich so, als ob sie mit Hilfe einer Münze erwürfelt wurden. Es gibt keinerlei Struktur, die eine weitere Verdichtung ermöglichen würde.
\( \Omega \) enthält eine ungeheure Menge an Information, denn es gilt:
Ein analgoges Ergebnis hatten wir oben bereits für \( \Omega_n \) erhalten. Die Details sind hier allerdings etwas anders, denn \( \Omega_n \) ist wegen möglicher Bit-Überträge beim Aufsummieren nicht identisch mit den ersten \(n\) Bit von \( \Omega \).
Wir wollen uns ansehen, warum die ersten \(n\) Bit von \( \Omega \) das Halteproblem für alle Programme mit maximal \(n\) Bit lösen, und wie man diese Information aus \( \Omega \) gewinnen kann. Dazu definieren wir die folgenden Größen:
Wenn wir \(s\) gegen Unendlich gehen lassen, so werden schließlich alle Programme in \( \Omega^s \) berücksichtigt und \( \Omega^s \) wird gleich \( \Omega \) : \begin{equation} \lim \limits_ {s \to \infty} \Omega^s = \Omega \end{equation} Anders als \( \Omega \) ist jedes \( \Omega^s \) berechenbar, denn wir müssen ja nur alle Programme mit maximal \(s\) Bit Länge bis zu \(s\) Schritte lang laufen lassen und die bis dahin anhaltenden Programme in der Summe berücksichtigen. Die Folge der \( \Omega^s \) bildet damit eine mit \(s\) anwachsende Folge von berechenbaren rationalen Zahlen, die gegen die nicht berechenbare reelle Zahl \( \Omega \) konvergiert. Wegen dieser Eigenschaft bezeichnet man \( \Omega \) auch als eine rekursiv aufzählbare reelle Zahl. Dieses Ergebnis werden wir weiter unten in anderem Zusammenhang noch einmal benötigen.
Es ist bemerkenswert, dass man jedes einzelne \( \Omega^s \) berechnen kann, aber die Konvergenz zu \( \Omega \) nicht berechenbar ist. Man kann die Folge der \( \Omega^s \) nicht dazu verwenden, um eine Rechenvorschrift zur Berechnung vom \( \Omega \) abzuleiten, denn egal wie groß man \(s\) auch wählt, so weiß man dennoch beispielsweise nie, wie viele der kürzeren anhaltenden Programme in der Summe noch fehlen (sie haben ja evtl. nur bisher in \(s\) Schritten noch nicht angehalten). Diese kürzeren anhaltenden Programme können, wenn sie erst spät anhalten, auch bei großem \(s\) die vorderen Bits noch ändern (es wird ja immer das \(n\)-te Bit hochgezählt, das der Programmlänge \(n\) entspricht). Zudem könnten theoretisch auch große Gruppen längerer Programme über Bitüberträge die vorderen Bits von \( \Omega \) verändern. Schauen wir uns das noch etwas genauer an:
Nehmen wir konkret ein Programm mit der Läge \(m\). Wenn dieses Programm anhält und damit zur Summe beiträgt, so wird die Summe um den Term \( (1/2)^m \) hochgezählt, d.h. das \(m\)-te Bit hinter dem Komma wird um Eins hochgezählt. Das kann einen Übertrag zu den davorliegenden Bits auslösen. Niemals jedoch kann ein Programm mit Länge \(m\) ein Bit rechts von der \(m\)-ten Binärstelle beeinflussen.
Für \( \Omega^s \) bedeutet das, dass dessen Binärdarstellung höchstens \(s\) Binärstellen hinter dem Komma besitzt, denn wir lassen ja hier maximal Programme bis Länge \(s\) für bis zu \(s\) Schritte laufen.
Wenn wir \( s = n \) setzen und die Summe \( \Omega^s = \Omega^n \) mit \( \Omega(n) \) vergleichen (also mit den ersten \(n\) Binärstellen von \( \Omega \) hinter dem Komma), dann muss deshalb \( \Omega^s = \Omega^n \leq \Omega(n) \) sein. Schließlich enthält \( \Omega(n) \) (anders als \( \Omega^n \) ) zusätzlich noch mögliche Überträge von längeren Programmen auf die ersten \(n\) Bit von \( \Omega \) sowie die Beiträge länger als \(n\) Schritte laufender Programme.
Was passiert nun, wenn wir \(s\) schrittweise größer als das vorgegebenes \(n\) machen? Dann werden mehr und mehr Programme zu \( \Omega^s \) beitragen, und \( \Omega^s \) wird sich immer mehr an \( \Omega \) annähern (wobei niemand weiß, wie schnell). Irgendwann wird das berechnete \( \Omega^s \) größer als \( \Omega(n) \) werden, denn \( \Omega(n) \) umfasst ja nur die ersten \(n\) Binärstellen von \( \Omega \) und ist damit kleiner als \( \Omega \) (wir setzen voraus, dass \( \Omega \) unendlich viele Binärstellen hat, da es anhaltende Programme mit beliebig großer Länge gibt). Auf diese Weise können wir also eine Zahl \(s\) oberhalb von \(n\) bestimmen, so dass \( \Omega^s > \Omega(n) \) wird.
Dies ermöglicht es uns nun, anzugeben, wie viele Schritte ein anhaltendes Programm mit \(n\) Bit Länge maximal laufen kann, bis es anhält: Es läuft maximal \(s\) Schritte, wenn \(s\) wie oben so gewählt wurde, dass \( \Omega^s > \Omega(n) \) ist (automatisch ist dann auch \(s \geq n \) ). Die Begründung dafür lautet so:
Angenommen, ein \(n\)-Bit-Programm würde mehr als \(s\) Schritte benötigen, um anzuhalten. Dann würde dieses Programm einen Beitrag \( (1/2)^n \) zur vollständigen \( \Omega \)-Summe liefern, aber keinen Beitrag zur Teilsumme \( \Omega^s \). Die \( \Omega \)-Summe enthält also den Term \( (1/2)^n \), die \( \Omega^s \)-Summe nicht. Wenn wir diesen Term zur \( \Omega^s \)-Summe hinzufügen, rückt diese Teilsumme näher an die volle Summe \( \Omega \) heran, kann aber nicht größer als \( \Omega \) werden, da im Normalfall auch noch andere Summanden fehlen. Es gilt also \( \Omega \geq \Omega^s + (1/2)^n \) .
Und weil \(s\) so gewählt wurde, dass \( \Omega^s > \Omega(n) \) ist, muss auch \( \Omega > \Omega(n) + (1/2)^n \) sein. Das aber kann nicht sein, denn würde man zu den ersten \(n\) Bit von \( \Omega \) (also zu \( \Omega(n) \) ) den Term \( (1/2)^n \) hinzuaddieren (also das \(n\)-te Bit um 1 erhöhen), so ist die resultierende Zahl größer als \( \Omega \), d.h. es gilt immer \( \Omega < \Omega(n) + (1/2)^n \) . Also ist unsere Annahme falsch! Jedes anhaltende Programm mit \(n\) Bit Länge muss in maximal \(s\) Schritten anhalten. Im Grunde haben wir durch die Bedingung \( \Omega^s > \Omega(n) \) den Wert von \(s\) gerade entsprechend gewählt.
Wie sieht es mit den kürzeren Programmen (sagen wir, mit Länge \(m\) ) aus? Da \( \Omega(n) \geq \Omega(m) \) ist für \(n > m\), gilt für das oben ermittelte \(s\) auch \( \Omega^s > \Omega(m) \). Wir können daher im obigen Beweis überall \(n\) durch \(m\) ersetzen und damit nachweisen, dass auch die kürzeren Programme in maximal \(s\) Schritten anhalten müssen, wenn sie denn jemals anhalten.
Man kann sich diese Argumentation auch ganz anschaulich so vorstellen: Wenn wir \(s\) hochzählen, dann werden immer mehr anhaltende Programme in der \( \Omega^s \)-Summe berücksichtigt, die immer größer wird. Dabei stabilisieren sich nach und nach von links nach rechts immer mehr der vorderen Bits hinter dem Komma. Wenn diese Bits nämlich erst einmal den Bits der vollen Summe \( \Omega \) entsprechen, können sie nicht noch weiter hochgezählt werden, denn sonst würde die \( \Omega^s \)-Teilsumme größer als die volle Summe \( \Omega \) werden. Sobald die \( \Omega^s \)-Teilsumme größer als \( \Omega(n) \) wird, sind diese ersten \(n\) Bits in \( \Omega^s \) stabil (nämlich gleich \( \Omega(n) \) ) und werden bei weiter wachsendem \(s\) durch weitere hinzukommende Programme nicht mehr geändert. Damit kann sich aber auch kein Programm mit \( \leq n\) Bit Länge noch verspätet als anhaltendes Programm entpuppen, denn das würde ja eines der vorderen \(n\) Bit noch ändern. Alle anhaltenden Programme mit \( \leq n\) Bit Länge müssen bereits (also innerhalb der vollzogenen \(s\) Schritte) angehalten haben.
Ein Beispiel: Angenommen, wir wüssten, dass die ersten drei Stellen von \( \Omega \) so aussehen: \( \Omega(3) = 0,101 \), d.h. \( \Omega = 0,101... \) . Wenn wir \(s\) hochzählen, könnte sich die Teilsumme \( \Omega^s \) so entwickeln: \begin{align} \Omega^1 &= 0,0 \\ \Omega^2 &= 0,01 \\ \Omega^3 &= 0,011 \\ \Omega^4 &= 0,100 \\ \Omega^5 &= 0,101 \\ \Omega^6 &= 0,1011 \\ ... \end{align}
In Schritt fünf mit \( s = 5 \) haben sich die ersten drei Bits stabilisiert, denn sie entsprechen den ersten drei Bits von \( \Omega \). Sie werden sich also im weiteren Verlauf nicht mehr ändern, wenn die Teilsumme \( \Omega^s \) weiter anwächst, denn diese nähert sich ja von unten immer mehr der vollen Summe \( \Omega \). Daher kann ab Schritt fünf auch kein Programm mit maximal drei Bits Länge mehr hinzukommen (also in mehr als 5 Programmschritten anhalten), denn das würde eines dieser ersten drei Bits weiter hochzählen (ein Programm zählt ja immer dasjenige Bit hoch, das seiner Programmlänge entspricht). Die Teilsumme \( \Omega^s \) würde damit größer als die volle Summe \( \Omega \) werden.
Unser Ergebnis lautet also:
Was aber nützt es, das Halteproblem für alle Programme bis \(n\) Bit Länge gelöst zu haben? Ist das für irgend etwas nützlich?
Die Antwort auf diese Frage lautet: Für genügend große Werte von \(n\) ist diese Information sogar extrem nützlich – zumindest im Prinzip!
Ein Beispiel dazu (siehe z.B. G.J.Chaitin: META-MATHEMATICS AND THE FOUNDATIONS OF MATHEMATICS): Es gibt ein berühmtes, immer noch ungelöstes Problem in der Zahlentheorie, das den Namen Riemannsche Hypothese trägt. Diese Hypothese besagt, dass die interessanten Nullstellen einer bestimmten Funktion sich alle entlang einer bestimmten Geraden in der komplexen Ebene befinden (Details folgen in einem späteren Kapitel). Die Hypothese hat sich als sehr fruchtbar erwiesen und wurde mit Computerhilfe an sehr vielen Nullstellen getestet. Ein Beweis ist jedoch bisher nicht gelungen, und keiner weiß, ob es überhaupt einen Beweis gibt. Leider gibt es unendlich viele interessante Nullstellen, so dass man sie nicht alle überprüfen kann. Ein Programm kann sie lediglich eine nach der anderen überprüfen. Sollte das Programm jemals eine Nullstelle finden, die sich nicht auf der Geraden befindet, so könnte man es so einrichten, dass dieses Programm diese Nullstelle ausgibt und anhält – die Riemannsche Hypothese wäre damit widerlegt und ein Gegenbeispiel gefunden.
Wir wollen die Bitlänge dieses Programms mit \(n\) bezeichnen. Angenommen, die ersten \(n\) Binärstellen von \( \Omega \) wären uns bekannt. Dann könnten wir eine Zahl \(s\) oberhalb von \(n\) bestimmen, so dass das Programm innerhalb von \(s\) Schritten anhalten muss, wenn es überhaupt anhält. Nun brauchen wir das Programm nur noch \(s\) Schritte lang laufen zu lassen. Entweder, es hat bis dahin ein Gegenbeispiel zur Riemannschen Hypothese gefunden, oder es wird nie eines finden. Die Riemannsche Hypothese wäre damit entweder bewiesen oder widerlegt.
Wir können den Informationsgehalt der ersten \(n\) Bit von \( \Omega \) mit der Größe formaler Systeme vergleichen. Wie im letzten Kapitel fassen wir dabei ein formales System als ein Programm auf, das alle Regeln und Axiome des formalen Systems enthält und damit die vollständige Liste aller Beweise, die in diesem System möglich sind, der Größe nach alphabetisch geordnet beliebig weit ausgeben kann. Die Bitgröße (nennen wir sie \(n\) ) dieses Programms fassen wir als Größe des formalen Systems auf.
Wir können nun dieses Programm etwas erweitern (sagen wir, um \(k\) Bit) und nach dem Beweis für eine wohlgeformte Aussage (nennen wir sie \(A\) ) suchen. Dazu erzeugt das Programm einfach einen Beweis nach dem anderen und überprüft, ob es sich um einen Beweis für \(A\) handelt. Wenn ja, gibt das Programm den Beweis aus und hält an. Falls nein, sucht das Programm weiter.
Die Größe dieses Programms ist \(n + k\), wobei \(k\) bei umfangreichen formalen Systemen (z.B. Peano-Arithmetik) sehr viel kleiner als \(n\) ist. Nehmen wir nun an, die ersten \(n + k\) Binärstellen von \( \Omega \) wären bekannt. Dann könnten wir wie oben entscheiden, ob das Programm jemals anhält und einen Beweis findet oder nicht. Wir hätten damit ein Entscheidungsverfahren für alle wohlgeformten Aussagen des formalen Systems gefunden (siehe Kapitel 2.2). Wir sehen also, welche Fülle an Informationen in \( \Omega \) verschlüsselt sind. Die ersten \(n + k\) Bit ermöglichen es im Prinzip, für alle wohlgeformten Aussagen eines formalen Systems anzugeben, ob sie innerhalb des Systems beweisbar sind, widerlegbar sind oder keines von Beidem. Dies ist der Grund, weshalb Chaitins \( \Omega \) auch gelegentlich die Zahl der Weisheit genannt wird.
Nun wissen wir andererseits aus Kapitel 2.4, dass es innerhalb eines hinreichend mächtigen formalen Systems (d.h. das alle berechenbaren Funktionen der natürlichen Zahlen darstellen kann) kein Entscheidungsverfahren geben kann (Widerspruchsfreiheit vorausgesetzt). Daraus folgt wiederum, dass man innerhalb dieses formalen Systems nicht \(n + k\) Binärstellen von \( \Omega \) berechnen kann, denn sonst hätte man ja das Entscheidungsverfahren. Da \(k\) viel kleiner als \(n\) ist, kann man auch sagen:
Aussagen wie "das \(2 \cdot n\) -te Bit von \( \Omega \) ist \(1\)" sind daher innerhalb eines \(n\)-Bit großen formalen Systems werder beweisbar noch widerlegbar – eine weitere Spielart von Gödels Unvollständigleitssatz.
Um mehr als etwa \(n\) Bit von \( \Omega \) zu berechnen, benötigt man demnach entsprechend größere und mächtigere formale Systeme. Anders ausgedrückt: es sind weitere Axiome notwendig. Man muss mehr Information in Form von Axiomen in das formale System hineinstecken, um mehr Informationen (in Form von weiteren \( \Omega \)-Bits) herauszubekommen. Man kann sich leicht vorstellen, wie ein umfangreicheres formales System ein Entscheidungsverfahren für ein kleineres formales System (z.B. die Euklidische Geometrie) bereitstellen kann. In einem größeren formalen System sind mehr Aussagen beweisbar oder widerlegbar als in einem kleineren formalen System – entsprechend können auch mehr Bits von \( \Omega \) berechnet werden. So sind mit Hilfe der Mengenlehre Aussagen über natürliche Zahlen beweisbar, die innerhalb der Peano-Arithmetik nicht entscheidbar sind (z.B. die Widerspruchsfreiheit der Peano-Arithmetik).
Man kann \( \Omega \) als die bestmögliche Kompression der Information darüber ansehen, welche Aussagen entscheidbar sind und welche nicht. Dabei hängt es vom formalen System und von der betrachteten Programmiersprache ab, welche Aussagen beweisbar sind und wie die einzelnen Bits von \( \Omega \) aussehen. Wir werden unten noch sehen, dass es unendlich viele verschiedene \( \Omega \)s gibt!
Allgemein muss man zur Berechnung der ersten \( \Omega \)-Bits erst einmal über alle Informationen verfügen, die in diese Bits hineinkomprimiert werden. Man muss also wissen, ob die entsprechenden Programme anhalten oder nicht, bzw. ob die entsprechenden Aussagen beweisbar sind. Die ersten Bits von \( \Omega \) zu berechnen bedeutet also, das gesamte in diesen Bits komprimierte Wissen erst einmal zusammenzutragen. Man kann sich vorstellen, dass das immer schwieriger wird, je mehr Bits von \( \Omega \) wir ermitteln wollen. Genau deshalb gibt es auch keinen Algorithmus, der beliebig viele Bits von \( \Omega \) ermitteln kann – \( \Omega \) ist nicht berechenbar.
Man zahlt nun einen Preis für diese extreme Kompression mathematischer Information. Es ist extrem aufwendig, sie aus \( \Omega \) wieder herauszuholen. Die Kompression der Information ist gleichzeitig eine sehr gute Verschlüsselung dieser Information (es ist sogar die bestmögliche Verschlüsselung). Das hat folgenden Grund:
Um das Halteproblem für die Programme mit maximal \(n\) Bit Größe mit Hilfe der ersten \(n\) Bit von \( \Omega \) zu lösen, muss man die maximale Anzahl Schritte \(s\) ermitteln, innerhalb derer jedes dieser Programme anhält. Wie das geht, haben wir oben bereits gesehen: Man muss \(s\) von \(n\) ausgehend schrittweise solange vergrößern, bis \( \Omega^s > \Omega(n) \) wird. Dazu muss man beim Vergrößern von \(s\) (also beim Schritt von \(s-1\) nach \(s\)) folgendes tun: Man muss alle bisher getesteten Programme (Programme, die \(s-1\) Bit lang sind und die noch nicht angehalten haben), einen Schritt weiterlaufen lassen und nachsehen, ob sie jetzt anhalten. Außerdem muss man alle neu hinzugekommenen Programme mit \(s\) Bit Länge \(s\) Schritte lang laufen lassen, um zu sehen, ob sie anhalten. Damit kann man den Wert von \( \Omega^s \) ermitteln und nachprüfen, ob er größer als die ersten \(n\) Binärstellen von \( \Omega \) (also größer als \( \Omega(n) \) ) ist. Falls er das nicht ist, vergrößert man \(s\) wieder um \(1\) und wiederholt die Prozedur.
Bei großen Werten von \(s\) wird dieser Algorithmus sehr schnell extrem langsam, denn es kommen immer mehr zu testende Programme hinzu (der Zuwachs wächst exponentiell mit \(s\) ), die man über immer mehr Schritte testen muss, ob sie anhalten. Insgesamt muss man genügend viele Programme über genügend lange Zeit testen, um die ersten \(n\) Bit von \( \Omega \) korrekt zu reproduzieren (genau das bedeutet \( \Omega^s > \Omega(n) \) ). Wann dieser Punkt erreicht ist, weiß man allerdings nur, wenn man die ersten \(n\) Bit von \( \Omega \) bereits kennt (wir erinnern uns: die Konvergenz von \( \Omega^s \) gegen \( \Omega \) ist nicht berechenbar, d.h. man weiß nie, wie nahe man dem Wert von \( \Omega \) bereits gekommen ist; deshalb ist die Ermittlung der ersten \(n\) Bit von \( \Omega \) noch viel schwieriger als die Ermittlung von \(s\), bei der man diese Bits ja schon vorher kennen muss).
Anders ausgedrückt: Wenn man \( \Omega(n) \) noch nicht kennt, muss man zur Ermittlung von \(s\) alle Programme bis \(s\) Bit Größe solange laufen lassen, bis alle anhaltenden Programme mit maximal \(n\) Bit Größe ( \(n \leq s \) ) angehalten haben (sodass man \( \Omega(n) \) kennt). Dabei muss man \(s\) (und damit die Zahl der zu testenden Programme, die exponentiell mit \(s\) zunimmt) umso größer machen, je mehr Schritte man die Programme laufen lässt. Dass alle Programme mit maximal \(n\) Bit Größe, die überhaupt anhalten, auch angehalten haben, sieht man an \( \Omega^s > \Omega(n) \).
Den Aufwand, der zum Extrahieren der Information aus \( \Omega \) notwendig ist, wird durch die folgende beweisbare Aussage besonders deutlich:
(siehe z.B. C.S.Calude, M.J.Dinneen, Chi-Kou Shu: Computing A Glimpse of Randomness). Das ist nicht mehr zu überbieten! In der Praxis ist die Information in \( \Omega \) also letztlich unbrauchbar. Sie ist so dicht komprimiert, dass die Dekompression viel zu aufwendig ist. Die Kompression der Halte-Information in \( \Omega \) wirkt also wie eine Verschlüsselung, die kaum zu knacken ist – es ist die bestmögliche Verschlüsselung überhaupt!.
Oben hatten bereits erwähnt, dass \( \Omega \) eine Zufallszahl (also nicht weiter komprimierbar) ist. Nun sind wir gerüstet, den Grund dafür zu verstehen:
Wir haben oben gesehen, dass man das Halteproblem für alle Programme mit Längen bis \(n\) Bit lösen kann, wenn die ersten \(n\) Binärstellen von \( \Omega \) (also \( \Omega(n) \) ) bekannt sind. Wir schreiben nun ein Programm (nennen wir es \(P\)), das \( \Omega(n) \) als Konstante enthält und das folgenden Algorithmus ausführt:
Programm P:
Damit haben wir ein Programm \(P\) geschrieben, das irgendwann eine Zahl \(x\) ausgibt, die eine Komplexität größer als \(n\) haben muss, denn kein Programm mit maximal \(n\) Bit kann diese Zahl ausgeben (genau das hat das Programm ja überprüft). Eine solche Zahl muss es geben, denn für große \(n\) sind die meisten Zahlen Zufallszahlen. Bezeichnen wir die Komplexität von \(x\) mit \(H(x)\), so gilt also \( H(x) > n \) .
Andererseits kann die Komplexität von \(x\) nicht größer sein als die Länge \(|P|\) des Programms \(P\), denn \(P\) gibt \(x\) ja aus: \[ H(x) \leq |P| \] Wie lang ist nun das kürzeste Programm \(P\), das den obigen Algorithmus durchführt? Es besteht aus der obigen Schleife, die eine konstante Anzahl Bit benötigt, sowie aus der vorgegebenen Konstante \( \Omega(n) \), die in der kürzest möglichen Form gerade soviel Speicherplatz benötigt, wie es ihrer Komplexität \(H(\Omega(n))\) entspricht. Also ist \[ |P| = H(\Omega(n)) + c \] wobei \(c\) eine konstante Zahl ist, die nicht von \(n\) abhängt. Damit haben wir \[ H(x) \leq |P| = H(\Omega(n)) + c \] Weil aber zusätzlich auch \( H(x) > n \) ist (siehe oben), folgt \( n < |P| = H(\Omega(n)) + c \) , oder etwas anders geschrieben: \[ H(\Omega(n)) > n - c \] Dies entspricht genau der Definition einer unendlich langen Zufallszahl aus dem vorherigen Kapitel, denn es gibt eine maximale Abweichung \(c\) zwischen der Komplexität der ersten \(n\) Binärstellen von \( \Omega \) und der Stellenzahl \(n\). Für große Stellenzahlen \(n\) fällt daher \(c\) kaum noch ins Gewicht, und die Komplexität der ersten \(n\) Stellen von \( \Omega \) entspricht ungefähr der Stellenzahl \(n\) selbst. \( \Omega \) ist damit nicht kompressibel und somit zufällig.
Die obige Überlegung zeigt sehr gut, woran es liegt, dass Turings Halteproblem unlösbar ist. Die einzige Information, die wir über Turings Halteproblem in das Programm \(P\) hineingesteckt haben, ist \( \Omega(n) \). Wir können deren Komplexität \( H(\Omega(n)) \) als die kürzest mögliche Informationsmenge ansehen, die wir in das Programm \(P\) hineinstecken müssen, um das Halteproblem für die Programme bis \(n\) Bit Länge zu lösen.
Die Stellenanzahl \(n\) von \( \Omega(n) \) repräsentiert letztlich die Informationsmenge, die wir hineinstecken müssen, um das Halteproblem für alle Programme mit Maximallänge \(n\) zu lösen. Diese notwendige Informationsmenge wächst also linear mit der Maximalgröße \(n\) der betrachteten Programme.
Daher kann es keinen allgemeinen Algorithmus geben, der ein beliebiges \(n\) als Konstante enthält (entsprechend einem Informationsgehalt von höchstens \( \log_2 n \) Bit) und der das Halteproblem für alle Programme bis \(n\) Bit Größe löst, denn dieser Algorithmus hätte eine Größe von \( \log_2 n + d \) Bit (wobei \(d\) eine Konstante ist). Für die Lösung des Halteproblems bis \(n\) Bit Programmlänge benötigt man aber \(n - c\) Bit. Ab einer gewissen maximalen Programmlänge \(n\) wird also jeder Algorithmus überfordert sein.
Letztlich ist genau das auch der Grund für die Unvollständigkeit hinreichend mächtiger formaler mathematischer Systeme, und damit für Gödels Satz. Die mathematischen Aussagen können wir uns dabei als Programme vorstellen, die nach Gegenbeispielen zu diesen Aussagen suchen und anhalten, wenn ein Gegenbeispiel gefunden wurde. Könnte man das Halteproblem für diese Programme lösen, so wären damit zugleich die entsprechenden mathematischen Aussagen entschieden. Doch zum Lösen des Halteproblems bis zu \(n\) Bit Programmlänge benötigen wir auch ungefähr \(n\) Bit an Information (die Konstante \(c\) lassen wir einfach unter den Tisch fallen, da sie bei großen \(n\) keine Rolle mehr spielt). Die in einem formalen System enthaltene Information ist aber begrenzt – sie entspricht ungefähr der Größe eines Programms, das alle Beweise des Systems auflisten kann (siehe oben). Aus dieser Perspektive erscheint es selbstverständlich, dass es eine Grenze gibt, ab der die Probleme so kompliziert (und die zugehörigen Testprogramme so lang) werden, dass die Information des formalen Systems nicht mehr ausreicht, sie zu lösen.
Es ist interessant, sich einmal anzusehen, was passiert, wenn wir statt Chaitins \( \Omega \) versuchen, Turings Zahl (nennen wir sie \(T\)) in diesem Beweis zu verwenden. Turings Zahl hatten wir oben bereits definiert: das \(k\)-te Bit dieser Zahl gibt an, ob das \(k\)-te Programm anhält oder nicht. Um das Halteproblem für alle Programme mit Maximalgröße \(n\) Bit zu lösen, benötigen wir allerdings (zumindest bei größeren \(n\)) mehr als nur \(n\) Stellen von Turings Zahl, denn die Zahl der Programme mit maximal \(n\) Bit wächst exponentiell mit deren Maximallänge \(n\). Wir können also grob davon ausgehen, dass die Zahl Zahl der Programme mit maximal \(n\) Bit sich ungefähr wie \(a^n\) verhält, wobei \(a\) irgendeine Zahl größer als \(1\) ist. Also brauchen wir auch die ersten \(a^n\) Stellen von Turings Zahl \(T\) (was wir als \( T(a^n) \) schreiben wollen ), um das Halteproblem für diese Programme zu lösen.
Statt \( \Omega(n) \) müssten wir also in der obigen Überlegung dieses \( T(a^n) \) verwenden. Unser Ergebnis wäre dann \( H(T(a^n)) > n - c \). Wenn wir noch die Stellenzahl (gleich Programmzahl) \(a^n\) als \(m\) schreiben (also \( m = a^n \) und somit \( n = \log_a m \) ), dann haben wir \( H(T(m)) > \log_a m - c \). Die obige Überlegung würde daher nur ergeben, dass die Komplexität der ersten \(m\) Stellen von Turings Zahl mindestens logarithmisch mit der Stellenzahl \(m\) zunimmt. Dies passt sehr gut zu unserem Ergebnis weiter oben, dass Turings Zahl komprimiert werden kann.
Wie eng \( \Omega \) mit der Lösbarkeit mathematischer Probleme verknüpft sein kann, zeigt folgendes Beispiel:
Im Jahr 1970 untersuchten J.P.Jones und Y.V.Matijasevic sogenannte Diophantische Gleichung, die einen ganzzahligen Parameter \(k\) besitzen. Diophantische Gleichungen sind nach dem griechischen Mathematiker Diophantos von Alexandrien aus dem 3ten Jahrhundert benannt. Sie enthalten nur Multiplikationen, Additionen und Exponentieren von ganzen Zahlen und ganzzahligen Variablen. Ein Beispiel für eine solche Gleichung ist \begin{equation} x^3 + k y^2 = 5 z^4 \end{equation} Gesucht sind bei vorgegebenem ganzzahligem \(k\) (beispielsweise \(k = 3 \) ) ganzzahlige Lösungen für die Variablen \(x, y\) und \(z\).
Jones und Matijasevic fanden eine Methode, Programme einer vorgegebenen Programmiersprache in eine Familie von Diophantischen Gleichungen zu übersetzen, wobei sich die einzelnen Gleichungen nur durch verschiedene Werte des darin enthaltenen Parameters \(k\) unterscheiden. Wenn nun ein bestimmtes Programm (sagen wir, das \(15\)-te) nicht anhält, so hat die Diophantische Gleichung mit Parameterwert \(k = 15\) keine ganzzahligen Lösungen. Wenn das Programm dagegen anhält, dann hat Gleichung genau eine Lösung. Die Umkehrung gilt ebenfalls. Details dazu folgen in einem späteren Kapitel.
G.Chaitin hat diese Methode abgewandelt und eine Methode gefunden, die ein LISP-Programm zur Berechnung der \(k\)-ten Binärstelle von \( \Omega_n \) umwandelt in eine Diophantische Gleichung mit Parametern \(n\) und \(k\). Die Gleichung kann mit Hilfe eines Computerprogramms erzeugt werden. Sie ist etwa 200 Seiten lang und enthält etwa 17000 nicht-negative ganzzahlige Variablen. Für irgendwelche vorgegebenen Werte von \(n\) und \(k\) hat die Gleichung genau dann genau eine Lösung, wenn das \(k\)-te Bit von \( \Omega_n \) gleich \(1\) ist. Ist das Bit gleich \(0\), so hat die Gleichung keine Lösung.
Man kann nun \(k\) festhalten und \(n\) größer werden lassen. Anfangs wird das \(k\)-te Bit von \( \Omega_n \) mit wachsendem \(n\) sich immer mal wieder verändern. Doch für genügend große Werte von \(n\) wird es sich stabilisieren, denn \( \Omega_n \) konvergiert ja gegen \( \Omega \). Betrachtet man \(n\) nicht als extern vorgegebenen Parameter, sondern als Variable der Gleichung (die Diophantische Gleichung wird dadurch zu einer exponentiell-Diophantischen Gleichung, weil nun auch Variablen im Exponenten vorkommen), so hat die Gleichung demnach unendlich viele Lösungen für dieses \(k\), wenn das \(k\)-te Bit von \( \Omega \) gleich \(1\) ist, und nur endlich viele (oder gar keine) Lösungen, wenn das \(k\)-te Bit von \( \Omega \) gleich \(0\) ist.
Nun sind die einzelnen Bits von \( \Omega \) vollkommen unabhängig voneinander, denn \( \Omega \) ist eine Zufallszahl. Das bedeutet, dass die mathematische Aussage, ob die obige Gleichung endlich oder unendlich viele Lösungen für einen Wert von \(k\) hat, vollkommen unabhängig ist von der entsprechenden Aussage für einen anderen Wert von k. Die Aussagen sind logisch nicht miteinandner verknüpft. Ein Mathematiker, dem es mit Hilfe von bestimmten Axiomen über die natürlichen Zahlen gelingt, die Antworten für bestimmte Werte von \(k\) zu finden, hat dennoch keinen Anhaltspunkt darüber, ob die Gleichung für andere Wert von \(k\) endlich oder unendlich viele Lösungen hat. Da in einem \(n\)-Bit-formalen-System nur höchstens etwa \(n\) Binärstellen von \( \Omega \) überhaupt berechnet werden können, ist die Frage aufgrund der Axiome des formalen Systems generell nur für endlich viele Werte von \(k\) entscheidbar, und keine mathematische Methode kann ohne neue Axiome die Frage für weitere Werte von \(k\) entscheiden. Die beiden Alternativen, dass Chaitins Gleichung für einen dieser Werte von \(k\) endlich oder unendlich viele Lösungen hat, sind wie zwei zusätzliche Axiome, von denen eines dem formalen System hinzugefügt werden kann, denn es handelt sich um eine Zusatzinformation, die bisher im System nicht enthalten ist. Dies entspricht Gödels Unvollständigkeitssatz.
Eine andere Sichtweise ist folgende: Da die einzelnen Bits von \( \Omega \) sich wie die Bits einer Zufallszahl verhalten, hat auch die Gleichung für verschiedene Werte von \(k\) wie zufällig mal endlich viele Lösungen, mal unendlich viele Lösungen. In diesem Sinn kann man sagen, dass die Mathematik hier ein zufälliges Verhalten aufweist, sogar in einem Bereich, der sich nur mit den natürlichen Zahlen befasst. Mathematisches Schlussfolgern ist in diesem Bereich weitgehend nutzlos. Es gibt sogar verschiedene Möglichkeiten, \( \Omega_n \) in Gleichungen zu übersetzen. Außerdem gibt es unendlich viele verschiedene \( \Omega \)s, da \( \Omega \) von der gewählten Computersprache abhängt. Es gibt also ganze Bereiche, in denen die Mathematik ein zufälliges Verhalten aufweist.
Da \( \Omega \) eine nicht berechenbare Zufallszahl ist, ist es schwierig, wenigstens die ersten Bits dieser Zahl zu berechnen. Zur Erinnerung: Nicht-berechenbar heißt, dass nicht alle Bits durch einen einzigen Algorithmus berechnet werden können. Wir hatten oben allerdings gesehen, dass in einem \(n\)-Bit-formalen System nur höchstens etwa \(n\) Binärstellen überhaupt berechnet werden können. Jedes Verfahren zur Berechnung von \( \Omega \) bleibt daher auf endlich viele Binärstellen beschränkt, d.h. es gibt kein skalierbares Rechenverfahren.
Trotz dieser Schwierigkeiten gelang es im Jahr 2002 tatsächlich, die ersten 64 Bits von Chaitins originalem \( \Omega \) (entsprechend seiner Wahl einer bestimmten Computersprache) zu berechnen (siehe C.S.Calude, M.J.Dinneen, Chi-Kou Shu: Computing A Glimpse of Randomness). Dazu überprüften Calude, Dineen und Shu in der gewählten Programmiersprache für alle Programme mit einer Maximallänge von 84 Bit, ob diese anhalten oder nicht. Diese Überprüfung bestand in einer genauen Analyse der Programme und dem Aufdecken von Ähnlichkeiten unter den Programmen. Außerdem musste noch untersucht werden, wie weit längere, nicht untersuchte Programme die ersten Bit von \( \Omega \) beeinflussen könnten. So konnte sichergestellt werden, dass die Analyse aller Programme mit maximal 84 Bit ausreicht, die ersten 64 Bit von Chaitins \( \Omega \) zu bestimmen. Hier ist das Ergebnis in Binärform:
\( \Omega = \) 0,0000001000000100000110001000011010001111110010111011101000010000...
Man sieht, dass die Zahl tatsächlich recht klein ist. Sie ist ungefähr gleich \(1/128\), also etwa \(0,78\) %. Die Wahrscheinlichkeit, durch ewiges Verlängern eines Bitstrings mit zufälligen Bits irgendwann ein anhaltendes Programm zu erzeugen, ist also in der gewählten Programmiersprache kleiner als ein Prozent.
Der Wert von \( \Omega \) hängt natürlich von der gewählten Kombination aus Programmiersprache, Compiler und Computer ab. Andere Computersprachen führen aber auch zu anderen Ergebnissen. Da es sehr viele verschiedene denkbare Computersprachen gibt, wird es auch sehr viele verschiedene \( \Omega \)s geben, die alle dieselben Zufallseigenschaften wie Chaitins originales \( \Omega \) aufweisen. Es ist sogar umgekehrt so, dass jedes \( \Omega \) die Haltewahrscheinlichkeit von unendlich vielen verschiedenen Programmiersprachen ist.
Man kann sich nun die Frage stellen, wie häufig diese verschiedenen \( \Omega \)s innerhalb der zufälligen reellen Zahlen sind.
Um diese Frage zu klären, ist neben der Zufälligkeit eine besondere Eigenschaft der \( \Omega \)-Zahlen wichtig:
(der englische Begriff lautet computably enumerable oder recursively enumerable). Das bedeutet, dass man einen unendlich langen Näherungsprozess definieren kann, an dessen Ende der Wert von \( \Omega \) herauskommt. Wir haben diesen Näherungsprozess oben bereits kennengelernt: es ist die Folge der Werte von \( \Omega^s \) mit wachsendem \(s\). Das Problem bei diesem Näherungsprozess ist, dass man nach endlich vielen Schritten nicht unbedingt wissen kann, wie nahe man dem Wert des jeweiligen \( \Omega \) bereits gekommen ist. Der Näherungsprozess muss also nicht zwangsläufig einem Algorithmus zur Berechnung der jeweiligen Zahl liefern – und für die \( \Omega \)s tut er das auch nicht, denn es kann ja eine große Gruppe langer und langlaufender Programme geben, die in einem \( \Omega^s \) noch nicht berücksichtigt wurden, die aber dennoch zusammen die ersten Bit von \( \Omega \) verändern können.
Wir wollen den Begriff rekursiv aufzählbar noch etwas genauer definieren:
Man konnte in den letzten Jahren eine Reihe von dazu gleichwertigen Formulierungen finden. So kann man eine rekursiv aufzählbare reelle Zahl \(x\) auch dadurch charakterisieren, dass die Menge aller rationalen Zahlen, die kleiner als die reelle Zahl \(x\) sind, sich vollständig durch einen Algorithmus in einer (unendlich langen) Liste auflisten lassen (d.h. diese Menge ist rekursiv aufzählbar).
Wie häufig sind nun die rekursiv aufzählbaren reellen Zahlen unter allen reellen Zahlen? Dazu müssen wir uns daran erinnern, wie reelle Zahlen überhaupt definiert sind.
Es gibt eine Reihe von gleichwertigen Definitionen reeller Zahlen. So kann man sie als Zahlen mit ggf. unendlich vielen Dezimal- oder Binärstellen hinter dem Komma charakterisieren. Eine andere dazu gleichwertige Definition wird als Dedekindscher Schnitt bezeichnet. Eine reelle Zahl \(x\) wird dabei als Grenzwert einer (monoton) anwachsenden konvergierenden Folge rationaler Zahlen definiert, wobei diese Folge unendlich lang sein darf. Im Grunde ist auch die Darstellung durch unendlich viele Dezimal- oder Binärstellen nichts anderes.
Der Unterschied zwischen einer beliebigen Zahl und einer rekursiv aufzählbaren reellen Zahl liegt also darin, dass bei der rekursiv aufzählbaren reellen Zahl die Folge rationaler Zahlen berechenbar (algorithmisch aufstellbar) sein muss. Es muss also ein Programm geben, dass diese Folge ausgibt. Trotzdem muss die rekursiv aufzählbare reelle Zahl nicht selbst berechenbar sein, denn die Konvergenz der Folge muss nicht zu einem Rechenverfahren für die reelle Zahl führen, wie das Beispiel der \( \Omega \)s zeigt.
Man kann sich leicht überlegen, dass es unendlich viele rekursiv aufzählbare reelle Zahlen gibt, die wie die rationalen Zahlen dicht in den reellen Zahlen liegen (d.h. beliebig kleine Abstände aufweisen können) und die wie die rationalen Zahlen abzählbar sind (denn die Programme zur Berechnung der konvergierenden Folge rationaler Zahlen sind abzählbar), also in einer unendlichen Liste aufgelistet werden können.
Im Jahr 2001 bewiesen nun Antonin Kucera und Theodore A. Slaman folgenden bemerkenswerten Satz:
(siehe Antonin Kucera und Theodore A. Slaman, Randomness and Recursive Enumerability). Die \( \Omega \)-Zahlen (also die Haltewahrscheinlichkeiten von zufälligen Programmstrings) sind also keineswegs eine Kuriosität im Zahlenreich der reellen Zahlen. Im Gegenteil: die Menge aller durch verschiedene Computersprachen definierbaren \( \Omega \)-Zahlen ist identisch mit der Menge aller rekursiv aufzählbaren reellen Zufallszahlen. Das ist die maximal mögliche Verbreitung, die \( \Omega \)-Zahlen aufgrund ihrer Eigenschaften (Zufälligkeit, rekursive Aufzählbarkeit) überhaupt innerhalb der reellen Zahlen haben können.
Die \( \Omega \)-Zahlen sind also in jeder Hinsicht bemerkenswert. Sie sind definierbar, nicht berechenbar, zufällig und rekursiv aufzählbar. Sie enthalten in der dichtest möglichen Form in ihren ersten \(n\) Bit die Information über Turings Halteproblem aller Programme mit maximal \(n\) Bit in der zu \( \Omega \) gehörenden Programmiersprache. Und damit enthalten sie in ihren ersten \(n\) Bit die Information über die Beweisbarkeit aller Ausdrücke eines maximal \(n\) Bit großen formalen Systems. Und schließlich ist die Menge der \( \Omega \)-Zahlen innerhalb der reellen Zahlen sogar maximal möglich verbreitet – sie ist identisch mit der Menge aller rekursiv aufzählbaren reellen Zufallszahlen.
Was dies alles für das Wesen der Mathematik und die Art, wie wir zukünftig Mathematik betreiben sollten, bedeutet, ist heute sicher noch nicht klar und wird sehr kontrovers diskutiert. In jedem Fall sind die \( \Omega \)-Zahlen und die Art, wie sie mathematische Strukturen extrem dicht komprimieren und gerade dadurch zu Zufallszahlen werden, sehr faszinierend. In einem bekannten Zitat hat Martin Gardner diese Faszination einmal so ausgedrückt (siehe Martin Gardner: The random number \( \Omega \) bids fair to hold the mysteries of the universe, Scientific American 241 (1979) 22-31 ):
"\( \Omega \) ... embodies an enormous amount of wisdom in a very small space ... inasmuch as its first few thousand digits, which could be written on a small piece of paper, contain the answers to more mathematical questions than could be written down in the entire universe.
Throughout history mystics and philosophers have sought a compact key to universal wisdom, a finite formula or text which, when known and understood, would provide the answer to every question. The use of the Bible, the Koran and the I Ching for divination and the tradition of the secret books of Hermes Trismegistus, and the medieval Jewish Cabala exemplify this belief or hope. Such sources of universal wisdom are traditionally protected from casual use by being hard to find, hard to understand when found, and dangerous to use, tending to answer more questions and deeper ones than the searcher wishes to ask. The esoteric book is, like God, simple yet undescribable. It is omniscient, and transforms all who know it. \( \Omega \) is in many senses a cabalistic number. It can be known of, but not known, through human reason. To know it in detail, one would have to accept its uncomputable digit sequence on faith, like words of a sacred text."
© Jörg Resag, www.joerg-resag.de
last modified on 03 March 2023