Einige kombinatorische Überlegungen

Es gibt 2ⁿ verschiedene binäre Zeichenketten der Länge n. Da jede Zeichenkette zu ihrer Konstruktion ein anderes Programm erfordert, gibt es stets einige Zeichenketten der Länge n, deren Kolmogoroffkomplexität mindestens n ist. Weiterhin läßt sich zeigen, daß sogar die allermeisten Zeichenketten der Länge n eine Kolmogoroffkomplexität der Größenordnung n haben.

Interessanterweise läßt sich erkennen, daß es stets eine Zeichenkette Z der Länge n gibt, wobei K(Z) mindestens n ist, während sich ein solches Z nicht für den allgemeinen Fall konkret angeben läßt - auch keine allgemeine Konstruktionsvorschrift ! Dies rührt daher, daß die kürzeste Beschreibung von Znach Definition gerade mindestens von der Länge n ist, mithin es kein allgemeines Schema von konstanter Länge geben kann, nach dem sich Z für ein beliebiges n bestimmen läßt.

Dieser Sachverhalt läßt bestimmte Parallelen zu dem Gödelschen Theorem^4.16 über die Unvollständigkeit von Axiomensystemen für die elementaren Arithmetik erkennen Gödel[Göd31]. Dort zeigte Gödel, daß es für jedes mögliche, widerspruchsfreie Axiomensystem A stets wahre Sätze der elementaren Arithmetik gibt, die sich aus A nicht ableiten lassen. In der Tat gelang es Chaitin, das Gödelsche Unvollständigkeitstheorem mit Hilfe der algorithmischen Informationstheorie zu beweisen Chaitin[Cha74].  

Beispiele: Zeichenketten wie `11111111', `000000000000000' oder `101010101010101010' etc. sind einfache Zeichenketten, die sich mittels eines kurzen Programms konstruieren lassen. Ein derartiges Programm muß im wesentlichen nur die Länge der Zeichenkette beinhalten; also höchstens $\log_{2}$ (Länge(Z)) Binärzeichen lang sein, sowie noch ein bis zwei weitere Zeichen beinhalten, die bestimmen, ob Einsen oder Nullen ausgedruckt werden sollen. Je nach dem wie lang eine Zeichenkette ist, läßt sich ihre Länge auch noch kürzer darstellen, beispielsweise wie bei den folgenden Zahlen: 10¹⁰, 9⁽⁹⁹⁾, etc.

Dagegen sind Zeichenketten wie `100001111010010101010111010110101101111000010...' oder `10011010010010110111101101011101010010...' komplizierter, d.h. sie haben eine größere Kolmogoroffkomplexität, da zur Beschreibung solcher Zeichenketten die Angabe ihrer Länge bei weitem nicht ausreicht.

Für die folgenden Ausführungen ist bemerkenswert, daß Zeichenketten, insbesondere endliche Zeichenketten auf sehr verschiedene Weisen algorithmisch beschrieben werden können.

0 1 0 0 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 ...

Dies kann wie folgt beschrieben werden:

1.

Es stehen überall Nullen, außer an den Stellen 2, 6, 7, 9, 10, 11, 12, 16, 17, ...

2.

Es stehen alternierend jeweils 2 Einsen und 3 Nullen; Ausnahmen sind die Stellen 1, 9, 10, ...