Masalah kompresi data, ing wangun sing paling gampang, bisa digandhengake karo nomer lan notasi. Angka bisa didudut nganggo angka ("sewelas" kanggo nomer 11), ekspresi matematika ("loro ing rong puluh" kanggo 1048576), ekspresi string ("limang sangang" kanggo 99999), jeneng sing tepat ("nomer kewan" kanggo 666, "taun seda Turing" kanggo 1954), utawa kombinasi sing sewenang-wenang. Sembarang sebutan cocok kanggo sing interlocutor bisa nemtokake nomer apa kita ngomong bab. Temenan, matur marang mitra tutur sampeyan "faktorial XNUMX" luwih efisien tinimbang notasi sing padha "patang puluh ewu telung atus rong puluh". Pitakonan logis muncul ing kene: apa notasi paling cendhak kanggo nomer tartamtu?
Filsuf Bertrand Russell diterbitake taun 1908 , sing ndemek masalah notasi nomer saka sisih ngelawan: Apa nomer paling cilik sing ora mbutuhake wolung puluh aksara?
Nomer kasebut kudu ana: saka wolung puluh huruf lan spasi Rusia sampeyan bisa nggawe mung 3480 sebutan, sing tegese nggunakake wolung puluh huruf sampeyan bisa nemtokake ora luwih saka 3480 nomer. Iki tegese ora bisa nemtokake nomer tartamtu ora luwih saka 3480 kanthi cara iki.
Iki tegese nomer iki bakal cocog karo sebutan kasebut "nomer paling cilik sing wolung puluh huruf ora cukup", sing mung 78 aksara! Ing tangan siji, nomer iki kudu ana; ing tangan liyane, yen nomer iki ana, banjur sebutan ora cocog kanggo iku. Paradoks!
Cara paling gampang kanggo ngilangi paradoks iki yaiku ngrujuk marang notasi verbal sing ora resmi. Kaya, yen mung set ekspresi sing ditemtokake khusus sing diidini ing notasi, banjur "nomer paling cilik sing wolung puluh huruf ora cukup" ora bakal dadi notasi sing bener, dene notasi sing praktis migunani kaya "faktorial XNUMX" bakal tetep ditrima.
Apa ana cara resmi kanggo njlèntrèhaké urutan (algoritma) tumindak ing nomer? Ana, lan akeh banget - diarani basa pemrograman. Tinimbang notasi lisan, kita bakal nggunakake program (contone, ing Python) sing nampilake nomer sing dibutuhake. Contone, kanggo limang nines program cocok print("9"*5). Kita bakal terus kasengsem ing program paling cendhak kanggo nomer tartamtu. Dawane program kasebut diarani angka; iku watesan teori sing nomer tartamtu bisa teken.
Tinimbang paradoks Berry, saiki kita bisa nimbang sing padha: Apa nomer paling cilik sing program kilobyte ora cukup kanggo output?
Kita bakal menehi alesan kanthi cara sing padha kaya sadurunge: ana 2561024 teks kilobyte, sing tegese ora luwih saka 2561024 nomer sing bisa dicetak dening program kilobyte. Iki tegese nomer tartamtu ora luwih saka 2561024 ora bisa diturunake kanthi cara iki.
Nanging ayo kang nulis program ing Python sing ngasilake kabeh teks kilobyte bisa, mbukak kanggo eksekusi, lan yen padha output nomer, banjur nambah nomer iki kanggo kamus tekan. Sawise mriksa kabeh 2561024 kemungkinan, ora ketompo suwene wektu, program kasebut nggoleki nomer paling cilik sing ilang saka kamus lan nyithak nomer kasebut. Iku misale jek ketok sing program kuwi bakal pas menyang kilobyte kode - lan bakal output nomer banget sing ora bisa output dening program kilobyte!
Apa sing nyekel saiki? Ora bisa digandhengake karo notasi sing ora resmi!
Yen sampeyan bingung karo kasunyatan manawa program kita mbutuhake memori astronomi sing bisa digunakake - kamus (utawa susunan bit) saka 2561024 unsur - mula sampeyan bisa nindakake perkara sing padha tanpa: kanggo saben nomer 2561024, banjur , bukak kabeh 2561024 program sing bisa ditindakake, nganti ora ana sing cocog. Ora ketompo yen telusuran kasebut bakal suwe banget: sawise mriksa kurang saka (2561024) 2 pasangan saka nomer lan program, bakal mungkasi lan nemokake nomer sing dihormati.
Utawa ora bakal rampung? Pancen, ing antarane kabeh program sing bakal dicoba, bakal ana while True: pass (lan analog fungsional) - lan masalah kasebut ora bakal luwih saka nyoba program kasebut!
Boten kados paradoks Berry, ing pundi kemawon wonten ing informalitas notasi, ing kasus kaping kalih kita gadhah reformulasi ingkang samar. . Kasunyatan iku mokal kanggo nemtokake output saka program ing wektu winates. Utamane, kerumitan Kolmogorov : ora ana algoritma sing bakal ngidini, kanggo nomer tartamtu, kanggo nemokake dawa program paling cendhak sing prints nomer iki; tegese ora ana solusi kanggo masalah Berry - kanggo nemokake dawa sebutan lisan sing paling cendhak kanggo nomer tartamtu.
Source: www.habr.com