Problema compresiei datelor, în forma sa cea mai simplă, se poate referi la numere și la notațiile acestora. Numerele pot fi notate cu cifre ("unsprezece" pentru numărul 11), expresii matematice („doi în al douăzecilea” pentru 1048576), expresii șir („cinci nouă” pentru 99999), nume proprii („numărul fiarei” pentru 666, „Anul morții lui Turing” pentru 1954), sau combinații arbitrare ale acestora. Este potrivită orice denumire prin care interlocutorul poate determina clar despre ce număr vorbim. Evident, spune-i interlocutorului tău "factorial de opt" mai eficient decât notația echivalentă „patruzeci de mii trei sute douăzeci”. O întrebare logică apare aici: care este cea mai scurtă notație pentru un anumit număr?
Filosoful Bertrand Russell a publicat în 1908 , care abordează problema notării numerelor din partea opusă: Care este cel mai mic număr care nu necesită optzeci de litere?
Un astfel de număr trebuie să existe: din optzeci de litere și spații rusești poți alcătui doar 3480 de desemnări, ceea ce înseamnă că folosind optzeci de litere nu poți desemna mai mult de 3480 de numere. Aceasta înseamnă că este imposibil să desemnați un anumit număr nu mai mult de 3480 în acest fel.
Aceasta înseamnă că acest număr va corespunde desemnării „cel mai mic număr pentru care optzeci de litere nu sunt suficiente”, care are doar 78 de litere! Pe de o parte, acest număr trebuie să existe; pe de altă parte, dacă acest număr există, atunci desemnarea lui nu îi corespunde. Paradox!
Cel mai simplu mod de a respinge acest paradox este să ne referim la informalitatea notațiilor verbale. Ca, dacă ar fi permis doar un set de expresii definit în mod specific în notație, atunci „cel mai mic număr pentru care optzeci de litere nu sunt suficiente” nu ar fi o notație validă, în timp ce notații practic utile ca "factorial de opt" ar rămâne acceptabil.
Există modalități formale de a descrie succesiunea (algoritmul) acțiunilor asupra numerelor? Există și din abundență - se numesc limbaje de programare. În loc de notații verbale, vom folosi programe (de exemplu, în Python) care afișează numerele necesare. De exemplu, pentru cinci nouă, programul este potrivit print("9"*5). Vom continua să fim interesați de cel mai scurt program pentru un anumit număr. Se numește lungimea unui astfel de program numere; este limita teoretică până la care poate fi comprimat un anumit număr.
În loc de paradoxul lui Berry, acum putem lua în considerare unul similar: Care este cel mai mic număr pe care un program kilobyte nu este suficient să îl scoată?
Vom raționa în același mod ca și înainte: există 2561024 de texte kilobyte, ceea ce înseamnă că nu pot fi scoase mai mult de 2561024 de numere de programele kilobyte. Aceasta înseamnă că un anumit număr nu mai mare de 2561024 nu poate fi derivat în acest fel.
Dar să scriem un program în Python care generează toate textele posibile în kilobyte, le rulează pentru execuție și, dacă scot un număr, apoi adaugă acest număr la dicționarul celor accesibile. După ce a verificat toate cele 2561024 de posibilități, indiferent de cât timp va dura, programul caută cel mai mic număr care lipsește din dicționar și tipărește acel număr. Pare evident că un astfel de program se va potrivi într-un kilobyte de cod - și va scoate chiar numărul care nu poate fi scos de un program kilobyte!
Care este captura acum? Nu mai poate fi pusă pe seama informalității notației!
Dacă sunteți confuz de faptul că programul nostru va necesita o cantitate astronomică de memorie pentru a funcționa - un dicționar (sau matrice de biți) de 2561024 elemente - atunci puteți face același lucru fără el: pentru fiecare dintre cele 2561024 numere, la rândul său , parcurgeți toate cele 2561024 de programe posibile, până când nu există unul potrivit. Nu contează că o astfel de căutare va dura foarte mult timp: după ce a verificat mai puțin de (2561024)2 perechi din număr și program, se va termina și va găsi acel număr foarte prețuit.
Sau nu se va termina? Într-adevăr, printre toate programele care vor fi încercate, vor exista while True: pass (și analogii săi funcționali) - și problema nu va merge mai departe decât testarea unui astfel de program!
Spre deosebire de paradoxul lui Berry, unde prinderea a fost în informalitatea notației, în al doilea caz avem o reformulare bine mascată. . Faptul este că este imposibil să se determine rezultatul dintr-un program într-un timp finit. În special, complexitatea Kolmogorov : nu există un algoritm care să permită, pentru un număr dat, să găsească lungimea celui mai scurt program care tipărește acest număr; ceea ce înseamnă că nu există o soluție la problema lui Berry - să găsești lungimea celei mai scurte desemnări verbale pentru un anumit număr.
Sursa: www.habr.com