Das Problem der Datenkomprimierung kann sich in seiner einfachsten Form auf Zahlen und ihre Notationen beziehen. Zahlen können durch Ziffern bezeichnet werden ("elf" für die Zahl 11), mathematische Ausdrücke („zwei im zwanzigsten“ für 1048576), Zeichenfolgenausdrücke („Fünf Neunen“ für 99999), Eigennamen ("nummer der Bestie" für 666, „Jahr von Turings Tod“ für 1954) oder beliebige Kombinationen davon. Geeignet ist jede Bezeichnung, anhand derer der Gesprächspartner eindeutig erkennen kann, um welche Zahl es sich handelt. Sagen Sie es natürlich Ihrem Gesprächspartner „Fakultät von acht“ effizienter als die entsprechende Notation „vierzigtausenddreihundertzwanzig“. Hier stellt sich eine logische Frage: Was ist die kürzeste Notation für eine bestimmte Zahl?
Der Philosoph Bertrand Russell veröffentlichte 1908 , der die Frage der Zahlenschreibweise von der anderen Seite berührt: Was ist die kleinste Zahl, für die keine achtzig Buchstaben erforderlich sind?
Eine solche Zahl muss existieren: Aus achtzig russischen Buchstaben und Leerzeichen können nur 3480 Bezeichnungen gebildet werden, was bedeutet, dass man mit achtzig Buchstaben nicht mehr als 3480 Zahlen bezeichnen kann. Dies bedeutet, dass es auf diese Weise unmöglich ist, eine bestimmte Nummer von höchstens 3480 zu benennen.
Dies bedeutet, dass diese Nummer der Bezeichnung entspricht „die kleinste Zahl, für die achtzig Buchstaben nicht ausreichen“, das nur 78 Buchstaben hat! Einerseits muss diese Nummer existieren; Existiert diese Nummer hingegen, dann stimmt ihre Bezeichnung nicht mit ihr überein. Paradox!
Der einfachste Weg, dieses Paradoxon zu verwerfen, besteht darin, auf die Informalität verbaler Notationen zu verweisen. Wenn beispielsweise nur ein speziell definierter Satz von Ausdrücken in der Notation zulässig wäre, dann „die kleinste Zahl, für die achtzig Buchstaben nicht ausreichen“ wäre keine gültige Notation, wohingegen praktisch nützliche Notationen wie „Fakultät von acht“ würde akzeptabel bleiben.
Gibt es formale Möglichkeiten, die Abfolge (den Algorithmus) von Aktionen auf Zahlen zu beschreiben? Es gibt sie, und zwar in Hülle und Fülle – sie werden Programmiersprachen genannt. Anstelle von verbalen Notationen verwenden wir Programme (z. B. in Python), die die erforderlichen Zahlen anzeigen. Für fünf Neuner ist das Programm beispielsweise geeignet print("9"*5). Wir werden weiterhin an dem kürzesten Programm für eine bestimmte Nummer interessiert sein. Die Länge eines solchen Programms wird aufgerufen Zahlen; Es ist die theoretische Grenze, bis zu der eine bestimmte Zahl komprimiert werden kann.
Anstelle von Berrys Paradoxon können wir nun ein ähnliches betrachten: Was ist die kleinste Zahl, die ein Kilobyte-Programm nicht ausgeben kann?
Wir werden wie zuvor argumentieren: Es gibt 2561024 Kilobyte-Texte, was bedeutet, dass von Kilobyte-Programmen nicht mehr als 2561024 Zahlen ausgegeben werden können. Dies bedeutet, dass eine bestimmte Zahl, die nicht größer als 2561024 ist, auf diese Weise nicht abgeleitet werden kann.
Aber schreiben wir ein Programm in Python, das alle möglichen Kilobyte-Texte generiert, sie zur Ausführung ausführt und, wenn sie eine Zahl ausgeben, diese Zahl dann zum Wörterbuch der erreichbaren Texte hinzufügt. Nachdem alle 2561024 Möglichkeiten überprüft wurden, sucht das Programm, egal wie lange es dauert, nach der kleinsten Zahl, die im Wörterbuch fehlt, und gibt diese Zahl aus. Es scheint offensichtlich, dass ein solches Programm in ein Kilobyte Code passt – und genau die Zahl ausgibt, die ein Kilobyte-Programm nicht ausgeben kann!
Was ist jetzt der Haken? Es kann nicht mehr auf die Informalität der Notation zurückgeführt werden!
Wenn Sie verwirrt sind, dass unser Programm eine astronomische Menge an Speicher benötigt, um zu funktionieren – ein Wörterbuch (oder Bit-Array) mit 2561024 Elementen –, dann können Sie das Gleiche auch ohne tun: für jede der 2561024 Zahlen der Reihe nach Gehen Sie alle 2561024 möglichen Programme durch, bis kein passendes mehr dabei ist. Es spielt keine Rolle, dass eine solche Suche sehr lange dauern wird: Nachdem weniger als (2561024)2 Paare aus der Nummer und dem Programm überprüft wurden, wird es beendet und die sehr geschätzte Nummer gefunden.
Oder wird es nicht enden? Tatsächlich wird es unter all den Programmen, die ausprobiert werden, eines geben while True: pass (und seine funktionalen Analoga) - und die Sache wird nicht über das Testen eines solchen Programms hinausgehen!
Im Gegensatz zu Berrys Paradoxon, wo der Haken in der Informalität der Notation lag, haben wir es im zweiten Fall mit einer gut getarnten Umformulierung zu tun . Tatsache ist, dass es unmöglich ist, die Ausgabe eines Programms in endlicher Zeit zu bestimmen. Insbesondere die Komplexität von Kolmogorov : Es gibt keinen Algorithmus, der es ermöglichen würde, für eine gegebene Zahl die Länge des kürzesten Programms zu ermitteln, das diese Zahl ausgibt; Das bedeutet, dass es keine Lösung für Berrys Problem gibt – die Länge der kürzesten verbalen Bezeichnung für eine gegebene Zahl zu finden.
Source: habr.com