Paradoxer om datakomprimering

Oppgave med datakomprimering i sin enkleste form kan referere til tall og deres betegnelser. Tall kan betegnes med numeriske ord («elleve» for tallet 11), matematiske uttrykk («to opphøyd i tjue» for 1048576), strengeuttrykk («fem niere» for 99999), egennavn («dyrets tall» for 666, «året Turing døde» for 1954), eller vilkårlige kombinasjoner av dem. Enhver betegnelse som samtalepartneren kan entydig identifisere hvilket tall som menes, er gyldig. Det er åpenbart at det er mer effektivt å informere samtalepartneren om «faktoriell åtte» enn den tilsvarende betegnelsen «førti tusen tre hundre og tyve». Her oppstår det et logisk spørsmål: hva er den korteste betegnelsen for et gitt tall?

Filosofen Bertrand Russell publiserte i 1908 «Berry-paradokset», som tar opp spørsmålet om tallbetegnelser fra den motsatte siden: hva er det minste tallet som ikke kan betegnes med åtti bokstaver?
Et slikt tall må eksistere: av åtti russiske bokstaver og mellomrom kan man lage totalt 3480 betegnelser, noe som betyr at man ikke kan betegne mer enn 3480 tall med bruk av åtti bokstaver. Dermed er det umulig å betegne et tall som ikke er større enn 3480.

Dermed vil dette tallet ha betegnelsen «det minste tallet som ikke kan betegnes med åtti bokstaver», som inneholder bare 78 bokstaver! På den ene siden må dette tallet eksistere; på den andre siden, hvis dette tallet eksisterer, så samsvarer ikke betegnelsen med det. Et paradoks!

Den enkleste måten å avfeie dette paradokset på, er å referere til uformelle verbale betegnelser. Man kan si at hvis bare en spesifikk sett med uttrykk var tillatt i betegnelser, så «det minste tallet som ikke kan betegnes med åtti bokstaver» ville det ikke vært en gyldig betegnelse, mens prakiske nyttige betegnelser som «faktoriell åtte» ville forbli gyldige.

Finnes det formelle måter å beskrive sekvensen (algoritmen) av handlinger på tall? Ja, og i overflod - de kalles programmeringsspråk. La oss bruke programmer (for eksempel i Python) i stedet for verbale betegnelser, som kan skrive ut de nødvendige tallene. For eksempel, for fem niere, ville programmet print("9"*5). Vi vil fortsatt være interessert i den korteste programmet for et gitt tall. Lengden på et slikt program kalles Kolmogorov-kompleksitet til tallet; dette er det teoretiske grensepunktet for hvor mye et gitt tall kan komprimeres.

I stedet for Berry-paradokset kan vi nå vurdere et lignende: hva er det minste tallet som ikke kan skrives ut med et kilobyte-program?

Vi vil tenke likt som tidligere: det finnes 2561024 kilobyte-tekster, derfor kan kilobyte-programmer skrive ut ikke mer enn 2561024 tall. Det betyr at et visst tall, som ikke overstiger 2561024, ikke kan bli skrevet ut på denne måten.

Men vi skal skrive et Python-program som genererer alle mulige kilobyte-tekster, kjører dem, og hvis de skriver ut et tall, legger det tallet til en oppnåelig liste. Etter å ha sjekket alle 2561024 mulighetene, uansett hvor lang tid det måtte ta - programmet leter etter det minste tallet som mangler i listen, og skriver ut dette tallet. Det virker opplagt at et slikt program vil få plass innenfor en kilobyte kode - og det vil skrive ut det tallet som ikke kan skrives ut med et kilobyte-program!

Hva er så fellen nå? Den kan ikke lenger forklares ved uformelle betegnelser!

Hvis du er bekymret for at programmet vårt vil kreve en astronomisk mengde minne for å fungere - en ordliste (eller bitarray) av 2561024 elementer - så kan alt det samme gjøres uten det: for hvert av de 2561024 tallene, prøv alle 2561024 mulige programmer en etter en, til en passende program blir funnet. Det er ikke viktig at en slik prøving vil ta veldig lang tid: etter å ha sjekket mindre enn (2561024)2 par av et tall og et program vil det avsluttes, og finne det dyrebare tallet.

Eller vil det ikke avsluttes? For blant alle programmene som vil bli prøvd, vil vi møte while True: pass (og dens funksjonelle analoger) - og videre testing av et slikt program vil ikke føre noe sted!

I motsetning til Berry-paradokset, hvor fellen lå i de uformelle betegnelsene, har vi i dette tilfellet en godt kamuflert omformulering av «stoppproblemet». Saken er at det er umulig å fastslå et programs utdata på en endelig tid. Spesielt er Kolmogorov-kompleksitet uberegnelig: det finnes ingen algoritme som gjør det mulig å finne lengden på det korteste programmet som skriver ut et gitt tall; dermed finnes det heller ingen løsning for Berry-problemet — å finne lengden på den korteste verbale betegnelsen for et gitt tall.

Kilde: habr.com