Andmete kokkusurumise paradoksid

Andmete kokkusurumise ülesanne oma lihtsaimas vormis võib seonduda numbrite ja nende tähistustega. Numbrid saab tähistada numbritega („üheteistkümme“ 11 kohta), matemaatiliste avaldarvutustega („kaks kahekümnendas“ 1048576 kohta), stringiavaldusena („viis üheksandikku“ 99999 kohta), omadussõnadega („selle looma number“ 666 kohta, „Turingi surma aasta“ 1954 kohta), või nende suvaliste kombinatsioonide kaudu. Sobib iga tähistus, mille alusel vestluskaaslane suudab üheselt määratleda, millest numbrist jutt. On ilmne, et vestluskaaslasele on tõhusam öelda „kaheksa faktoriaal“ kui sellele vastav tähistus „nelikümmend tuhat kolmkümmend“. Siin tekib loogiline küsimus: milline tähistus on antud numbri jaoks kõige lühem?

Filosoof Bertrand Russell avaldas 1908. aastal „Berry paradoksi“, mis käsitleb numbri tähistamise küsimust vastupidiselt: milline on väikseim number, mille tähistamiseks ei piisa kaheksast kümnest tähest?
Selline number peab eksisteerima: kaheksast kümnest vene tähest ja tühikutest saab kokku vaid 3480 tähist, seega saab kaheksast kümnest tähest tähistada mitte rohkem kui 3480 numbrit. Seega, mingit numbrit, mis ei ole suurem kui 3480, ei saa sel moel tähistada.

Seega vastab sellele numbrile tähistus „väikseim number, mille tähistamiseks ei piisa kaheksast kümnest tähest“, kus on kokku 78 tähte! Ühest küljest peab see number existeerima; teisest küljest, kui see number eksisteerib, siis ei vasta selle tähistus sellele. Paradoks!

Lihtsaim viis sellest paradoksist kõrvale hiilida on viidata sõnaliste tähistuste mitteformaalusele. Nagu, kui tähistustes oleks aktsepteeritud vaid kindel ja määratletud väljendite kogum, siis „väikseim number, mille tähistamiseks ei piisa kaheksast kümnest tähest“ ei oleks see kehtiv tähistus, samas kui praktiliselt kasulikud tähistused, nagu „kaheksa faktoriaal“ jääksid kehtivaks.

Kas on olemas formaalseid viise numbritega tehtavate toimingute (algoritmi) järjekorra kirjeldamiseks? Jah, ja küllaga - neid nimetatakse programmeerimiskeelteks. Kasutame sõnaliste tähistuste asemel programme (näiteks Pythonis), mis väljastavad vajalikud numbrid. Näiteks viis üheksandikku võiks sobida programm print("9"*5). Jätkuvalt huvitume kõige lühemast programmist antud arvu jaoks. Sellise programmi pikkust nimetatakse kolmogorovi keerukuseks arvule; see on teoreetiline piir, mille võrra antud arvu saab kokku suruda.

Berry paradoksi asemel võib nüüd kaaluda sarnast: milline on kõige väiksem number, mille väljundiks ei piisa kilobaidist programmist?

Arutame nagu varem: eksisteerib 2561024 kilobaidi teksti, seega kilobaidiprogrammidega saab väljundiks saada mitte rohkem kui 2561024 numbrit. Seega mingit arvu, mis ei ületa 2561024, ei saa sellisel viisil väljundiks saada.

Kuid kirjutame Pythonis programmi, mis genereerib kõik võimalikke kilobaidi texte, käivitab need ja kui need väljastavad mingi numbri - lisab selle numbri saavutuste sõnastikku. Pärast kõigi 2561024 variandi kontrollimist, kui kaua see ka ei võtaks - programm otsib, milline on see kõige väiksem number, mis puudub sõnastikust, ja väljastab selle numbri. Tundub ilmselge, et selline programm mahtuks kilobaidi koodi - ja väljastaks just selle numbri, mida ei saa kilobaidiprogrammi abil väljastada!

Kus on nüüd nõks? Mitteformaalsust nimelt ei saa enam kasuks tuua!

Kui teid häirib, et meie programm nõuab tööks astronoomilist hulka mälu - sõnastik (või bitimassiiv) 2561024 elemendist - siis on võimalik kõik see ka ilma selleta teostada: igale 2561024 numbrile järjestikku järjestada kõiki 2561024 võimalikke programme, kuni leitakse sobiv. Pole oluline, et selline läbivaatamine kestab väga kaua: pärast kontrollimist vähem kui (2561024)2 paari numbri ja programmi vahel see ju lõpuks lõpeb ja leiab selle kauaoodatud numbri.

Või ei lõpeta? Sest kõigi katsetatavate programmide seas satume me while True: pass (ja tema funktsionaalsed analoogid) - ja edasi niisuguse programmi kontrollimisega ei saagi edasi minna!

Erinevalt Berry paradoksist, kus nõks oli mitteformaalsuses, on teises olukorras meil hästi maskeeritud ümberformuleerimine «peatumisprobleemist». Asi on selles, et programmi põhjal ei ole võimalik selle väljundit lõpliku ajaga määrata. Eriti kolmogorovi keerukus on arvutamatu.: ei ole olemas mingit algoritmi, mis võimaldaks antud arvu jaoks leida kõige lühema programmi pikkust, mis seda arvu väljastab; seega ei ole lahendust ka Berra ülesandele — leida antud arvu jaoks kõige lühema sõnalise tähistuse pikkust.

Allikas: habr.com