Problemet med datakomprimering, i sin enkleste form, kan relateres til tall og deres notasjoner. Tall kan angis med tall ("elleve" for tallet 11), matematiske uttrykk ("to i det tjuende" for 1048576), strenguttrykk ("fem niere" for 99999), egennavn ("nummer på udyret" for 666, "år for Turings død" for 1954), eller vilkårlige kombinasjoner derav. Enhver betegnelse er egnet som samtalepartneren tydelig kan bestemme hvilket nummer vi snakker om. Selvfølgelig, fortell samtalepartneren din "faktor av åtte" mer effektiv enn tilsvarende notasjon "førti tusen tre hundre og tjue". Et logisk spørsmål oppstår her: hva er den korteste notasjonen for et gitt tall?
Filosofen Bertrand Russell publiserte i 1908 , som berører spørsmålet om tallnotasjon fra motsatt side: Hva er det minste tallet som ikke krever åtti bokstaver?
Et slikt tall må eksistere: fra åtti russiske bokstaver og mellomrom kan du bare lage 3480 betegnelser, noe som betyr at ved å bruke åtti bokstaver kan du ikke angi mer enn 3480 tall. Dette betyr at det er umulig å angi et visst tall som ikke er mer enn 3480 på denne måten.
Dette betyr at dette tallet vil samsvare med betegnelsen "det minste tallet som åtti bokstaver ikke er nok for", som bare har 78 bokstaver! På den ene siden må dette nummeret eksistere; på den annen side, hvis dette nummeret eksisterer, samsvarer ikke betegnelsen med det. Paradoks!
Den enkleste måten å avvise dette paradokset på er å referere til det uformelle ved verbale notasjoner. Som, hvis bare et spesifikt definert sett med uttrykk var tillatt i notasjonen, da "det minste tallet som åtti bokstaver ikke er nok for" ville ikke være en gyldig notasjon, mens praktisk talt nyttige notasjoner som "faktor av åtte" vil forbli akseptabelt.
Finnes det formelle måter å beskrive sekvensen (algoritmen) av handlinger på tall? Det finnes, og i overflod – de kalles programmeringsspråk. I stedet for verbale notasjoner vil vi bruke programmer (for eksempel i Python) som viser de nødvendige tallene. For eksempel, for fem niere er programmet egnet print("9"*5). Vi vil fortsatt være interessert i det korteste programmet for et gitt nummer. Lengden på et slikt program kalles tall; det er den teoretiske grensen som et gitt tall kan komprimeres til.
I stedet for Berrys paradoks, kan vi nå vurdere et lignende: Hva er det minste tallet som et kilobyteprogram ikke er nok til å sende ut?
Vi vil resonnere på samme måte som før: det er 2561024 kilobyte tekster, noe som betyr at ikke mer enn 2561024 tall kan skrives ut av kilobyte programmer. Dette betyr at et visst tall som ikke er større enn 2561024 ikke kan utledes på denne måten.
Men la oss skrive et program i Python som genererer alle mulige kilobyte-tekster, kjører dem for utførelse, og hvis de sender ut et tall, legger du dette nummeret til ordboken over tilgjengelige. Etter å ha sjekket alle 2561024 XNUMX XNUMX muligheter, uansett hvor lang tid det tar, ser programmet etter det minste tallet som mangler i ordboken og skriver ut det nummeret. Det virker åpenbart at et slikt program vil passe inn i en kilobyte med kode - og vil gi ut det tallet som ikke kan skrives ut av et kilobyteprogram!
Hva er fangsten nå? Det kan ikke lenger tilskrives notasjonens uformelle!
Hvis du er forvirret av det faktum at programmet vårt vil kreve en astronomisk mengde minne for å fungere - en ordbok (eller bitarray) med 2561024 elementer - så kan du gjøre det samme uten det: for hvert av de 2561024 tallene i sin tur , gå gjennom alle 2561024 mulige programmer, til det ikke er noe passende. Det spiller ingen rolle at et slikt søk vil vare veldig lenge: etter å ha sjekket mindre enn (2561024)2 par fra nummeret og programmet, vil det avsluttes og finne det veldig kjære nummeret.
Eller blir det ikke ferdig? Faktisk, blant alle programmene som vil bli prøvd, vil det være while True: pass (og dets funksjonelle analoger) - og saken vil ikke gå lenger enn å teste et slikt program!
I motsetning til Berrys paradoks, hvor fangsten lå i det uformelle i notasjonen, har vi i det andre tilfellet en godt forkledd omformulering . Faktum er at det er umulig å bestemme utgangen fra et program på en begrenset tid. Spesielt Kolmogorov kompleksitet : det er ingen algoritme som vil tillate, for et gitt tall, å finne lengden på det korteste programmet som skriver ut dette nummeret; som betyr at det ikke er noen løsning på Berrys problem - å finne lengden på den korteste verbale betegnelsen for et gitt tall.
Kilde: www.habr.com