Problema comprimării datelor, în cea mai simplă formă, poate fi referitoare la numere și nașterea lor. Numerele pot fi reprezentate prin numeraluri ("unzeci" pentru numărul 11), prin expresii matematice ("doi la puterea douăzeci" pentru 1048576), prin expresii textuale ("cinci nouă" pentru 99999), prin nume proprii ("numărul fiarei" pentru 666, "anul morții lui Turing" pentru 1954), sau prin combinații arbitrare ale acestora. Orice denumire este acceptabilă atâta timp cât interlocutorul poate identifica fără echivoc despre ce număr este vorba. Este evident că a spune interlocutorului "factorialul lui opt" este mai eficient decât o denumire echivalentă "patruzeci de mii trei sute douăzeci". Aici apare întrebarea logică: care este cea mai scurtă denumire pentru un număr dat?
Filozoful Bertrand Russell a publicat în 1908 , care abordează problema denumirii numerelor dintr-un unghi opus: care este cel mai mic număr pentru care nu sunt suficiente optzeci de litere pentru a-l denumi?
Un astfel de număr trebuie să existe: din cele optzeci de litere rusești și spațiile se pot forma maxim 3480 de denumiri, așadar, folosind optzeci de litere, nu se pot denumi mai mult de 3480 de numere. Asta înseamnă că un număr, nu mai mare de 3480, nu poate fi denumit astfel.
Deci, acestui număr îi va corespunde denumirea "cel mai mic număr pentru care nu sunt suficiente optzeci de litere", care conține doar 78 de litere! Pe de o parte, acest număr trebuie să existe; pe de altă parte, dacă acest număr există, denumirea sa nu îi corespunde. Paradox!
Cel mai simplu mod de a ignora acest paradox este să facem referire la informalitatea denumirilor verbale. Se spune că, dacă în denumiri ar fi admis un singur set definit de expresii, atunci "cel mai mic număr pentru care nu sunt suficiente optzeci de litere" nu ar fi o denumire acceptabilă, în timp ce denumirile practic utile de tipul "factorialul lui opt" ar rămâne acceptabile.
Există metode formale de a descrie secvența (algoritmul) acțiunilor asupra numerelor? Da, și din belșug — acestea se numesc limbaje de programare. Vom folosi în loc de denumiri verbale programe (de exemplu, în Python) care să emită numerele necesare. De exemplu, pentru cinci nouă se potrivește programul print("9"*5)În continuare, ne vom interesa de cea mai scurtă programă pentru un număr dat. Lungimea unei astfel de programe se numește a numărului; acesta este limitarea teoretică până la care un număr dat poate fi comprimat.
În locul paradoxului Berry, acum putem considera un analog: care este cel mai mic număr pentru a cărui afișare nu este suficientă o programă de un kilobyte?
Vom raționa la fel ca înainte: există 2561024 texte de un kilobyte, ceea ce înseamnă că cu programele de un kilobyte pot fi generate nu mai mult de 2561024 numere. Așadar, un anumit număr, nu mai mare decât 2561024, nu poate fi generat în acest mod.
Dar vom scrie un program în Python care generează toate textele posibile de un kilobyte, le execută, iar dacă acestea afișează un număr, atunci adaugă acel număr în dicționarul numeric. După verificarea tuturor celor 2561024 posibilități, indiferent de timpul necesar — programul caută care este cel mai mic număr absent în dicționar și îl afișează. Se pare că este evident că o astfel de programă va încăpea într-un kilobyte de cod — și va afișa exact acel număr care nu poate fi generat de o programă de un kilobyte!
Dar care este capcana acum? Nu mai putem da vina pe informalitatea denumirilor!
Dacă te îngrijorează faptul că programul nostru va necesita o cantitate astronomică de memorie pentru a funcționa — un dicționar (sau un tablou de biți) cu 2561024 elemente — atunci totul poate fi realizat și fără el: pentru fiecare dintre cele 2561024 numere, pe rând, să încercăm toate cele 2561024 programe posibile până când găsim unul potrivit. Nu este important că o astfel de încercare va dura foarte mult: după verificarea a mai puțin de (2561024)2 perechi de număr și program, ea se va încheia și va găsi acel număr dorit.
Sau nu se va încheia? Căci printre toate programele care vor fi testate, se va întâlni while True: pass (și omologii săi funcționali) — iar verificarea unei astfel de programe nu va continua!
Spre deosebire de paradoxul Berry, în care capcana era în informalitatea denumirilor, în al doilea caz avem o reformulare bine camuflată a . Ceea ce este important este că, în functie de program, nu se poate determina rezultatul său într-un timp finit. În special, complexitatea kolmogorov : nu există niciun algoritm care să permită pentru un număr dat găsirea lungimii celei mai scurte programe care produce acel număr; prin urmare, nu există soluție nici pentru problema Berry — de a găsi pentru un număr dat lungimea celei mai scurte reprezentări verbale.
Sursa: habr.com
