Andmete tihendamise probleem oma kõige lihtsamal kujul võib olla seotud numbrite ja nende tähistusega. Numbreid saab tähistada numbritega ("üksteist" arvu 11 jaoks), matemaatilised avaldised ("kaks kahekümnendas" 1048576 jaoks), stringi avaldised ("viis üheksa" 99999 jaoks), pärisnimed ("metsalise number" 666 eest, "Turingi surma aasta" 1954) või nende suvalised kombinatsioonid. Iga tähistus sobib, mille järgi vestluskaaslane saab selgelt kindlaks teha, millisest numbrist me räägime. Loomulikult rääkige sellest oma vestluskaaslasele "kaheksa faktor" tõhusam kui samaväärne märge "nelikümmend tuhat kolmsada kakskümmend". Siin tekib loogiline küsimus: milline on antud arvu lühim tähis?
Filosoof Bertrand Russell avaldas 1908. aastal , mis puudutab numbrite märkimise küsimust teisest küljest: Mis on väikseim number, mis ei nõua kaheksakümmend tähte?
Selline number peab olemas olema: kaheksakümnest vene tähest ja tühikust saate moodustada ainult 3480 tähist, mis tähendab, et kaheksakümne tähega saate tähistada mitte rohkem kui 3480 numbrit. See tähendab, et teatud arvu, mis ei ületa 3480, on sel viisil võimatu määrata.
See tähendab, et see number vastab tähistusele "väikseim number, mille jaoks kaheksakümnest tähest ei piisa", millel on ainult 78 tähte! Ühest küljest peab see number olemas olema; teisest küljest, kui see number on olemas, siis selle tähistus sellele ei vasta. Paradoks!
Lihtsaim viis seda paradoksi kõrvale heita on viidata verbaalsete märgete mitteametlikkusele. Nagu, kui noodikirjas oleks lubatud ainult konkreetselt määratletud avaldiste komplekt, siis "väikseim number, mille jaoks kaheksakümnest tähest ei piisa" ei oleks kehtiv märge, samas kui praktiliselt kasulikud märgid nagu "kaheksa faktor" jääks vastuvõetavaks.
Kas arvudega tehtavate toimingute jada (algoritmi) kirjeldamiseks on formaalseid viise? Neid on ja ohtralt - neid nimetatakse programmeerimiskeelteks. Sõnaliste märgete asemel kasutame programme (näiteks Pythonis), mis kuvavad vajalikud numbrid. Näiteks viiele üheksale sobib programm print("9"*5). Oleme jätkuvalt huvitatud antud numbri lühima programmi vastu. Sellise programmi pikkust nimetatakse numbrid; see on teoreetiline piir, milleni antud arvu saab tihendada.
Berry paradoksi asemel võime nüüd kaaluda sarnast: Mis on väikseim arv, mille väljastamiseks kilobaidisest programmist ei piisa?
Arutleme samamoodi nagu varem: kilobaidiseid tekste on 2561024, mis tähendab, et kilobaidiprogrammid ei saa väljastada rohkem kui 2561024 numbrit. See tähendab, et teatud arvu, mis ei ületa 2561024, ei saa sel viisil tuletada.
Aga kirjutame Pythonis programmi, mis genereerib kõik võimalikud kilobaidised tekstid, käivitab need täitmiseks ja kui väljastab numbri, siis lisab selle numbri kättesaadavate sõnaraamatusse. Pärast kõigi 2561024 XNUMX XNUMX võimaluse kontrollimist otsib programm sõnaraamatust kõige väiksema puuduva arvu, olenemata sellest, kui kaua see aega võtab, ja prindib selle numbri välja. Näib ilmselge, et selline programm mahub kilobaidi koodi sisse – ja väljastab just selle numbri, mida kilobaidine programm väljastada ei suuda!
Mis on nüüd saak? Seda ei saa enam panna tähistuse mitteametlikkuse arvele!
Kui teid ajab segadusse asjaolu, et meie programm vajab töötamiseks astronoomiliselt palju mälu – 2561024 elemendist koosnevat sõnastikku (või bitimassiivi), siis saate teha sama asja ka ilma selleta: iga 2561024 numbri puhul omakorda , käige läbi kõik 2561024 võimalikku programmi, kuni sobivat pole. Pole tähtis, et selline otsing kestab väga kaua: pärast vähem kui (2561024)2 paari kontrollimist numbrist ja programmist see lõpeb ja leiab selle väga kalli numbri.
Või see ei lõpe? Tõepoolest, kõigi proovitavate programmide hulgas on while True: pass (ja selle funktsionaalsed analoogid) - ja asi ei lähe kaugemale sellise programmi testimisest!
Erinevalt Berry paradoksist, kus konks oli tähistuse mitteformaalsuses, on teisel juhul meil hästi varjatud ümbersõnastus. . Fakt on see, et selle väljundit on programmist piiratud aja jooksul võimatu määrata. Eelkõige Kolmogorovi keerukus : puudub algoritm, mis võimaldaks antud numbri puhul leida lühima programmi pikkust, mis selle numbri prindib; mis tähendab, et Berry probleemile pole lahendust – leida antud numbri lühima sõnalise nimetuse pikkus.
Allikas: www.habr.com