Kapitel 3
Im Umfeld von Gödels Theorem

4  Chaitins Zufallszahl 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, http://www.cs.auckland.ac.nz/CDMTCS/chaitin/unm.html und Gregory Chaitin: Paradoxes of Randomness, http://www.cs.auckland.ac.nz/CDMTCS/chaitin/Summer.html) 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:

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 b1 bis bn. 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 log2n 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 log2n -Bit-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 2m Stück.
Einige dieser Strings repräsentieren gültige Programme. Wir zählen nun alle die Programme darunter, die anhalten, und dividieren diese Anzahl durch die Gesamtzahl 2m der betrachteten Binärstrings. 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

P(m) = Σp:|p|=m,U(p) hält 1/2|p|

Die Summe Σ 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/2m 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 Ωn ), dass irgendein Teilstring, der die ersten m Bit dieses 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 Ωn addieren, d.h.

Ωn = P(1) + P(2) + ... + P(n) = Σp:|p|≤n,U(p) hält 1/2|p|

Angenommen, irgend jemand würde uns den Wert eines Ωn mitteilen. Was bedeutet das dann für die Lösung von Turings Halteproblems? Ω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. Ω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 2n).

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. Ωn ist gleich dieser Zahl, dividiert durch 2n. Daher ist die Zahl der anhaltenden Programm-Binärstrings mit einer Länge von maximal n Bit gleich Ωn * 2n. Aus Ωn können wir also die Zahl der Programme ermitteln, die maximal n Bit aufweisen und die anhalten. Mit dem oben beschreibenen Algorithmus können wir damit Turings Halteproblem für alle Programme mit maximal n Bit lösen:

Man sieht also, dass Ωn sehr viele Informationen enthält, insbesondere bei großen Werten von n.


Wir können die Wahrscheinlichkeit Ω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 ggf. weiter, bis wir beim n-ten Bit angekommen sind, oder bis wir auf ein anhaltendes Programm gestoßen sind. Dann ist Ω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 Ω, 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 Ω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| die Länge des Binärstrings p ist):

Ω = Σp:U(p) hält 1/2|p|

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 Ω hoch. Genauer tut sie folgendes:

Für jedes anhaltende Programm der Länge m Bit wird also das m-te Bit von Ω um 1 hochgezählt (wobei wir Ω natürlich als Binärstring schreiben, also z.B. Ω = 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 Ω links vom m-ten Bit beeinflussen (je nachdem wieviele Überträge zu höheren Bits erforderlich sind). Daher hat ein einzelnes Bit von Ω auch keine unmittelbare anschauliche Bedeutung (anders als bei Turings Zahl oben).

Man kann beweisen, dass Ω 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 100 Bit schon programmtechnischer Unsinn sind, wird das durch weitere Bit meistens nicht besser. Vermutlich ist Ω also eine recht kleine Zahl.

Wie groß genau ist Ω also? Kann man Ω irgendwie berechnen?

Zunächst einmal hängt der Wert von Ω 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 Ω betrachten so müssen wir leider feststellen, dass sich damit Ω 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: Ω ist nicht nur nicht-berechenbar - man kann beweisen, dass Ω sogar eine Zufallszahl ist! 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 Ω ist vollkommen unabhängig von jedem anderen Bit. Anders ausgedrückt: Ω 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.


Ω enthält eine ungeheure Menge an Information, denn es gilt:

Ein analgoges Ergebnis hatten wir oben bereits für Ωn erhalten. Die Details sind hier allerdings etwas anders.

Wir wollen uns ansehen, warum die ersten n Bit von Ω das Halteproblem für alle Programme mit maximal n Bit lösen, und wie man diese Information aus Ω gewinnen kann (siehe z.B. http://fortnow.com/lance/complog/archive/2002_09_29_archive.html). Dazu definieren wir die folgenden Größen:

Wenn wir s gegen Unendlich gehen lassen, so werden schließlich alle Programme in Ωs berücksichtigt und Ωs wird gleich Ω :

lims→∞ Ωs = Ω.

Anders als Ω ist aber jedes Ωs berechenbar, denn wir müssen ja nur alle Programme mit maximal s Bit bis zu s Schritte lang laufen lassen und die bis dahin anhaltenden Programme in der Summe berücksichtigen. Die Folge der Ωs bildet damit eine mit s anwachsende Folge von berechenbaren rationalen Zahlen, die gegen die nicht berechenbare reelle Zahl Ω konvergiert. Wegen dieser Eigenschaft bezeichnet man Ω 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 Ωs berechnen kann, aber die Konvergenz zu Ω nicht berechenbar ist. Man kann die Folge der Ωs nicht dazu verwenden, um eine Rechenvorschrift zur Berechnung vom Ω abzuleiten, denn egal wie groß man s auch wählt, man weiß nie, wie viele Programme in der Summe noch fehlen, und ob diese Programme alle zusammen nicht doch noch die vorderen Bits von Ω verändern können.

Betrachten wir den Fall, dass s = n ist, und vergleichen Ωs mit Ω(n) (also mit den ersten n Binärstellen von Ω). Dazu überlegen wir, wie sich ein Programm mit m Bit Länge auf die Binärstellen von Ω (und genauso auf Ωs) auswirkt: Wenn das Programm zur Summe beiträgt, so wird Ω um den Term 1/2m hochgezählt, d.h. das m-te Bit wird um Eins hochgezählt, was ggf. einen Überschlag zu den davorliegenden Bits auslösen kann. Niemals jedoch kann ein Programm mit Länge m ein Bit rechts von der m-ten Binärstelle beeinflussen. Daher hat Ωs höchstens s Binärstellen hinter dem Komma, und (für s = n) muss Ωn ≤ Ω(n) sein, denn Ω(n) enthält (anders als Ωs) noch ggf. die Überträge von längeren Programmen auf die ersten n Bit von Ω sowie die Beiträge länger als n Schritte laufender Programme.

Was passiert nun, wenn wir s schrittweise größer als ein vorgegebenes n machen? Dann werden mehr und mehr Programme zu Ωs beitragen, und Ωs wird sich immer mehr an Ω annähern (wobei niemand weiß, wie schnell). Schließlich wird Ωs größer als Ω(n) werden, denn Ω(n) umfasst ja nur die ersten n Binärstellen von Ω und ist damit kleiner als Ω (wir setzen voraus, dass Ω unendlich viele Binärstellen hat, da es anhaltende Programme mit beliebig großer Länge gibt - man füge ggf. einfach einige PRINT-Statements in ein Programm ein, um es zu vergrößern). Auf diese Weise können wir also eine Zahl s oberhalb von n bestimmen, so dass Ωs > Ω(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 Ωs > Ω(n) ist (automatisch ist dann auch s ≥ n ). Die Begründung dafür lautet so:

Angenommen, das Programm würde mehr als s Schritte benötigen, um anzuhalten. Dann würde dieses Programm einen Beitrag 1/2n zur Ω-Summe liefern, aber keinen Beitrag zu Ωs, d.h. es gilt Ω ≥ Ωs + 1/2n . Und weil s so gewählt wurde, dass Ωs > Ω(n) ist, muss auch Ω > Ω(n) + 1/2n sein. Das aber kann nicht sein, denn würde man zu den ersten n Bit von Ω den Term 1/2n hinzuaddieren (also das n-te Bit um 1 erhöhen), so ist die resultierende Zahl größer als Ω, d.h. es gilt immer Ω < Ω(n) + 1/2n . Also muss jedes anhaltende Programm mit n Bit Länge in maximal s Schritten anhalten. Im Grunde haben wir durch die Bedingung Ωs > Ω(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 Ω(n) ≥ Ω(m) ist für n > m, gilt für das oben ermittelte s auch Ωs > Ω(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.

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, EATCS Bulletin, June 2002, vol. 77, pp. 167-179, http://www.cs.umaine.edu/~chaitin/italy.html ): Es gibt ein sehr bekanntes, 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 wiederlegt und ein Gegenbeispiel gefunden.

Wir wollen die Bitlänge dieses Programms mit n bezeichnen. Angenommen, die ersten n Binärstellen von Ω 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 wiederlegt.

Wir können den Informationsgehalt der ersten n Bit von Ω 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, such 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 Ω 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 Ω 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, wiederlegbar sind oder keines von Beidem. Dies ist der Grund, weshalb Chaitins Ω 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 Ω 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*n -te Bit von Ω ist 1" sind daher innerhalb eines n-Bit großen formalen Systems werder beweisbar noch wiederlegbar - eine weitere Spielart von Gödels Unvollständigleitssatz.

Um mehr als etwa n Bit von Ω 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 Ω-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 wiederlegbar als in einem kleineren formalen System - entsprechend können auch mehr Bits von Ω 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 Ω als die dichteste mögliche Kompression der Information darüber ansehen, welche Aussagen beweisbar bzw. wiederlegbar 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 Ω aussehen. Wir werden unten noch sehen, dass es unendlich viele verschiedene Ωs gibt!

Allgemein muss man zur Berechnung der ersten Ω-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 Ω 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 Ω wir ermitteln wollen. Genau deshalb gibt es auch keinen Algorithmus, der beliebig viele Bits von Ω ermitteln kann -- Ω ist nicht berechenbar.

Man zahlt nun einen Preis für diese extreme Kompression mathematischer Information. Es ist extrem aufwendig, sie aus Ω 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 Ω 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 Ωs > Ω(n) wird (d.h. Ωs reproduziert korrekt die ersten n Stellen von Ω). 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. Nun kann man den Wert von Ωs ermitteln und nachprüfen, ob er größer als die ersten n Binärstellen von Ω (also größer als Ω(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 Programme über genügend lange Zeit testen, um die ersten n Bit von Ω korrekt zu reproduzieren (genau das bedeutet Ωs > Ω(n) ). Wann dieser Punkt erreicht ist, weiß man allerdings nur, wenn man die ersten n Bit von Ω bereits kennt (wir erinnern uns: die Konvergenz von Ωs gegen Ω ist nicht berechenbar, d.h. man weiß nie, wie nahe man dem Wert von Ω bereits gekommen ist; deshalb ist die Ermittlung der ersten n Bit von Ω noch viel schwieriger als die Ermittlung von s).

Anders ausgedrückt: Man muss 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 ≤ s) angehalten haben. 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 Ωs > Ω(n).

Den Aufwand, der zum Extrahieren der Information aus Ω 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, http://www.arxiv.org/abs/nlin.cd/0112022). Das ist nicht mehr zu überbieten! In der Praxis ist die Information in Ω also letztlich unbrauchbar. Sie ist so dicht komprimiert, dass die Dekompression viel zu aufwendig ist. Die Kompression der Halte-Information in Ω 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 Ω eine Zufallszahl 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 Ω (also Ω(n) ) bekannt sind. Wir schreiben nun ein Programm (nennen wir es P), das Ω(n) als Konstante enthält und das folgenden Algorithmus ausführt:

Programm P:

  1. Ermittle mit Hilfe des vorgegebenen Ω(n) alle anhaltenden Programme bis n Bit Länge, lasse sie laufen und notiere ihre Ausgabe.
  2. Lasse die ganzzahlige Schleifenvariable x von 1 an laufen und zähle sie schrittweise um jeweils 1 hoch.
  3. Überprüfe, ob eines der anhaltenden Programme das aktuelle x ausgibt.
  4. Falls kein solches Programm vorhanden ist, gib x aus und halte an. Andernfalls gehe zum nächsten x über.

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. 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 des Programms P (die wir als |P| bezeichnen wollen), denn P gibt x ja aus: H(x) ≤ |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 der vorgegebenen Konstante Ω(n), die in der kürzest möglichen Form gerade soviel Speicherplatz benötigt, wie es ihrer Komplexität H(Ω(n)) entspricht. Also ist |P| = H(Ω(n)) + c , wobei c eine konstante Zahl ist, die nicht von n abhängt. Damit haben wir H(x) ≤ |P| = H(Ω(n)) + c . Weil aber zusätzlich auch H(x) > n ist (siehe oben), folgt n < |P| = H(Ω(n)) + c , oder etwas anders geschrieben:

H(Ω(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 Ω 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 Ω entspricht ungefähr der Stellenzahl n selbst. &Omega ist damit nicht kompressibel und damit ist Ω 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 Ω(n) . Wir können H(Ω(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. Dabei hätte H(Ω(n)) auch die Bitlänge des kürzesten Programms sein können, das das Halteproblem löst - die Überlegung bleibt die gleiche. Sie zeigt, dass diese minimale Information, die wir über das Halteproblem hineinstecken müssen, linear mit der Maximalgröße der betrachteten Programme wächst. Daher kann es keinen allgemeinen Algorithmus geben, der ein beliebiges n als Konstante enthält (entsprechend einem Informationsgehalt von höchstens log2n 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 log2n + 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 Ω 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 der Maximallänge n. Statt Ω(n) müssten wir in der obigen Überlegung daher T(an) verwenden, wobei a irgendeine Zahl größer als 1 ist. Unser Ergebnis wäre dann H(T(an)) > n - c oder anders geschrieben H(T(k)) > logak - c (wobei wir zum Umschreiben n = logak verwendet haben). Die obige Überlegung würde daher nur ergeben, dass die Komplexität der ersten k Stellen von Turings Zahl mindestens logarithmisch mit der Stellenzahl k zunimmt. Dies passt sehr gut zu unserem Ergebnis weiter oben, dass Turings Zahl komprimiert werden kann.


Wie eng Ω 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 x3 + k y2 = 5 z4 . Gesucht sind bei vorgegebenem ganzzahligem k (z.B. 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 Ω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 Ω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 Ω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 Ωn konvergiert ja gegen Ω. 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 Ω gleich 1 ist, und nur endlich viele (oder gar keine) Lösungen, wenn das k-te Bit von Ω gleich 0 ist.

Nun sind die einzelnen Bits von Ω vollkommen unabhängig voneinander, denn Ω 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 Ω ü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 Ω 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, Ωn in Gleichungen zu übersetzen. Außerdem gibt es unendlich viele verschiedene Ωs, da Ω von der gewählten Computersprache abhängt. Es gibt also ganze Bereiche, in denen die Mathematik ein zufälliges Verhalten aufweist.


Da Ω 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 Bit 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 Ω 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 Ω (entsprechend seiner Wahl einer bestimmten Computersprache) zu berechnen (siehe C.S.Calude, M.J.Dinneen, Chi-Kou Shu: Computing A Glimpse of Randomness, http://www.arxiv.org/abs/nlin.cd/0112022). 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 (siehe auch http://www.cs.auckland.ac.nz/~jaru003/treasure_chest/CrisWork_NewScientistReport.htm). 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 Ω beeinflussen könnten. So konnte sichergestellt werden, dass die Analyse aller Programme mit maximal 84 Bit ausreicht, die ersten 64 Bit von Chaitins Ω zu bestimmen. Hier ist das Ergebnis in Binärform:

Ω = 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 Ω 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 Ωs geben, die alle Zufallseigenschaften wie Chaitins originales Ω aufweisen. Es ist sogar umgekehrt so, dass jedes Ω die Haltewahrscheinlichkeit von unendlich vielen verschiedenen Programmiersprachen ist.

Man kann sich nun die Frage stellen, wie häufig diese verschiedenen Ωs innerhalb der zufälligen reellen Zahlen sind.

Um diese Frage zu klären, ist neben der Zufälligkeit eine besondere Eigenschaft der Ω-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 Ω herauskommt. Wir haben diesen Näherungsprozess oben bereits kennengelernt: es ist die Folge der Werte von Ωs mit wachsendem s. Das Problem bei diesem Näherungsprozess ist, dass man nach endlich vielen Schritten nicht unbedingt wissen muss, wie nahe man dem Wert des jeweiligen Ωs bereits gekommen ist. Der Näherungsprozess muss also nicht zwangsläufig einem Algorithmus zur Berechnung der jeweiligen Zahl liefern - und für die Ωs tut er das auch nicht, denn es kann ja eine große Gruppe langer und langlaufender Programme geben, die in einem Ωs noch nicht berücksichtigt wurden, die aber dennoch zusammen die ersten Bit von Ω 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 Ω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 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, http://math.berkeley.edu/~slaman/papers/random.pdf). Die Ω-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 Ω-Zahlen ist identisch mit der Menge aller rekursiv aufzählbaren reellen Zufallszahlen. Das ist die maximal mögliche Verbreitung, die Ω-Zahlen aufgrund ihrer Eigenschaften (Zufälligkeit, rekursive Aufzählbarkeit) überhaupt innerhalb der reellen Zahlen haben können.

Die Ω-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 Ω 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 Ω-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 Ω-Zahlen und die Art, wie sie mathematische Strukturen extrem dicht komprimieren und gerade dadurch zu Zufallszahlen werden, sehr faszinierend. In einem bekannten Zitat hat M.Gardner diese Faszination einmal so ausgedrückt (siehe M.Gardner: The random number omega bids fair to hold the mysteries of the universe, Scientific American 241 (1979) 22-31 ):


zurück zum Inhaltsverzeichnis

last modified on 16 December 2008