Die Aufgabe der Datenkompression kann in ihrer einfachsten Form Zahlen und deren Bezeichnungen betreffen. Zahlen können durch Zahlwörter bezeichnet werden (âelfâ fĂŒr die Zahl 11), mathematische AusdrĂŒcke (âzwei hoch zwanzigâ fĂŒr 1048576), textuelle AusdrĂŒcke (âfĂŒnf Neunenâ fĂŒr 99999), Eigennamen (âZahl des Biestesâ fĂŒr 666, âJahr des Todes von Turingâ fĂŒr 1954), oder beliebigen Kombinationen davon. Jede Bezeichnung ist zulĂ€ssig, wenn der GesprĂ€chspartner eindeutig bestimmen kann, um welche Zahl es sich handelt. Offensichtlich ist es effektiver, dem GesprĂ€chspartner âFakultĂ€t von achtâ zu sagen als die Ă€quivalente Bezeichnung âvierzigtausenddreihundertzwanzigâ. Hier stellt sich die logische Frage: Welche Bezeichnung fĂŒr die gegebene Zahl ist die kĂŒrzeste?
Der Philosoph Bertrand Russell veröffentlichte 1908 , das die Frage der Bezeichnungen von Zahlen von der anderen Seite betrachtet: Welche ist die kleinste Zahl, fĂŒr die nicht genug achtzig Buchstaben zur VerfĂŒgung stehen?
Eine solche Zahl muss existieren: Aus achtzig russischen Buchstaben und Leerzeichen können insgesamt nur 3480 Bezeichnungen gebildet werden, was bedeutet, dass mit achtzig Buchstaben nicht mehr als 3480 Zahlen bezeichnet werden können. Das bedeutet, dass eine Zahl, die nicht gröĂer als 3480 ist, auf diese Weise nicht benannt werden kann.
Daher wird dieser Zahl die Bezeichnung âdie kleinste Zahl, fĂŒr die nicht genug achtzig Buchstaben zur VerfĂŒgung stehenâzugeordnet, die insgesamt 78 Buchstaben hat! Einerseits muss diese Zahl existieren; andererseits, wenn diese Zahl existiert, dann stimmt ihre Bezeichnung nicht mit ihr ĂŒberein. Ein Paradoxon!
Der einfachste Weg, dieses Paradoxon abzutun, ist, auf die InformalitĂ€t der verbalen Bezeichnungen zu verweisen. Man könnte sagen, dass, wenn nur eine konkret definierte Sammlung von AusdrĂŒcken als Bezeichnungen zulĂ€ssig wĂ€re, dann âdie kleinste Zahl, fĂŒr die nicht genug achtzig Buchstaben zur VerfĂŒgung stehenâ nicht als zulĂ€ssige Bezeichnung gĂ€lte, wĂ€hrend praktisch nĂŒtzliche Bezeichnungen wie âFakultĂ€t von achtâ zulĂ€ssig blieben.
Gibt es formale Methoden zur Beschreibung der Abfolge (Algorithmus) von Handlungen mit Zahlen? Ja, und in HĂŒlle und FĂŒlle â diese werden Programmiersprachen genannt. Lassen Sie uns anstelle von verbalen Bezeichnungen Programme verwenden (zum Beispiel in Python), die die benötigten Zahlen ausgeben. Zum Beispiel eignet sich fĂŒr fĂŒnf Neunen das Programm print("9"*5). Wir werden weiterhin an dem kĂŒrzesten Programm fĂŒr eine gegebene Zahl interessiert sein. Die LĂ€nge eines solchen Programms wird der Zahl bezeichnet; dies ist die theoretische Grenze, bis zu der eine gegebene Zahl komprimiert werden kann.
Anstelle des Berry-Paradoxons können wir jetzt ein Ă€hnliches betrachten: Was ist die kleinste Zahl, fĂŒr die ein kilobyte-Programm nicht ausreicht, um sie auszugeben?
Wir werden die Ăberlegungen wie zuvor anstellen: Es gibt 2561024 kilobyte groĂe Texte, das bedeutet, dass mit kilobyte-Programmen nicht mehr als 2561024 Zahlen ausgegeben werden können. Das bedeutet, dass eine Zahl, die nicht gröĂer als 2561024 ist, auf diese Weise nicht ausgegeben werden kann.
Aber wir werden ein Python-Programm schreiben, das alle möglichen kilobyte-Texte generiert, sie ausfĂŒhrt, und wenn sie eine Zahl ausgeben â fĂŒgt es diese Zahl dem erreichbaren Wörterbuch hinzu. Nach der PrĂŒfung aller 2561024 Möglichkeiten, egal wie lange das dauert â 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 passt â und diejenige Zahl ausgibt, die mit einem kilobyte-Programm nicht ausgegeben werden kann!
Was ist also der Haken jetzt? Man kann ihn nicht mehr auf die UnformalitÀt der Bezeichnungen schieben!
Wenn Sie sich Sorgen machen, dass unser Programm astronomisch viel Speicher benötigt, um zu arbeiten â ein Wörterbuch (oder ein Bit-Array) aus 2561024 Elementen â dann kann man das alles auch ohne es umsetzen: Man kann fĂŒr jede der 2561024 Zahlen nacheinander alle 2561024 möglichen Programme durchprobieren, bis man ein passendes findet. Es spielt keine Rolle, dass ein solches Durchprobieren sehr lange dauern wird: Nach der ĂberprĂŒfung von weniger als (2561024)2 Paaren aus Zahl und Programm wird es schlieĂlich enden und die besagte Zahl finden.
Oder wird es nicht enden? Denn unter all den Programmen, die ausprobiert werden, wird man while True: pass (und ihre funktionalen Analoga) treffen â und dann wird die ĂberprĂŒfung eines solchen Programms bereits nicht weitergehen!
Im Gegensatz zum Berry-Paradoxon, in dem der Haken in der UnformalitĂ€t der Bezeichnungen lag, haben wir im zweiten Fall eine gut maskierte Umformulierung der . Das Problem ist, dass man mit einem Programm nicht in endlicher Zeit dessen Ausgabe bestimmen kann. 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; das bedeutet, es gibt keine Lösung fĂŒr die Berry-Aufgabe â die LĂ€nge der kĂŒrzesten verbalen Bezeichnung fĂŒr eine gegebene Zahl zu finden.
Quelle: habr.com
