Opgaven til komprimering af data i sin enkleste form kan relateres til tal og deres repræsentationer. Tal kan repræsenteres med numeriske betegnelser ("elleve" for tallet 11), matematiske udtryk ("to til den tyvende" for 1048576), strengudtryk ("fem niere" for 99999), egennavne ("dyrets tal" for 666, "året for Turing's død" for 1954), eller en vilkårlig kombination af dem. Enhver betegnelse, der gør det muligt for samtalepartneren entydigt at bestemme, hvilket tal der menes, er anvendelig. Det er åbenlyst, at det er mere effektivt at informere samtalepartneren om "faktorialen af otte" end den tilsvarende betegnelse "fyrre tusinde treogtyve". Her opstår et logisk spørgsmål: hvilken betegnelse for et givet tal er den korteste?
Filosof Bertrand Russell offentliggjorde i 1908 , som berører spørgsmålet om betegnelser for tal fra den modsatte vinkel: hvad er det mindste tal, som ikke kan betegnes med færre end firs bogstaver?
Et sådant tal må eksistere: Af firs russiske bogstaver og mellemrum kan der kun dannes 3480 betegnelser, så med brug af firs bogstaver kan man maksimalt betegne 3480 tal. Dette betyder, at et tal, der er mindre eller lig med 3480, ikke kan betegnes på denne måde.
Det betyder, at dette tal vil blive repræsenteret med betegnelsen "det mindste tal, som ikke kan betegnes med færre end firs bogstaver", som har i alt 78 bogstaver! På den ene side må dette tal eksistere; på den anden side, hvis dette tal eksisterer, så stemmer dets betegnelse ikke overens med det. Et paradoks!
Den enkleste måde at feje dette paradoks væk på er at henvise til uformelle verbale betegnelser. Man kan sige, at hvis der kun blev tilladt et specifikt sæt udtryk i betegnelse, så "det mindste tal, som ikke kan betegnes med færre end firs bogstaver" ikke ville være en gyldig betegnelse, mens praktisk nyttige betegnelser som "faktorialen af otte" ville forblive gyldige.
Er der formelle måder at beskrive sekvenser (algoritmer) af handlinger med tal? Ja, og der er rigeligt — de kaldes programmeringssprog. Lad os i stedet for verbale betegnelser bruge programmer (f.eks. i Python), der udskriver de ønskede tal. For eksempel vil programmet print("9"*5). Vi vil stadig være interesseret i det korteste program for et givet tal. Længden af et sådant program kaldes af tallet; det er den teoretiske grænse, hvortil et givet tal kan komprimeres.
I stedet for Berrys paradoks kan vi nu overveje et lignende: hvad er det mindste tal, som ikke kan udskrives af et kilobyte-program?
Vi vil ræsonnere på samme måde som før: der findes 2561024 kilobyte-tekster, hvilket betyder, at ikke mere end 2561024 tal kan genereres med kilobyte-programmer. Dermed er der et tal, som ikke kan genereres på denne måde, og som ikke er større end 2561024.
Men lad os skrive et Python-program, der genererer alle mulige kilobyte-tekster, kører dem og, hvis de udskriver et tal, så tilføjer det tal til en opnåelig ordbog. Efter at have kontrolleret alle 2561024 muligheder, hvor lang tid det end måtte tage, vil programmet finde det mindste tal, der er fraværende i ordbogen, og udskrive dette tal. Det virker indlysende, at et sådant program vil holde sig inden for en kilobyte kode — og vil udskrive det tal, som ikke kan udskrives af et kilobyte-program!
Men hvad er fælden nu? Det er ikke længere muligt at afskrive det på grund af uformelle betegnelser!
Hvis det forvirrer dig, at vores program kræver en astronomisk mængde hukommelse for at køre — en ordbog (eller bit-array) med 2561024 elementer — så kan alt det samme også gøres uden det: for hvert af de 2561024 tal kan vi se på alle 2561024 mulige programmer én ad gangen, indtil vi finder en passende. Det betyder ikke noget, at en sådan gennemgang vil tage meget lang tid: efter mindre end (2561024)2 par af tal og programmer vil det jo ende, og finde det eftertragtede tal.
Eller vil det ikke ende? For blandt alle de programmer, der vil blive afprøvet, vil vi støde på while True: pass (og dens funktionelle ækvivalenter) — og derefter vil kontrol af et sådant program ikke kunne fortsætte!
I modsætning til Berrys paradoks, hvor fælden var i de uformelle betegnelser, har vi i dette tilfælde en godt camoufleret omformulering af . Det er umuligt at bestemme udfaldet af programmet inden for en endelig tid. Specifikt er Kolmogorov-kompleksiteten : der er ingen algoritme, der gør det muligt at finde længden af det korteste program, der udskriver et givet tal; derfor er der heller ikke nogen løsning på Berry's problem — at finde længden af den korteste verbale betegnelse for et givet tal.
Kilde: habr.com
