Kapitel 3
Im Umfeld von Gödels Theorem

3  Über die Komplexität und Zufälligkeit von Zahlen

Zu Beginn dieses Kapitels möchte ich den Leser bitten, sich die folgende Zahl anzusehen

3.1415926535897932384626433832795028841971693993751058209749445923078164062862
089986280348253421170679821480865132823066470938446095505822317253594081284811
174502841027019385211055596446229489549303819644288109756659334461284756482337
867831652712019091456485669234603486104543266482133936072602491412737245870066
063155881748815209209628292540917153643678925903600113305305488204665213841469
519415116094330572703657595919530921861173819326117931051185480744623799627495
673518857527248912279381830119491298336733624406566430860213949463952247371907
021798609437027705392171762931767523846748184676694051320005681271452635608277
857713427577896091736371787214684409012249534301465495853710507922796892589235
420199561121290219608640344181598136297747713099605187072113499999983729780499
510597317328160963185950244594553469083026425223082533446850352619311881710100
031378387528865875332083814206171776691473035982534904287554687311595628638823
537875937519577818577805321712268066130019278766111959092164201989380952572010
...

und nun die Frage zu beantworten: "Ist diese Zahl zufällig?"

Wenn man sich die Zahl so ansieht, hat man tatsächlich den Eindruck, dass sie zufällig ist. Die einzelnen Ziffern scheinen vollkommen unregelmäßig aufeinander zu folgen, und es ist kein Muster erkennbar. Insofern besitzt diese Zahl tatsächlich viele Eigenschaften, die man bei einer zufälligen Zahl erwarten würde.

Um die obige Frage klar zu beantworten, müssen wir jedoch genauer spezifizieren, was wir unter einer zufälligen Zahl (oder kurz Zufallszahl) verstehen wollen.

Dazu legen wir fest:

Zufallszahl ist damit gleichbedeutend mit nicht komprimierbarer Zahl. Was dabei die Formulierung "deutlich kürzer" bedeuten soll, muss man strenggenommen noch genau festlegen. Man kann z.B. fordern, dass es bei Zufallszahlen kein Computerprogramm gibt, dass um mindestens 10 Bit kürzer ist als die Zahl. Außerdem gilt diese Definition nur für Zahlen, die sich durch einen endlichen Binärstring darstellen lassen. Wir gehen weiter unten noch genauer darauf ein.

Der Grund für diese Festlegung von Zufälligkeit einer Zahl liegt darin, dass wir bei einer Zufallszahl keine Muster oder Regelmäßigkeiten erwarten, die sich zum Komprimieren der Zahl nutzen lassen. Beispielsweise lässt sich die Zahl 1212121212 komprimieren durch die Anweisung "Drucke fünf mal die Ziffernfolge 12". Bei größeren Ziffernfolgen kann man sich so leicht vorstellen, dass das entsprechende Computerprogramm deutlich kürzer als die Zahl selbst ist.

Die obige Definition wirft die Frage auf, ob es überhaupt Zahlen gibt, die in diesem Sinn nicht komprimierbar und damit zufällig sind. Vielleicht lässt sich ja jede Zahl wenigstens um einige Prozent komprimieren?

Man kann diese Frage durch Abzählen klären. Dazu zählt man einerseits, wieviele Zahlen es bis maximal n Bit Speicherplatz für diese Zahlen gibt, und vergleicht diese Zahl mit der Zahl der Programme mit maximal n Bit Speicherplatz. Gibt es deutlich mehr Zahlen als Programme, so bleiben Zahlen übrig, zu denen es kein kürzeres Programm geben kann. Diese Zahlen sind dann nicht-komprimierbar und damit zufällig.

Beginnen wir mit den Zahlen, die maximal n Bit lang sind (die sich also als Binärstring mit höchstens n Stellen schreiben lassen; z.B. wird die Zahl 19 durch den Binärstring "10011" dargestellt, was soviel bedeutet wie 1*16 + 0*8 + 0*4 + 1*2 + 1*1). Es gibt 2 hoch n solche Zahlen, denn jeder Binärstring mit höchstens n Stellen ist eine solche Zahl.

Betrachten wir nun zum Vergleich alle Programme, die als Binärstring kodiert maximal n Bit lang sind (letztlich werden auf einem üblichen Computer ja alle Programme als Binärstring abgelegt). Dazu müssen wir natürlich vorher irgendeine Programmiersprache auswählen. Programme müssen entsprechend der gewählten Programmiersprache eine gewisse Struktur haben, d.h. ein Compiler wird nicht jeden beliebigen Binärstring als Programm generieren können. Eine genauere Analyse zeigt, dass Binärstrings, die Programme kodieren sollen, eine wichtige Eigenschaft besitzen müssen (Gregory Chaitin, der sich viel mit diesen Fragestellungen beschäftigt hat, benötigte nach eigenen Angaben etwa 10 Jahre, um dieses wichtige technische Detail zu erkennen und sauber auszuarbeiten): Jede Verlängerung eines als Computerprogramm geeigneten Binärstrings ist selbst kein geeigneter Binärstring. Man sagt auch, die Programmiersprache muss Präfix-frei sein, d.h. ausbalancierte Klammersymbole und BEGIN-END-Kommandos haben. Wenn man also einmal auf einen als Programm zulässigen Binärstring stößt, so kann man alle durch Verlängerung daraus erzeugten Binärstrings wegstreichen, denn sie sind keine als Programm zulässigen Binärstrings. Damit ist klar, dass viele Binärstrings mit n Bit Länge keine zulässigen Programme repräsentieren.

Wie groß die Zahl der als Programm geeigneten Binärstrings im Vergleich zu der Gesamtzahl der Binärstrings gleicher Länge ist, kann man beispielsweise folgendermaßen grob abschätzen:

Angenommen, nur solche Binärstrings kommen als Programme in Frage, deren Länge ein Vielfaches einer natürlichen Zahl (nennen wir sie N) ist. Wenn beispielsweise N=2 ist, so müssen Programm-Binärstrings die Länge 2 Bit oder 4 Bit oder 6 Bit usw. aufweisen. Natürlich kann man auch N=1 wählen; dann ist jede Bitlänge erlaubt. Nun nehmen wir weiter an, dass sich unter je 2 hoch N Binärstrings der Länge N gerade ein Programm-Binärstring befindet. Für N=2 bedeutet das, dass jeder vierte Binärstring mit geradzahliger Bitlänge ein Programm darstellt. Der Parameter N dient also dazu, in unserem kleinen Modell die Wahrscheinlichkeit für das Auftreten von Programm-Binärstrings darzustellen.

Betrachten wir den Fall N=1. Programme treten demnach sehr häufig auf, denn jeder zweite noch erlaubte Binärstring ist ein Programm. Beginnen wir mit Binärstrings der Länge Eins. Es gibt die beiden Strings "0" und "1". Einer von beiden muss nach unserer Annahme ein Programm sein - nehmen wir den String "0". Ab sofort sind damit alle längeren Binärstrings, die mit "0" beginnen, keine möglichen Programm-Binärstrings mehr, denn Verlängerungen von Programmstrings sind keine Programmstrings. Gehen wir nun zu den Binärstrings der Länge Zwei. Nur die beiden Strings "10" und "11" sind möglich, denn Strings, die mit "0" beginnen, sind ausgeschlossen. Nun ist wieder einer dieser beiden Strings ein Programm (sagen wir "10") und wir können zu Strings der Länge Drei übergehen; wieder bleiben nur zwei Kandidaten: "110" und "111" (die Strings dürfen ja nicht mehr mit "0" oder mit "10" beginnen). Wir sehen, wie jeder Programmstring einen ganzen Baum von Möglichkeiten abschneidet, nämlich alle längeren Strings, die mit dem Programmstring beginnen. Im Fall N=1 gibt es deshalb für jede Bitlänge nur einen einzigen Programmstring, während die Zahl der als Zahlen geeigneten Binärstrings exponentiell mit der Bitlänge wächst (denn jeder Binärstring stellt eine Zahl dar).

Wir sehen: eine hohe Wahrscheinlichkeit, dass ein Binärstring ein Programm ist, führt dazu, dass sehr viele Äste des Baums abgeschnitten werden, so dass pro Bitlänge nur ein Programmstring übrig bleibt. Es ist wie bei einem Baum, bei dem an einem Ast sehr viele Blätter wachsen, bei dem diese Blätter aber den Platz für weitere Verzweigungen wegnehmen.

Betrachten wir daher den Fall N=2. Nur Binärstrings mit gerader Bitlänge können jetzt noch Programmstrings sein. Damit hat der Ast nun weniger Blätter, aber mehr Verzweigungen. Unter den vier Binärstrings der Länge Zwei befindet sich ein Programmstring. Damit fallen von den 16 Binärstrings der Länge Vier die Vier Binärstrings weg, die mit diesem Programmstring anfangen. Es bleiben 12 Strings übrig, von denen drei Programmstrings sind. Und so geht es weiter.


Fall N=2 bis zur einer Länge von vier Bit. Programm-Binärstrings sind in Rot dargestellt. Der Baum der möglichen Programmstrings ist hinter jedem roten Programmstring nach rechts abgeschnitten, da Verlängerungen eines Programmstrings selbst keine Programmstrings sein können.


Allgemein gilt in unserem Modell: Unter den 2i*N Binärstrings der Länge i*N kommen 2N (2N-1)i-1 als Programmstrings in Frage (alle anderen fallen weg, da sie Verlängerungen kürzerer Programmstrings sind), und (2N-1)i-1 Strings davon sind Programmstrings.

Die folgende Tabelle vermittelt einen Eindruck davon, wieviel Prozent aller Binärstrings einer bestimmten Länge in unserem Modell Programmstrings sein können, abhängig vom Parameter N:

Stringlänge in Bit

Anteil für N=2

Anteil für N=4

Anteil für N=8

8

10,55%

5,86%

0,391%

16

3,34%

5,15%

0,389%

24

1,05%

4,53%

0,387%

32

0,334%

3,98%

0,386%

40

0,106%

3,49%

0,385%

Es gibt also deutlich weniger Programme mit maximal n Bit Länge als Zahlen mit maximal n Bit Länge. Daher kann es nicht zu jeder Zahl mit höchstens n Bit ein Programm mit weniger als n Bit geben (das diese Zahl auch noch ausgibt), denn es sind nicht genug Programme da! Also muss es Zahlen geben, die nicht durch ein kürzeres Programm ausgegeben werden können, d.h. es muss zufällige Zahlen geben.

Der Unterschied zwischen der Zahl der Programme mit maximal n Bit und der 2 hoch n Zahlen mit maximal n Bit vergrößert sich, je größer die Bitzahl n ist. Dies zeigt die obige Tabelle. Je größer n wird, umso größer ist die Wahrscheinlichkeit, dass irgendeine willkürlich herausgegriffene Zahl eine Zufallszahl ist. Lässt man beliebig große Zahlen und Programme zu (d.h. die Bitzahl n darf beliebig groß werden), so gibt es nur abzählbar viele Programme (d.h. es gibt eine unendlich lange Programmliste), aber überabzählbar viele Zahlen (d.h. jede (unendlich lange) Liste von Zahlen ist unvollständig). In diesem Sinn kann man dann sogar sagen, dass dann fast jede Zahl zufällig ist. Wir werden weiter unten noch eine präzise Version dieser Aussage kennenlernen.

Was passiert nun, wenn man die einzelen Bits einer n-Bit langen Zahl würfelt, die Bits also zufällig bestimmt? Ist die so erhaltene Zahl im Sinne unserer Definition zufällig, also nicht komprimierbar?

Es könnte natürlich sein, dass man nur Einsen würfelt. Die so erhaltene Zahl lässt sich sicher komprimieren, ist also in diesem Sinne nicht zufällig. Je mehr Bits jedoch die Zahl enthält, d.h. je öfter gewürfelt werden muss, umso größer ist die Wahrscheinlichkeit, auf diese Weise eine nicht komprimierbare Zahl zu erzeugen. Im Grenzfall, dass unendlich viele Bits zu würfeln sind, ist die Wahrscheinlichkeit sogar gleich Eins, dass eine Zufallszahl dabei entsteht.


Nun ist es keineswegs immer offensichtlich, ob in einer vorgegebenen Zahl ein Muster vorhanden ist oder nicht. So konnten wir in der oben dargestellten Zahl kein Muster erkennen. Aber dennoch gibt es eines, denn es gibt relativ einfache und kurze Computerprogramme, die die obige Zahl (inclusive der nur durch ... angedeuteten weiteren Ziffern) berechnen können. Viele Leser werden bereits wissen, warum: es handelt sich um die Kreiszahl Pi. Eine der vielen Möglichkeiten, Pi zu berechnen, ist die folgende:

Pi = 4 - 4/3 + 4/5 - 4/7 + 4/9 - 4/11 + ...

Dieser Algorithmus lässt sich leicht in einem kleinen Computerprogramm codieren. Auf diese Weise kann man (einen hinreichend großen Computer vorausgesetzt - eine Turingmaschine ist nach Definition sogar beliebig groß) beliebig viele Stellen der Zahl Pi berechnen.

Wäre es möglich, ein Computerprogramm zu entwickeln, das dieses Muster in der Zahl Pi entdecken würde und damit die Zahl deutlich komprimieren könnte? Natürlich wäre das möglich, denn dieses Programm würde jede Zahl daraufhin untersuchen, ob Pi darin vorkommt, und dann das Wissen über Pi anwenden.

Interessanter wäre es, ein Programm zu besitzen, das beliebige versteckte Muster in irgendeiner vorgegebenen Zahl entdecken könnte und damit bei jeder Zahl angeben könnte, ob sie komprimierbar (und damit nicht-zufällig) ist oder nicht. Dass ein solches Programm wohl nicht einfach zu schreiben ist, hat uns das Beispiel der Zahl Pi bereits gezeigt. Gregory Chaitin hat schließlich gezeigt, dass es unmöglich ist, ein solches Programm zu schreiben:

Warum ist das so?

Nehmen wir einmal an, es gäbe doch einen solchen Algorithmus, den wir dann z.B. als Unterprogramm für andere Programme zur Verfügung stellen könnten. Nun schreiben wir ein Programm, das eine interne Variable schrittweise von 1 an hochzählt. Nennen wir diese Variable N. Das Programm besitzt also eine Schleife, in der N die Werte 0, 1, 2, 3 usw. annimmt. Innerhalb der Schleife wird nun das obige Unterprogramm aufgerufen und überprüft, ob die Schleifenvariable N zufällig ist oder nicht. Wenn sie zufällig ist, so druckt das Programm die Zahl N aus und hält an. Ist die Zahl N jedoch nicht zufällig, so läuft die Schleife einfach weiter, d.h. das Programm addiert eine "1" zu der Schleifenvariablen N hinzu und überprüft für diese neue Zahl erneut, ob sie zufällig ist.

Auf diese Weise wird die Schleifenvariable N schrittweise solange um 1 vergrößert, bis sie irgendwann vom Unterprogramm als zufällig angesehen wird, woraufhin das Programm sie ausdruckt anhält. Damit würde das Programm die kleinste natürliche Zahl ausdrucken, die zufällig ist.

Wir können dieses Programm nun leicht so modifizieren, dass es eine zufällige Zahl ausdruckt, die (als Binärstring) sehr viel größer ist als die Größe des Programms (auch kodiert als Binärstring). Nehmen wir an, die Größe des Programms sei L Bit. Dann beginnen wir die obige Schleife nicht mit dem Wert N=1, sondern mit einer Zahl (nennen wir sie Nstart), die als Binärstring als eine 1 mit 2*L Nullen dahinter geschrieben wird. Damit ist gewährleistet, dass diese Zahl Nstart mindestens doppelt so viel Speicherplatz benötigt wie das Programm (also mehr als L Bit).

Das Programm beginnt nun, die Zahlen ab der Zahl Nstart schrittweise auf Zufälligkeit hin zu untersuchen. Die erste gefundene Zufallszahl wird ausgedruckt, und das Programm hält an. Wir wissen, dass es eine Zufallszahl oberhalb von Nstart geben muss, denn es gibt sehr viel mehr Zahlen oberhalb von Nstart als Programme mit maximal gleicher Bitlänge (siehe oben). Die Existenz von Zufallszahlen oberhalb von Nstart erscheint uns auch plausibel, denn schließlich können wir ja unbegrenzt viele Stellen einer Zahl zufällig würfeln. Das Programm wird also irgendwann eine Zufallszahl ausdrucken, die mehr als 2*L Bit Speicherplatz benötigt und dann anhalten. Andererseits benötigt das Programm selbst nur L Bit Speicherplatz.

Unsere Überlegung zeigt: Wenn es einen Algorithmus gibt, mit dem man jede beliebige Zahl auf Zufälligkeit hin überprüfen kann, so kann man damit ein Programm der Länge L Bit bauen, das eine Zufallszahl ausgibt, die deutlich mehr Speicherplatz benötigt als das Programm, welches sie ausgibt. Das aber bedeutet, dass sich die ausgegebene Zahl komprimieren lässt, denn wir haben gerade ein Programm angegeben, das deutlich kürzer ist als die Zahl und das dennoch die Zahl ausgeben kann. Nach unserer Definition kann damit die ausgegebene Zahl nicht zufällig sein. Wir haben einen Widerspruch! Daher muss unsere Annahme falsch sein, d.h. es kann keinen Algorithmus geben, der beliebige Zahlen auf Zufälligkeit überprüfen kann. Chaitins Theorem ist damit bewiesen.

Noch eine kurze Randbemerkung: In Einzelfällen mag es durchaus möglich sein, zu beweisen, dass eine Zahl zufällig ist. Es ist jedoch unmöglich, dies mit Hilfe eines einzigen Algorithmus bei beliebigen Zahlen zu tun.


Es gibt einen engen Zusammenhang zwischen Chaitins Theorem und Turings Halteproblem. Angenommen, Turings Halteproblem wäre lösbar, d.h. wir können bei jedem Programm mechanisch bestimmen, ob es irgendwann anhält oder nicht. Dann könnten wir folgenden Algorithmus aufbauen:

  1. Wir geben irgendeine Zahl (nennen wir sie x) der Länge n Bit vor und bestimmen die Länge des Programms "PRINT x" (wobei x als Binärzahl explizit ausgeschrieben ist). Dieses Programm wird etwas mehr als n Bit lang sein - sagen wir, n + m Bit lang.
  2. Liste alphabetisch und der Größe nach geordnet alle Programme auf, die kürzer als n + m Bit sind (also kürzer als das Programm "PRINT x" mit ausgeschriebener Zahl x).
  3. Lösche alle Programme aus der Liste, die nicht anhalten.
  4. Lasse alle übrigen Programme aus der Liste laufen und sieh nach, ob eines dabei ist, das die oben vorgegebene Zahl x ausgibt.

Wenn ein solches Programm dabei ist, so wissen wir, dass x nicht zufällig ist, denn wir haben gerade ein Programm gefunden, das kürzer als "PRINT x" ist und das die Zahl x ausgibt. Andernfalls wissen wir, dass x zufällig ist, denn kein kürzeres Programm kann sie ausgeben. Damit hätten wir einen Algorithmus gefunden, der jede Zahl auf Zufälligkeit hin untersuchen kann - im Widerspruch zu Chaitins Theorem, das wir gerade bewiesen haben. Einer der Schritte in diesem Algorithmus muss also undurchführbar sein. Der einzige Schritt, der dafür in Frage kommt, ist der Vorletzte ("Lösche alle Programme aus der Liste, die nicht anhalten"). Aus Chaitins Theorem folgt also unmittelbar, dass Turings Halteproblem unlösbar ist.


Im Folgenden möchte ich die obigen Aussagen etwas erweitern und präzisieren (siehe z.B. http://www.wikipedia.org/wiki/Algorithmic_information_theory). Man kann den oben definierten Begriff der Zufälligkeit erweitern und den Begriff der Komplexität einer Zahl (oder allgemeiner: einer Zeichenkette) einführen:

(statt von Zahlen kann man auch allgemeiner von Zeichenketten (Strings) reden). Je kürzer das kürzeste Programm ist, das eine bestimmte Zahl ausgeben kann, umso weniger komplex ist die Zahl, d.h. umso weniger Information enthält sie. Eine zufällige Zahl lässt sich dagegen praktisch gar nicht komprimieren, d.h. das kürzeste Programm, das sie ausgibt, hat ungefähr dieselbe Länge wie die Zahl selbst (z.B. das Programm "PRINT (Ziffernfolge der Zahl)".

Um die Definition der Komplexität einer Zahl formell sauber zu fassen, muss man strenggenommen genau festlegen, welcher Typ von Programmen erlaubt ist, d.h. welche Programmiersprache, welcher Compiler und welcher Computer verwendet wird. Man könnte z.B. Turingmaschinen verwenden, oder eine Programmiersprache wie C oder LISP sowie einen bestimmten Compiler und einen bestimmten PC-Prozessor.

Glücklicherweise spielt es letztlich keine Rolle, für welchen Computer und für welche Programmiersprache man sich entscheidet, solange sich verschiedene Computer und Programmiersprachen gegenseitig simulieren können. So wissen wir ja, dass eine Turingmaschine alles das tun kann, was ein gewöhnlicher Digitalcomputer tut. Ein Programm in der einen Programmiersprache lässt sich in ein Programm in einer anderen Programmiersprache umwandeln, indem man einen Interpreter für die umzuwandelnde Programmiersprache dem vorgegebenen Programm hinzufügt sowie in der neuen Sprache eine Art Container für das Programm baut. Wechselt man also die Programmiersprache, so verändert sich die Komplexität einer Zahl maximal um einen konstanten Faktor C (die den Speicher-Overhead beschreibt, um das umzuwandelnde Programm zu erfassen) und eine additive Konstante D (entsprechend der Länge des hinzugefügten Interpreters), die beide nur von den verwendeten Programmiersprachen abhängen, nicht aber von der untersuchten Zahl.

Im Folgenden wollen wir einfach irgendeine Programmiersprache und einen Computertyp wählen (z.B. Turingmaschinen). Damit ist eindeutig festgelegt, was die Komplexität einer Zahl bedeutet. Es stellt sich nun die Frage, ob und wie man die Komplexität einer beliebigen Zahl berechnen kann.

Wir hatten oben nachgewiesen, dass man die Zufälligkeit einer beliebigen Zahl nicht allgemein ermitteln kann. Vollkommen analog lässt sich auch zeigen, dass man die Komplexität einer beliebigen Zahl nicht mit einem einzigen Algorithmus berechnen kann (d.h. die Komplexität ist eine nicht-berechenbare Eigenschaft oder Funktion natürlicher Zahlen).

Nehmen wir also an, es gäbe einen solchen Algorithmus, mit dem man die Komplexität jeder Zahl berechnen kann. Wieder stellen wir diesen Algorithmus als Unterprogramm zur Verfügung. Nun schreiben wir ein Programm, das eine interne Variable N schrittweise von 1 an hochzählt. Innerhalb der Schleife rufen wir das obige Unterprogramm auf und bestimmen die Komplexität der Schleifenvariablen N. Wenn diese Komplexität größer als eine gewisse Zahl L (über die wir gleich etwas sagen) ist, so druckt das Programm die Zahl N aus und hält an. Andernfalls läuft die Schleife weiter.

Auf diese Weise wird die Schleifenvariable N schrittweise solange um 1 vergrößert, bis eine Zahl ausgegeben wird, deren Komplexität größer als die im Programm vorgegebene Konstante L ist. Solche Zahlen muss es geben, denn es gibt oberhalb von L unendlich viele Zufallszahlen, und Zufallszahlen haben eine Komplexität, die ungefähr gleich ihrer eigenen Bitlänge ist (denn sonst ließen sie sich komprimieren).

Nun müssen wir den Programmparameter L noch festlegen. Wir wählen ihn so, dass er deutlich größer als die Bitgröße des Programms selbst ist (z.B. doppelt so groß). Das Programm würde dann eine Zahl ausgeben, deren Komplexität deutlich größer als L ist. Aber die Komplexität dieser Zahl kann nicht deutlich größer als L sein, denn wir haben gerade ein Programm der Länge L geschrieben, das diese Zahl ausgibt. Dieser Widerspruch zeigt, dass es keinen allgemeinen Algorithmus zur Berechnung der Komplexität einer beliebigen Zahl geben kann.

Halten wir das Ergebnis noch einmal fest:

Auch hier gilt natürlich wieder, dass in Ausnahmefällen die Komplexität bestimmter Zahlen berechnet werden kann. Aber sie kann nicht allgemein in jedem Fall auf dieselbe Weise berechnet werden.

Der obige Beweis ist eng verwandt mit dem bekannten Berry-Paradoxon: "Es sei N die kleinste Zahl, die sich nicht in weniger als zwanzig Worten definieren lässt." Dieser Satz besitzt 16 Worte und damit weniger als 20 Worte. Damit konnten wir N in weniger als 20 Worten definieren, obwohl N so definiert war, dass genau dies unmöglich sein sollte. Wir haben einen Widerspruch!

Die Analogie zwischen Berrys Paradoxon und unserem Beweis ergibt sich folgendermaßen. Der Satz "Es sei N die kleinste Zahl, die sich nicht in weniger als zwanzig Worten definieren lässt." wird ersetzt durch das obige Programm, das die kleinste Zahl ausdruckt, die eine Komplexität von mindestens L aufweist. L war aber gerade die Größe des Programms, d.h. das Programm gibt eine Zahl N aus, die wegen ihrer Komplexität sich nicht durch ein Programm von L Bit Größe ausdrucken lässt. Genau das tut aber das Programm - ein Widerspruch, der zeigt, dass es dieses Programm nicht geben kann.

Es ist interessant, wie sich verschiedene Paradoxa als mathematische Sätze wiederspiegeln. Berrys Paradoxon führt zur Nicht-Berechenbarkeit der Komplexität einer Zahl, und das Paradoxon "Ich bin nicht wahr" führt zur Nicht-Beweisbarkeit von Gödels Satz (wobei wahr durch beweisbar zu ersetzen ist). Paradoxien sind also weit mehr als nur merkwürdige, nicht ernst zu nehmende Konstrukte. Sie zeigen die prinzipiellen Grenzen von Sprachen und von formalen Systemen auf.

Nun ist die Komplexität einer beliebigen Zahl zwar nicht allgemein berechenbar, aber es ist leicht möglich, obere Grenzen für diese Komplexität anzugeben. Dazu komprimiert man die Zahl einfach mit irgend einem Kompressionsalgorithmus, wie er in Packprogrammen auf Computern zur Verfügung steht (z.B. das bekannte ZIP-Programm). Wie nahe man damit allerdings an die Komplexität (und damit an die maximal mögliche Kompression der Zahl) herankommt, kann man höchstens im Einzelfall ermitteln, nicht aber allgemein für beliebige Zahlen.

Wir hatten oben den Zusammenhang zwischen der Komplexität und der Zufälligkeit einer Zahl bereits erwähnt: die Komplexität (in Bit) einer zufälligen Zahl entspricht ungefähr der Länge des Binärstrings der Zahl. Dabei hatte wir weiterhin gesagt, dass bei größeren Zahlen die meisten dieser Zahlen zufällig sind, also eine hohe Komplexität aufweisen. Diese Aussage können wir nun präzisieren:

Der Beweis dieser Aussage erfolgt ähnlich zu unserem obigen Modell, mit dem wir abgeschätzt haben, wieviele Binärstrings als Programme in Frage kommen.
Die Wahrscheinlichkeit, dass die Kompexität einer Zahl x um n Bit kleiner als ihre Bitlänge ist, nimmt also exponentiell mit n ab. Mit sehr großer Wahrscheinlichkeit hat x also eine Komplexität, die nur wenig unter ihrer Bitlänge liegt. Das ist damit gemeint, wenn man sagt, die meisten Zahlen sind zufällig.


Obwohl die meisten Zahlen zufällig sind, können wir die Zufälligkeit bei beliebig herausgegriffenen Zahlen weder beweisen noch wiederlegen, sobald ihre Komplexität eine gewisse kritische Grenze überschreitet. Präzise ausgedrückt, lautet diese Aussage so:

Es gibt also eine obere Grenze für beweisbare Komplexität in einem formalen System, die ungefähr gleich der Größe des formalen Systems ist (Details kommen gleich). Eine Komplexität oberhalb dieser Grenze kann in dem formalen System nicht mehr erfasst werden, d.h. sie kann bei den entsprechenden Zahlen nicht mehr erkannt werden. Es muss Zahlen mit entsprechend großer Komplexität geben, doch die Aussage "Die Zahl x hat eine Komplexität größer als L" ist bei den meisten Zahlen x nicht entscheidbar. Dies ist ein weiteres Beispiel für Gödels Unvollständigkeitssatz. Gregory Chaitin hat es einmal sinngemäß so ausgedrückt: "Man kann eine 10-Kilo-Aussage nicht mit einem 5-Kilo-Axiomensystem beweisen".

Warum ist das so?

Der Beweis verläuft wieder ähnlich zu den obigen Beweisen (siehe z.B. J. P. Lewis: Formally Unsolvable Problems in Software Engineering, http://www.idiom.com/~zilla/Work/Old/softEstimation28ja/ ): Zur Abkürzung bezeichnen im Folgenden wir mit H(x) die Komplexität der Zahl x. Nehmen wir an, wir könnten die Aussage H(x) > L für irgendeine Zahl x in unserem formalen System beweisen. Wir können das formale System als ein Programm betrachten, dass wohlgeformte Zeichenketten erzeugen und manipulieren kann. Das Programm verfügt dabei über Unterprogramme, die alle Regeln des formalen Systems repräsentieren. Die Axiome entsprechen gewissen Start-Zeichenketten, die dem Programm (z.B. in Form interner Konstanten) bekannt sind. Das Programm ist nun in der Lage, beliebig viele Beweise des formalen Systems in alphabetischer Reihenfolge, der Größe nach sortiert, zu erzeugen, denn in jedem formalen System gibt es nach Definition eine vollständige, unendlich lange Liste aller Beweise (siehe Kapitel 2.2). Wir können das Programm daher als Unterprogramm dazu verwenden, den Beweis zur Aussage H(x) > L zu suchen, und x anschließend auszugeben. Wenn es diesen Beweis gibt, so muss das Programm ihn nach endlich vielen Schritten in der Beweisliste finden können.

Nehmen wir an, das Unterprogramm, welches unser formales System repräsentiert, ist N Bit lang. Wir haben dieses Unterprogramm in ein etwas größeres Programm eingebunden, das die Aussage H(x) > L in der Beweisliste sucht, die vom Unterprogramm erzeugt wird, und das dann x ausgibt. Sagen wir, dieses Programm ist um k Bit länger als das Unterprogramm, d.h. das Programm hat eine Länge von N + k Bit. Man kann sich leicht vorstellen, dass bei umfangreichen formalen Systemen N sehr viel größer als k sein wird, denn der Überbau zum Durchsuchen der Beweisliste und Ausgeben von x wird gegenüber der Programmierung des kompletten formalen Systems kaum noch ins Gewicht fallen.

Wir setzen nun L gleich der Programmgröße N + k . Dann würde unser Programm eine Zahl x ausgeben, deren Komplexität laut Beweis größer als N + k ist, obwohl das Programm nur N + k Bit lang ist (d.h. die Komplexität der Zahl x kann höchstens N + k Bit betragen). Wir haben einen Widerspruch, der zeigt, dass es ein solches Programm nicht geben kann, und das bedeutet, dass das formale System die Aussage H(x) > L (mit L = N + k) für keine Zahl x beweisen kann. Das Durchsuchen der Beweisliste verläuft also erfolglos, und die Zahl x wird nicht ausgegeben.


Die obige Definition der Komplexität ist in dieser Form zunächst nur für Zahlen mit endlicher Binärdarstellung (oder analog für endliche Zeichenketten) anwendbar. Man kann den daraus abgeleiteten Begriff Zufälligkeit, den wir bisher nur für endliche natürliche Zahlen definiert haben, auf reelle Zahlen übertragen, die eine unendliche Anzahl von Dezimalstellen hinter dem Komma besitzen können.

Zunächst einmal ist klar, dass sich der Begriff unmittelbar auf reelle Zahlen übertragen lässt, die nur endlich viele Dezimalstellen hinter dem Komma haben. Das Dezimalkomma spielt keine Rolle - wichtig ist, dass sich die Zahl als endliche Zeichenkette darstellen lässt, die von Programmen ggf. ausgegeben werden kann.

Wie sieht es nun aus, wenn unendlich viele Dezimalstellen möglich sind, so wie bei unserem Eingangsbeispiel (der Zahl Pi)?

Zunächst einmal spielt das Dezimalkomma wieder keine Rolle, d.h. wir lassen es einfach weg und betrachten die Zahl einfach als unendlich lange Zeichenkette, wobei wir die Zahl als Binärstring schreiben wollen (d.h. in der Form "1001101..."). Bei dieser Zeichenkette (nennen wir sie Z) können wir nun vorne anfangen, die ersten n Zeichen betrachten und untersuchen, welche Komplexität diese Zeichenkette (nennen wir sie Zn) besitzt.

Nun wird die Komplexität der einzelnen Zeichenketten Zn mit wachsender Länge der Zeichenkette sicher schwanken. Wenn die gesamte unendlich lange Zeichenkette Z jedoch zufällig genannt werden soll, so erwarten wir, dass die Komplexität der Binär-Zeichenkette aus den ersten n Zeichen ungefähr gleich der Länge dieser Zeichenkette (also gleich n) ist.

Wir wollen die Komplexität der Binär-Zeichenketten Zn mit H(Zn) bezeichnen. Für eine zufällige unendlich lange Zeichenkette Z erwarten wir also, dass H(Zn) ungefähr gleich n ist.

Dieses ungefähr kann man präzisieren. Sicher wird aufgrund der Schwankung in der Komplexität der einzelnen Teilzeichenketten Zn bei mancher Zeichenkette auch mal eine deutliche Abweichung der Komplexität von n vorkommen - die Komplexität kann gelegentlich deutlich kleiner als n sein, d.h. die Teilzeichenkette ist etwas weniger zufällig. Wir verlangen nun aber, dass diese Abweichung nicht beliebig groß werden darf. Es muss eine obere Grenze für die Abweichung der Komplexität von n geben. Präzise ausgedrückt bedeutet das:

Es ist interessant, dass bei den unendlich langen Zeichenketten der Begriff Zufälligkeit durch diese Festlegung ohne jede Unschärfe definiert ist. Bei den endlichen Zeichenketten gab es noch eine gewisse Unschärfe, denn man musste sagen, wie weit die Komplexität denn unterhalb der Bitlänge der Zeichenkette liegen darf, damit die Zeichenkette noch als zufällig angesehen werden kann. Bei den unendlich langen Zeichenketten fällt dagegen die maximale Abweichung c für hinreichend großen Zeichenkettenlängen n prozentual kaum noch ins Gewicht, d.h. in diesem Sinne ist dann bei hinreichend langen Teilzeichenketten H(Zn) ungefähr gleich n. Deshalb ist es im Grenzfall unendlich langer Zeichenketten egal, wie groß die maximale Abweichung c ist. Sie muss nur endlich sein und darf nicht mit der Zeichenkettenlänge n anwachsen.

Mit Hilfe dieser Definition kann man nun beispielsweise zeigen, dass unser Eingangsbeispiel Pi nicht zufällig ist. Die Programme, die zur Ausgabe der ersten n Stellen von Pi benötigt werden, sind bei großen n alle deutlich kleiner als n, wobei es keine maximale Abweichung c gibt. Je größer n wird, umso größer wird auch die Abweichung zwischen Programmlänge und n (die Programmlänge wächst nur ungefähr logarithmisch mit n).

Wir sind nun gerüstet, um uns im folgenden Kapitel einer naheliegenden Frage zuzuwenden: Ist es möglich, eine Zufallszahl mathematisch zu konstruieren, ohne dass diese Konstruktionsvorschrift eine Komprimierung der Zahl zulässt? Wir dürfen gespannt sein, ob das möglich ist.


zurück zum Inhaltsverzeichnis

last modified on 16 December 2008