Paradoxer om datakomprimering

Problemet med datakomprimering, i sin enklaste form, kan relatera till siffror och deras notationer. Siffror kan betecknas med siffror ("elva" för talet 11), matematiska uttryck ("två i den tjugonde" för 1048576), stränguttryck ("fem nior" för 99999), egennamn ("odjurets nummer" för 666, "Turings dödsår" för 1954), eller godtyckliga kombinationer därav. Varje beteckning är lämplig genom vilken samtalspartnern tydligt kan bestämma vilket nummer vi pratar om. Självklart, berätta för din samtalspartner "faktor av åtta" effektivare än motsvarande notation "fyrtio tusen tre hundra tjugo". En logisk fråga uppstår här: vad är den kortaste notationen för ett givet tal?

Filosofen Bertrand Russell publicerade 1908 "Berrys paradox", som berör frågan om nummernotation från motsatt sida: Vilket är den minsta siffran som inte kräver åttio bokstäver?
Ett sådant nummer måste finnas: från åttio ryska bokstäver och mellanslag kan du bara skapa 3480 beteckningar, vilket innebär att du med åttio bokstäver kan beteckna högst 3480 siffror. Detta innebär att det är omöjligt att ange ett visst antal högst 3480 på detta sätt.

Detta innebär att detta nummer kommer att motsvara beteckningen "den minsta siffran för vilken åttio bokstäver inte räcker", som bara har 78 bokstäver! Å ena sidan måste detta nummer finnas; å andra sidan, om detta nummer finns, så motsvarar dess beteckning inte det. Paradox!

Det enklaste sättet att avfärda denna paradox är att hänvisa till det informella i verbala notationer. Som, om bara en specifikt definierad uppsättning uttryck tillåts i notationen, då "den minsta siffran för vilken åttio bokstäver inte räcker" skulle inte vara en giltig notation, medan praktiskt användbara notationer som "faktor av åtta" skulle förbli acceptabelt.

Finns det formella sätt att beskriva sekvensen (algoritmen) av åtgärder på siffror? Det finns, och i överflöd – de kallas programmeringsspråk. Istället för verbala notationer kommer vi att använda program (till exempel i Python) som visar de nödvändiga siffrorna. Till exempel, för fem nior passar programmet print("9"*5). Vi kommer att fortsätta att vara intresserade av det kortaste programmet för ett givet nummer. Längden på ett sådant program kallas Kolmogorov komplexitet tal; det är den teoretiska gränsen till vilken ett givet tal kan komprimeras.

Istället för Berrys paradox kan vi nu överväga en liknande: Vilket är det minsta antal som ett kilobyteprogram inte räcker för att mata ut?

Vi kommer att resonera på samma sätt som tidigare: det finns 2561024 kilobyte texter, vilket innebär att inte mer än 2561024 nummer kan matas ut av kilobyteprogram. Detta innebär att ett visst antal som inte är större än 2561024 inte kan härledas på detta sätt.

Men låt oss skriva ett program i Python som genererar alla möjliga kilobytetexter, kör dem för exekvering, och om de matar ut ett nummer, lägger vi till det här numret i ordboken över tillgängliga. Efter att ha kontrollerat alla 2561024 XNUMX XNUMX möjligheter, oavsett hur lång tid det tar, letar programmet efter det minsta nummer som saknas i ordboken och skriver ut det numret. Det verkar uppenbart att ett sådant program kommer att passa in i en kilobyte kod - och kommer att mata ut just det antal som inte kan matas ut av ett kilobyteprogram!

Vad är haken nu? Det kan inte längre tillskrivas notationens informalitet!

Om du är förvirrad av det faktum att vårt program kommer att kräva en astronomisk mängd minne för att fungera - en ordbok (eller bitarray) med 2561024 element - så kan du göra samma sak utan det: för vart och ett av de 2561024 numren i sin tur , gå igenom alla 2561024 möjliga program, tills det inte finns något lämpligt. Det spelar ingen roll att en sådan sökning kommer att pågå väldigt länge: efter att ha kontrollerat mindre än (2561024)2 par från numret och programmet, kommer den att sluta och hitta det mycket omhuldade numret.

Eller kommer det inte att sluta? Det kommer faktiskt att finnas bland alla program som kommer att prövas while True: pass (och dess funktionella analoger) - och saken kommer inte att gå längre än att testa ett sådant program!

Till skillnad från Berrys paradox, där haken låg i notationens informalitet, har vi i det andra fallet en väl förtäckt omformulering "stoppa problem". Faktum är att det är omöjligt att bestämma dess produktion från ett program på en begränsad tid. I synnerhet Kolmogorov komplexitet oberäkningsbar: det finns ingen algoritm som skulle tillåta, för ett givet nummer, att hitta längden på det kortaste programmet som skriver ut detta nummer; vilket betyder att det inte finns någon lösning på Berrys problem - att hitta längden på den kortaste verbala beteckningen för ett givet nummer.

Källa: will.com