Masalah pemampatan data, dalam bentuk yang paling mudah, boleh dikaitkan dengan nombor dan notasinya. Nombor boleh dilambangkan dengan angka ("sebelas" untuk nombor 11), ungkapan matematik ("dua dalam kedua puluh" untuk 1048576), ungkapan rentetan ("lima sembilan" untuk 99999), nama khas ("bilangan binatang" untuk 666, "tahun kematian Turing" untuk 1954), atau kombinasi sewenang-wenangnya. Mana-mana sebutan adalah sesuai yang mana lawan bicara dapat menentukan dengan jelas nombor yang kita bicarakan. Jelas sekali, beritahu teman bicara anda "faktorial lapan" lebih cekap daripada tatatanda setara "empat puluh ribu tiga ratus dua puluh". Soalan logik timbul di sini: apakah tatatanda terpendek untuk nombor tertentu?
Ahli falsafah Bertrand Russell diterbitkan pada tahun 1908 , yang menyentuh isu notasi nombor dari sisi bertentangan: Apakah nombor terkecil yang tidak memerlukan lapan puluh huruf?
Nombor sedemikian mesti wujud: dari lapan puluh huruf dan ruang Rusia anda boleh membuat hanya 3480 sebutan, yang bermaksud bahawa menggunakan lapan puluh huruf anda boleh menetapkan tidak lebih daripada 3480 nombor. Ini bermakna mustahil untuk menetapkan nombor tertentu tidak lebih daripada 3480 dengan cara ini.
Ini bermakna nombor ini akan sepadan dengan penetapan "nombor terkecil yang tidak mencukupi lapan puluh huruf", yang hanya mempunyai 78 huruf! Di satu pihak, nombor ini mesti wujud; sebaliknya, jika nombor ini wujud, maka sebutannya tidak sepadan dengannya. Paradoks!
Cara paling mudah untuk mengetepikan paradoks ini adalah dengan merujuk kepada notasi lisan yang tidak formal. Seperti, jika hanya set ungkapan yang ditakrifkan secara khusus dibenarkan dalam tatatanda, maka "nombor terkecil yang tidak mencukupi lapan puluh huruf" bukan notasi yang sah, sedangkan notasi praktikal yang berguna seperti "faktorial lapan" akan tetap diterima.
Adakah terdapat cara formal untuk menerangkan urutan (algoritma) tindakan pada nombor? Terdapat, dan dengan banyaknya - mereka dipanggil bahasa pengaturcaraan. Daripada notasi lisan, kami akan menggunakan program (contohnya, dalam Python) yang memaparkan nombor yang diperlukan. Sebagai contoh, untuk lima sembilan program ini sesuai print("9"*5). Kami akan terus berminat dengan program terpendek untuk nombor tertentu. Panjang program sedemikian dipanggil nombor; ia adalah had teori yang mana nombor tertentu boleh dimampatkan.
Daripada paradoks Berry, kita kini boleh mempertimbangkan yang serupa: Apakah nombor terkecil yang program kilobait tidak mencukupi untuk dikeluarkan?
Kami akan membuat alasan dengan cara yang sama seperti sebelumnya: terdapat 2561024 teks kilobait, yang bermaksud bahawa tidak lebih daripada 2561024 nombor boleh dikeluarkan oleh program kilobait. Ini bermakna nombor tertentu tidak lebih daripada 2561024 tidak boleh diperoleh dengan cara ini.
Tetapi mari kita tulis program dalam Python yang menjana semua teks kilobait yang mungkin, menjalankannya untuk pelaksanaan, dan jika ia mengeluarkan nombor, kemudian menambah nombor ini pada kamus yang boleh dicapai. Selepas menyemak semua 2561024 kemungkinan, tidak kira berapa lama masa yang diperlukan, program mencari nombor terkecil yang hilang daripada kamus dan mencetak nombor itu. Nampaknya jelas bahawa program sedemikian akan dimuatkan ke dalam satu kilobait kod - dan akan mengeluarkan nombor yang tidak boleh dikeluarkan oleh program kilobait!
Apa tangkapan sekarang? Ia tidak lagi boleh dikaitkan dengan notasi yang tidak formal!
Jika anda keliru dengan fakta bahawa program kami memerlukan jumlah memori astronomi untuk berfungsi - kamus (atau tatasusunan bit) 2561024 elemen - maka anda boleh melakukan perkara yang sama tanpanya: untuk setiap nombor 2561024, seterusnya , pergi melalui semua 2561024 program yang mungkin, sehingga tiada program yang sesuai. Tidak kira carian sedemikian akan bertahan lama: selepas menyemak kurang daripada (2561024)2 pasangan daripada nombor dan program, ia akan tamat dan mendapati nombor yang sangat dihargai itu.
Atau tidak akan selesai? Memang antara semua program yang akan dicuba pasti ada while True: pass (dan analog fungsinya) - dan perkara itu tidak akan pergi lebih jauh daripada menguji program sedemikian!
Tidak seperti paradoks Berry, di mana tangkapannya adalah dalam notasi yang tidak formal, dalam kes kedua kita mempunyai perumusan semula yang terselindung . Hakikatnya adalah mustahil untuk menentukan outputnya daripada program dalam masa yang terhad. Khususnya, kerumitan Kolmogorov : tiada algoritma yang membenarkan, untuk nombor tertentu, mencari panjang program terpendek yang mencetak nombor ini; yang bermaksud tiada penyelesaian kepada masalah Berry - untuk mencari panjang sebutan lisan terpendek untuk nombor tertentu.
Sumber: www.habr.com