Die Aufgabe der Datenkomprimierung in ihrer einfachsten Form kann sich auf Zahlen und deren Notation beziehen. Zahlen können durch Ziffern (
"elf" für die Zahl 11), mathematische Ausdrücke (
"zwei im zwanzigsten" für 1048576), Zeichenfolgenausdrücke (
"fünf Neunen" für 99999), Eigennamen (
"die Zahl des Tieres" für 666,
"das Jahr von Turings Tod" bezeichnet werden " Für 1954) oder ihre willkürlichen Kombinationen. Jede Bezeichnung, anhand derer der Gesprächspartner eindeutig bestimmen kann, welche Art von Sprache geeignet ist, ist geeignet. Offensichtlich
ist es effektiver, den Gesprächspartner über
„Fakultät Acht“ zu informieren, als über die entsprechende Bezeichnung
„Vierzigtausenddreihundertzwanzig“ . Dies wirft die logische Frage auf: Was ist die kürzeste Bezeichnung für eine bestimmte Nummer?
Der Philosoph Bertrand Russell veröffentlichte 1908 das
„Berry Paradox“, das sich mit der Notation von Zahlen auf der gegenüberliegenden Seite befasst:
Was ist die kleinste Zahl, um anzuzeigen, welche achtzig Buchstaben nicht ausreichen?Eine solche Zahl muss existieren: Aus achtzig russischen Buchstaben und Leerzeichen können Sie insgesamt 34
80 Bezeichnungen machen, was bedeutet, dass Sie mit achtzig Buchstaben nicht mehr als 34
80 Zahlen bezeichnen können. Daher kann eine bestimmte Anzahl, nicht mehr als 34
80 , auf diese Weise nicht bezeichnet werden.
Dies bedeutet, dass die Bezeichnung
„die kleinste Zahl, für die achtzig Buchstaben nicht ausreichen“ dieser Zahl entspricht, in der es nur 78 Buchstaben gibt! Einerseits muss diese Nummer existieren; Wenn andererseits diese Nummer existiert, entspricht ihre Bezeichnung nicht dieser. Paradox!
Der einfachste Weg, dieses Paradoxon zu verwerfen, besteht darin, sich auf die Informalität verbaler Bezeichnungen zu beziehen. Wenn in der Notation nur ein bestimmter Satz von Ausdrücken zulässig wäre, wäre
„die kleinste Zahl, für die achtzig Buchstaben nicht
ausreichen“ keine gültige Bezeichnung, während praktisch nützliche Bezeichnungen vom
Typ „Fakultät acht“ gültig bleiben würden.
Gibt es formale Möglichkeiten, die Reihenfolge (den Algorithmus) von Aktionen auf Zahlen zu beschreiben? Es gibt und im Überfluss - sie werden Programmiersprachen genannt. Anstelle der verbalen Notation verwenden wir Programme (z. B. in Python), die die erforderlichen Zahlen drucken. Beispielsweise ist für fünf Neunen das
print("9"*5) geeignet. Wir werden weiterhin an dem kürzesten Programm für eine bestimmte Anzahl interessiert sein. Die Länge eines solchen Programms wird als
Kolmogorov-Komplexität der Zahl bezeichnet; Dies ist die theoretische Grenze, bis zu der eine bestimmte Zahl komprimiert werden kann.
Anstelle des Berry-Paradoxons kann man nun ein ähnliches betrachten:
Was ist die kleinste Zahl, für die ein Kilobyte-Programm nicht ausreicht?Wir werden auf die gleiche Weise wie zuvor argumentieren: Es gibt
256.1024 Kilobyte-Texte, was bedeutet, dass in Kilobyte-Programmen nicht mehr als
256.224 Zahlen angezeigt werden können. Dies bedeutet, dass eine bestimmte Zahl, die nicht größer als 256
1024 ist , auf diese Weise nicht abgeleitet werden kann.
Wir schreiben jedoch in Python ein Programm, das alle möglichen Kilobyte-Texte generiert, zur Ausführung startet und diese Nummer dem erreichbaren Wörterbuch hinzufügt, wenn sie eine bestimmte Nummer drucken. Nachdem alle 256
1024 Möglichkeiten überprüft wurden, sucht das Programm nach der kleinsten Nummer, die nicht im Wörterbuch enthalten ist, und zeigt diese Nummer an. Es scheint offensichtlich, dass ein solches Programm in ein Kilobyte Code passt - und genau die Zahl ausgibt, die in einem Kilobyte-Programm nicht angezeigt werden kann!
Was ist jetzt der Haken? Es kann nicht mehr auf die Informalität der Notation zurückgeführt werden!
Wenn Sie sich nicht sicher sind, ob für unser Programm eine astronomische Speichermenge erforderlich ist - ein Wörterbuch (oder eine Bitmap) mit 256
1024 Elementen -, können Sie dasselbe auch tun: Durchlaufen Sie für jede der 256
1024 Zahlen alle 256
1024 möglichen Zahlen Programme, bis ein geeignetes gefunden wird. Es spielt keine Rolle, dass eine solche Aufzählung sehr lange dauert: Nachdem weniger als (256
1024 )
2 Paare aus der Nummer und dem Programm überprüft wurden, endet sie und findet diese sehr geschätzte Nummer.
Oder wird es nicht enden? In der Tat wird es unter allen Programmen, die ausprobiert werden,
while True: pass (und seine funktionalen Gegenstücke) geben - und die Dinge werden nicht über die Überprüfung eines solchen Programms hinausgehen!
Im Gegensatz zum Berry-Paradoxon, bei dem der Haken in der Informalität der Notation lag, haben wir im zweiten Fall eine gut getarnte Neuformulierung des
„Stopp-Problems“ . Tatsache ist, dass es laut Programm unmöglich ist, den Abschluss in einer endlichen Zeit zu bestimmen. Insbesondere ist die Kolmogorov-Komplexität nicht
berechenbar : Es gibt keinen Algorithmus, mit dem eine bestimmte Zahl die Länge des kürzesten Programms ermitteln könnte, das diese Zahl ausgibt. was bedeutet, dass es keine Lösung für das Berry-Problem gibt - für eine bestimmte Zahl die Länge der kürzesten Wortbezeichnung zu finden.