Problemet med datakomprimering kan i sin enkleste form relatere sig til tal og deres notationer. Tal kan angives med tal ("elleve" for tallet 11), matematiske udtryk ("to i det tyvende" for 1048576), strengudtryk ("fem niere" for 99999), egennavne ("dyrets nummer" for 666,- "år for Turings død" for 1954), eller vilkårlige kombinationer deraf. Enhver betegnelse er egnet, hvorved samtalepartneren klart kan bestemme, hvilket nummer vi taler om. Sig det selvfølgelig til din samtalepartner "faktor af otte" mere effektiv end tilsvarende notation "fyrre tusinde tre hundrede og tyve". Et logisk spørgsmål opstår her: hvad er den korteste notation for et givet tal?
Filosoffen Bertrand Russell udgav i 1908 , som berører spørgsmålet om talnotation fra den modsatte side: Hvad er det mindste tal, der ikke kræver firs bogstaver?
Et sådant tal skal eksistere: Fra firs russiske bogstaver og mellemrum kan du kun lave 3480 betegnelser, hvilket betyder, at du ved at bruge firs bogstaver ikke kan angive mere end 3480 tal. Det betyder, at det på denne måde er umuligt at udpege et bestemt tal, der ikke er mere end 3480.
Det betyder, at dette tal vil svare til betegnelsen "det mindste tal, som firs bogstaver ikke er nok til", som kun har 78 bogstaver! På den ene side skal dette nummer eksistere; på den anden side, hvis dette nummer eksisterer, så svarer dets betegnelse ikke til det. Paradoks!
Den nemmeste måde at afvise dette paradoks på er at henvise til det uformelle ved verbale notationer. Som, hvis kun et specifikt defineret sæt udtryk var tilladt i notationen, så "det mindste tal, som firs bogstaver ikke er nok til" ville ikke være en gyldig notation, hvorimod praktisk nyttige notationer som "faktor af otte" ville forblive acceptabelt.
Er der formelle måder at beskrive rækkefølgen (algoritmen) af handlinger på tal? Der er, og i overflod - de kaldes programmeringssprog. I stedet for verbale notationer vil vi bruge programmer (for eksempel i Python), der viser de nødvendige tal. For eksempel er programmet egnet til fem niere print("9"*5). Vi vil fortsat være interesserede i det korteste program for et givet nummer. Længden af et sådant program kaldes tal; 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 et kilobyteprogram ikke er nok til at udlæse?
Vi vil ræsonnere på samme måde som før: Der er 2561024 kilobyte tekster, hvilket betyder at der ikke kan udskrives mere end 2561024 tal af kilobyte programmer. Det betyder, at et bestemt tal, der ikke er større end 2561024, ikke kan udledes på denne måde.
Men lad os skrive et program i Python, der genererer alle mulige kilobyte-tekster, kører dem til udførelse, og hvis de udsender et tal, så tilføjer dette nummer til ordbogen over tilgængelige. Efter at have kontrolleret alle 2561024 muligheder, uanset hvor lang tid det tager, leder programmet efter det mindste tal, der mangler i ordbogen, og udskriver det nummer. Det virker indlysende, at et sådant program vil passe ind i en kilobyte kode - og vil udsende det tal, der ikke kan udlæses af et kilobyte program!
Hvad er fangsten nu? Det kan ikke længere tilskrives notationens uformelle karakter!
Hvis du er forvirret over det faktum, at vores program vil kræve en astronomisk mængde hukommelse for at fungere - en ordbog (eller bitarray) med 2561024 elementer - så kan du gøre det samme uden det: for hvert af de 2561024 numre til gengæld , gennemgå alle 2561024 mulige programmer, indtil der ikke er et passende. Det gør ikke noget, at en sådan søgning vil vare meget længe: efter at have kontrolleret mindre end (2561024)2 par fra nummeret og programmet, vil den ende og finde det meget værdsatte nummer.
Eller bliver det ikke færdigt? Ja, blandt alle de programmer, der vil blive prøvet, vil der være while True: pass (og dets funktionelle analoger) - og sagen vil ikke gå længere end at teste sådan et program!
I modsætning til Berrys paradoks, hvor fangsten lå i notationens uformelle, har vi i det andet tilfælde en godt forklædt omformulering . Faktum er, at det er umuligt at bestemme dets output fra et program på en begrænset tid. Især Kolmogorov kompleksitet : der er ingen algoritme, der ville tillade, for et givet tal, at finde længden af det korteste program, der udskriver dette tal; hvilket betyder, at der ikke er nogen løsning på Berrys problem - at finde længden af den korteste verbale betegnelse for et givet tal.
Kilde: www.habr.com