Masalah komprési data, dina wangun pangbasajanna, bisa patali jeung angka jeung notasi maranéhanana. Angka bisa dilambangkeun ku angka ("sabelas" pikeun angka 11), éksprési matematik ("dua dina dua puluh" pikeun 1048576), éksprési string ("lima salapan" pikeun 99999), ngaran ditangtoskeun ("jumlah sato galak" pikeun 666, "taun pupusna Turing urang" pikeun 1954), atanapi kombinasi sawenang-wenang. Sakur sebutan anu cocog sareng anu interlocutor jelas tiasa nangtoskeun nomer naon anu urang nyarioskeun. Jelas, ngabejaan interlocutor Anjeun "faktorial dalapan" leuwih efisien batan notasi sarimbag "opat puluh rebu tilu ratus dua puluh". Patarosan logis timbul di dieu: naon notasi shortest pikeun angka nu tangtu?
Filsuf Bertrand Russell diterbitkeun dina 1908 , nu némpél dina masalah notasi angka ti sisi sabalikna: Naon angka pangleutikna nu teu merlukeun dalapan puluh hurup?
Jumlah sapertos kitu kedah aya: ti dalapan puluh hurup sareng spasi Rusia anjeun tiasa ngan ukur 3480 sebutan, anu hartosna nganggo dalapan puluh hurup anjeun tiasa nunjuk henteu langkung ti 3480 nomer. Ieu ngandung harti yén teu mungkin keur nunjuk angka nu tangtu teu leuwih ti 3480 ku cara kieu.
Ieu ngandung harti yén angka ieu bakal pakait jeung designation nu "angka pangleutikna anu dalapan puluh hurup henteu cekap", nu boga ngan 78 hurup! Di hiji sisi, jumlah ieu kedah aya; di sisi séjén, lamun jumlah ieu aya, lajeng designation na teu pakait jeung eta. Paradoks!
Cara panggampangna pikeun ngaleungitkeun paradoks ieu nyaéta ngarujuk kana informalitas notasi verbal. Siga, upami ngan ukur set éksprési anu didefinisikeun dina notasi, teras "angka pangleutikna anu dalapan puluh hurup henteu cekap" moal janten notasi valid, sedengkeun notasi praktis mangpaat kawas "faktorial dalapan" bakal tetep ditarima.
Naha aya cara formal pikeun ngajelaskeun sekuen (algoritma) tindakan dina angka? Aya, sarta dina kaayaanana - aranjeunna disebut basa programming. Gantina notasi verbal, urang bakal ngagunakeun program (contona, dina Python) nu mintonkeun nomer diperlukeun. Contona, pikeun lima nines program cocog print("9"*5). Urang bakal terus kabetot dina program shortest pikeun angka nu tangtu. Panjang program sapertos disebut angka; éta wates téoritis nu jumlah dibikeun bisa dikomprés.
Gantina paradoks Berry, urang ayeuna tiasa nganggap anu sami: Naon jumlah pangleutikna anu program kilobyte teu cukup pikeun kaluaran?
Urang bakal alesan dina cara nu sarua kawas saméméhna: aya 2561024 kilobyte téks, nu hartina teu leuwih ti 2561024 angka bisa kaluaran ku program kilobyte. Ieu ngandung harti yén jumlah nu tangtu teu leuwih gede ti 2561024 teu bisa diturunkeun ku cara ieu.
Tapi hayu urang nulis program dina Python nu dibangkitkeun sagala téks kilobyte mungkin, ngajalankeun aranjeunna pikeun palaksanaan, sarta lamun aranjeunna kaluaran angka, lajeng nambahkeun angka ieu kana kamus leuwih reachable. Sanggeus mariksa sagala 2561024 kamungkinan, euweuh urusan sabaraha lila waktu nu diperlukeun, program néangan jumlah pangleutikna leungit tina kamus jeung prints angka nu. Sigana atra yén program sapertos bakal cocog kana kilobyte kode - sarta bakal kaluaran jumlah pisan nu teu bisa kaluaran ku program kilobyte!
Naon nu nyekel ayeuna? Éta henteu tiasa dikaitkeun deui kana informalitas notasi!
Upami anjeun bingung ku kanyataan yén program kami ngabutuhkeun jumlah mémori astronomis pikeun dianggo - kamus (atanapi susunan bit) tina 2561024 elemen - maka anjeun tiasa ngalakukeun hal anu sami tanpa éta: pikeun tiap angka 2561024, giliran. , ngaliwat sadaya 2561024 program anu mungkin, dugi ka teu aya anu cocog. Henteu janten masalah yén panéangan sapertos kitu bakal lami pisan: saatos mariksa kirang ti (2561024) 2 pasang tina nomer sareng program, éta bakal ditungtungan sareng mendakan éta nomer anu dipikacinta.
Atawa moal rengse? Mémang, di antara sadaya program anu bakal dicoba, bakal aya while True: pass (sareng analog fungsionalna) - sareng masalahna moal langkung jauh tibatan nguji program sapertos kitu!
Teu kawas paradoks Berry urang, dimana nyekel éta dina informalitas notasi, dina kasus kadua urang boga reformulasi well-disguised. . Kanyataanna nyaéta mustahil pikeun nangtukeun kaluaranna tina program dina waktos anu terbatas. Khususna, pajeulitna Kolmogorov : euweuh algoritma nu bakal ngidinan, pikeun angka nu tangtu, pikeun manggihan panjang program shortest nu prints angka ieu; nu hartina euweuh solusi pikeun masalah Berry urang - pikeun manggihan panjang designation verbal shortest pikeun angka nu tangtu.
sumber: www.habr.com