Die Aufgabe der Datenkompression kann in ihrer einfachsten Form auf Zahlen und deren Bezeichnungen bezogen werden. Zahlen können mit numerischen Wörtern („elf“ für die Zahl 11), mathematischen Ausdrücken („zwei hoch zwanzig“ für 1048576), Zeichenfolgen („fünf Neunern“ für 99999), Eigennamen („Zahl des Tieres“ für 666, „Jahr des Todes von Turing“ für 1954) oder beliebigen Kombinationen davon bezeichnet werden. Jegliche Bezeichnung, die es dem Gesprächspartner ermöglicht, eindeutig zu bestimmen, von welcher Zahl die Rede ist, ist zulässig. Offensichtlich ist es effektiver, dem Gesprächspartner zu sagen „Fakultät von acht“ als die äquivalente Bezeichnung „vierzigtausenddreihundertzwanzig“. Hier stellt sich die logische Frage: Welche Bezeichnung für eine gegebene Zahl ist die kürzeste?
Der Philosoph Bertrand Russell veröffentlichte 1908 , das die Frage der Zahlbezeichnungen von der entgegengesetzten Seite betrachtet: Welches ist die kleinste Zahl, für die nicht achtzig Buchstaben ausreichen?
Eine solche Zahl muss existieren: Aus achtzig russischen Buchstaben und Leerzeichen können insgesamt nur 3480 Bezeichnungen gebildet werden, was bedeutet, dass mit den achtzig Buchstaben nicht mehr als 3480 Zahlen bezeichnet werden können. Somit ist es unmöglich, eine bestimmte Zahl, die kleiner oder gleich 3480 ist, auf diese Weise zu bezeichnen.
Daher wird dieses Zahl eine Bezeichnung erhalten „die kleinste Zahl, für die nicht ausreichend achtzig Buchstaben zur Verfügung stehen“, die nur 78 Buchstaben umfasst! Einerseits muss diese Zahl existieren; andererseits, wenn diese Zahl existiert, dann entspricht ihre Bezeichnung nicht ihr. Ein Paradoxon!
Der einfachste Weg, dieses Paradoxon abzutun, ist, sich auf die Unformalität sprachlicher Bezeichnungen zu berufen. Es wäre sozusagen nicht zulässig, nur einen konkret definierten Satz von Ausdrücken zuzulassen, denn „die kleinste Zahl, für die nicht ausreichend achtzig Buchstaben zur Verfügung stehen“ wäre keine zulässige Bezeichnung, während praktisch nützliche Bezeichnungen wie „Fakultät von acht“ zulässig bleiben würden.
Gibt es formale Möglichkeiten, die Abfolge von Aktionen mit Zahlen zu beschreiben? Ja, und zwar reichlich – diese werden Programmiersprachen genannt. Statt schriftlicher Bezeichnungen verwenden wir Programme (zum Beispiel in Python), die die gewünschten Zahlen ausgeben. Beispielsweise könnte folgendes Programm für fünf Neunen verwendet werden: print("9"*5). Auch hier interessiert uns weiterhin das kürzeste Programm für eine gegebene Zahl. Die Länge eines solchen Programms bezeichnet man als der Zahl; dies ist die theoretische Grenze, bis zu der eine bestimmte Zahl komprimiert werden kann.
Anstelle des Berry-Paradoxons können wir jetzt ein ähnliches betrachten: Welches ist die kleinste Zahl, für die ein Kilobyte-Programm nicht ausreicht, um sie auszugeben?
Wir werden ebenso argumentieren wie zuvor: Es gibt 2561024 Kilobyte-Textinhalte, das heißt, mit Kilobyte-Programmen können nicht mehr als 2561024 Zahlen ausgegeben werden. Das bedeutet, dass eine bestimmte Zahl, die nicht größer als 2561024 ist, auf diese Weise nicht ausgegeben werden kann.
Aber wir schreiben ein Programm in Python, das alle möglichen Kilobyte-Texte generiert, sie zur Ausführung bringt und, falls sie eine Zahl ausgeben, diese Zahl dem Wörterbuch der erreichbaren Zahlen hinzufügt. Nachdem alle 2561024 Möglichkeiten überprüft sind, egal wie viel Zeit das in Anspruch nimmt – sucht das Programm nach der kleinsten Zahl, die im Wörterbuch fehlt, und gibt diese Zahl aus. Es scheint offensichtlich, dass ein solches Programm in einem Kilobyte Code Platz finden kann und genau die Zahl ausgeben wird, die mit einem Kilobyte Programm nicht ausgegeben werden kann!
Was ist jetzt der Haken? Man kann die Informalität der Bezeichnungen jetzt nicht mehr darauf abwälzen!
Wenn Sie besorgt sind, dass unser Programm eine astronomische Menge an Speicher für die Ausführung benötigt – ein Wörterbuch (oder Bit-Array) aus 2561024 Elementen – dann kann man all das auch ohne erreichen: Für jede der 2561024 Zahlen nacheinander alle 2561024 möglichen Programme durchprobieren, bis das passende gefunden wird. Es ist unerheblich, dass ein solcher Versuch sehr lange dauern wird: Nach der Überprüfung von weniger als (2561024)2 Paaren aus Zahl und Programm wird es schließlich enden und diese eine geheime Zahl finden.
Oder wird es nicht enden? Denn unter all den Programmen, die ausprobiert werden, trifft man auf while True: pass (und ihre funktionalen Analogien) – und damit wird die Prüfung eines solchen Programms nicht vorankommen!
Im Gegensatz zum Berry-Paradoxon, wo die Irreführung in der Unformalität der Bezeichnungen lag, haben wir hier eine gut getarnte Umformulierung . Die Sache ist die, dass es für das Programm unmöglich ist, innerhalb einer endlichen Zeit dessen Ausgabe zu bestimmen. Insbesondere ist die kolmogorovsche Komplexität : Es gibt keinen Algorithmus, der es ermöglicht, für eine gegebene Zahl die Länge des kürzesten Programms zu finden, das diese Zahl ausgibt; somit gibt es auch keine Lösung für das Berry-Problem – die Länge der kürzesten verbalen Bezeichnung für eine gegebene Zahl zu finden.
Quelle: habr.com
