Andmete tihendamine oma lihtsaimas vormis võib viidata numbritele ja nende tähistustele. Numbrid võivad olla tähistatud arvudena («üheteistkümne» arvule 11), matemaatiliste väljendite («kaks kahekümnendas» arvule 1048576), stringi väljendite («viis üheksat» arvule 99999), nimede («loomade number» arvule 666, «Turingi surmaasta» arvule 1954), või nende meelevaldsete kombinatsioonide kaudu. Sobib iga tähistus, mille kaudu vestluspartner suudab üheselt mõista, millest arvust jutt käib. Ilmselgelt on soovitada vestluspartnerile «kaheksa faktoriaal» efektiivsem kui ekvivalentne tähistus «nelikümmend tuhat kolmkümmend». Siit tekib loogiline küsimus: mis tähistus on antud arvu jaoks kõige lühem?
Filosoof Bertrand Russell avaldas 1908. aastal , mis käsitleb numbrite tähistamise küsimust vastupidiselt: mis on kõige väiksem number, mille tähistamiseks ei piisa kaheksakümnest tähest?
Selline number peab eksisteerima: kaheksakümnest vene tähest ja tühikutest saab moodustada vaid 3480 tähistust, seega võib kaheksakümne tähe abil tähistada mitte rohkem kui 3480 numbrit. Seega, mingit numbrit, mis on suurem kui 3480, ei saa sellisel viisil tähistada.
Seega vastab sellele numbrile tähistus «kõige väiksem number, mille tähistamiseks ei piisa kaheksakümnest tähest», kus on koguni 78 tähte! Ühelt poolt peab see number eksisteerima; teiselt poolt, 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 mitteformaalsusele. Justkui, kui tähistustes lubataks ainult konkreetset määratletud väljendite komplekti, siis «kõige väiksem number, mille tähistamiseks ei piisa kaheksakümnest tähest» ei oleks mitteaktsepteeritav tähistus, samas kui praktiliselt kasulikud tähistused nagu «kaheksa faktoriaal» püsivad aktsepteeritavana.
Kas on olemas formaalseid viise, kuidas kirjeldada tegevuste (algoritmi) järjestust arvudega? On, ja küll ja küll — neid nimetatakse programmeerimiskeelteks. Kasutame sõnaliste tähistuste asemel programme (näiteks Pythonis), mis genereerivad vajalikud numbrid. Näiteks, viie üheksa jaoks sobib programm print("9"*5). Jätkame kõige lühema programmi leidmist antud arvu jaoks. Selle programmi pikkust nimetatakse arvule; see on teoreetiline piir, kuhu antud arv saab tihendatuna jõuda.
Berry paradoksi asemel saab arutada sarnast: mis on kõige väiksem number, mille väljastamiseks ei piisa kilobaitidest programmist?
Jätkame sama loogikaga: on olemas 2561024 kilobaitilist teksti, seega saavad kilobaitilised programmid genereerida mitte rohkem kui 2561024 numbrit. Seega, mingit numbrit, mis on suurem kui 2561024, ei saa sellisel viisil genereerida.
Kuid kirjutame Pythonis programmi, mis genereerib kõik võimalikud kilobaitilised tekstid, käivitab need ning kui need annavad mingi arvu — lisab selle arvu saavutuste sõnaraamatusse. Pärast kõikide 2561024 võimaluse kontrollimist, olgu see kui kaua see ka ei kesta — programm otsib, mis on kõige väiksem number, mis puudub sõnaraamatust, ja väljastab selle numbri. Paistab ilmselge, et selline programm mahub kilobaiti koodi — ja väljastab just selle arvu, mida ei saa kilobaitide programmiga!
Kus on nüüd konks? Nüüd ei saa mitteformaalsust tähistustes selle alla kirjutada!
Kui teid häirib see, et meie programm vajab astronomilist hulka mälu tööks — sõnaraamat (või bitimassiiv) 2561024 elemendiga — siis võib kõik ülaltoodu teostada ka ilma selleta: igaühe 2561024 numbri korral järjestikune üritamine kõiki 2561024 võimalikke programme, kuni sobiv leitakse. Pole oluline, kui kaua selline proovimine kestab: pärast kontrollimist vähem kui (2561024)2 paari numbri ja programmi vahel, tuleb see ju lõpule ja leiab selle kuru arvu.
Või ei lõpeta? Lõppude lõpuks, kõikide katsetatavate programmide seas satub kokku while True: pass (ja tema funktsionaalsed analoogid) — ja edasi sellise programmi kontrollimine ei suju!
Erinevalt Berry paradoksist, kus konks oli sõnaliste tähistuste mitteformaalsuses, on teises olukorras tegemist hästi maskeeritud ümbervormistamisega . Tõde on, et programmi järgi ei ole võimalik lõpuni määrata selle väljundit. Eriti on Kolmogorovi keerukus : ei ole mingit algoritmi, mis võimaldaks antud arvu jaoks leida lühima programmi pikkust, mis seda arvu väljundab; see tähendab, et ka Beri probleemile — leida antud arvu jaoks lühima sõnalise tähistuse pikkus — ei ole lahendust.
Allikas: habr.com
