Tugas kompresi data dalam bentuknya yang paling sederhana dapat berhubungan dengan angka dan notasinya. Bilangan dapat dilambangkan dengan angka (
"sebelas" untuk angka 11), ekspresi matematis (
"two in the twentieth" untuk 1048576), ekspresi string (
"five nines" untuk 99999), nama-nama yang tepat (
"jumlah beast" untuk 666,
"tahun kematian Turing " Untuk 1954), atau kombinasi sewenang-wenang mereka. Penunjukan apa pun yang dengannya lawan bicara dapat secara jelas menentukan jenis bicara apa yang cocok adalah cocok. Jelas, memberi tahu lawan bicara
"faktorial delapan" lebih efektif daripada sebutan yang setara
"empat puluh ribu tiga ratus dua puluh" . Ini menimbulkan pertanyaan logis: apa sebutan terpendek untuk nomor yang diberikan?
Filsuf Bertrand Russell pada tahun 1908 menerbitkan
"Berry Paradox," yang membahas masalah notasi angka di sisi yang berlawanan:
berapakah angka terkecil untuk menunjukkan delapan puluh huruf mana yang tidak cukup?Angka semacam itu harus ada: dari delapan puluh huruf dan spasi Rusia Anda dapat membuat total
3480 penunjukan, yang berarti bahwa menggunakan delapan puluh huruf Anda dapat menunjuk tidak lebih dari 34
80 angka. Oleh karena itu, angka tertentu, tidak lebih dari
3480 , tidak dapat ditetapkan dengan cara ini.
Ini berarti bahwa penunjukan
"angka terkecil yang delapan puluh hurufnya tidak cukup" akan sesuai dengan angka ini, di mana hanya ada 78 huruf! Di satu sisi, angka ini harus ada; di sisi lain, jika nomor ini ada, maka peruntukannya tidak sesuai dengannya. Paradoks!
Cara termudah untuk mengabaikan paradoks ini adalah dengan merujuk pada informalitas penunjukan verbal. Seperti, jika hanya satu set ekspresi tertentu diizinkan dalam notasi, maka
"jumlah terkecil yang delapan huruf tidak
cukup" tidak akan menjadi penunjukan yang valid, sementara penunjukan praktis yang berguna dari tipe
"faktororial delapan" akan tetap valid.
Adakah cara formal untuk menggambarkan urutan (algoritme) tindakan pada angka? Ada, dan dalam kelimpahan - mereka disebut bahasa pemrograman. Alih-alih notasi verbal, kami akan menggunakan program (misalnya, dengan Python) yang mencetak angka yang diperlukan. Misalnya, untuk lima sembilan, program
print("9"*5) cocok. Kami akan terus tertarik pada program terpendek untuk nomor yang diberikan. Panjang program semacam itu disebut
kompleksitas nomor
Kolmogorov ; Ini adalah batas teoretis di mana angka yang diberikan dapat dikompres.
Alih-alih paradoks Berry, orang sekarang dapat mempertimbangkan yang serupa:
berapakah jumlah terkecil yang program kilobyte tidak cukup?Kami akan berdebat dengan cara yang sama seperti sebelumnya: ada
256.1024 kilobyte teks, yang berarti bahwa tidak lebih dari
256.224 angka dapat ditampilkan dalam program kilobyte. Ini berarti bahwa angka tertentu, tidak lebih besar dari 256
1024 , tidak dapat disimpulkan dengan cara ini.
Tapi kami menulis dalam Python sebuah program yang menghasilkan semua teks kilobyte yang mungkin, meluncurkannya untuk dieksekusi, dan jika mereka mencetak angka tertentu, itu menambahkan nomor ini ke kamus yang dapat dicapai. Setelah memeriksa semua 256
1024 kemungkinan, tidak peduli berapa lama waktu yang diperlukan - program mencari angka terkecil yang tidak ada dalam kamus dan menampilkan nomor ini. Tampaknya jelas bahwa program seperti itu akan muat dalam satu kilobyte kode - dan akan menampilkan angka yang tidak dapat ditampilkan dalam program kilobyte!
Apa tangkapannya sekarang? Itu tidak lagi dapat dikaitkan dengan informalitas notasi!
Jika Anda bingung bahwa program kami akan membutuhkan sejumlah memori astronomi untuk berfungsi - kamus (atau bitmap) 256
1024 elemen - maka Anda dapat melakukan hal yang sama tanpanya: untuk masing-masing dari 256
1024 angka, beralihlah ke semua 256
1024 yang memungkinkan. program sampai yang cocok ditemukan. Tidak masalah bahwa penghitungan seperti itu akan berlangsung sangat lama: setelah memeriksa kurang dari (256
1024 )
2 pasang dari nomor dan program, itu akan berakhir, dan akan menemukan nomor yang sangat dihargai.
Atau tidak akan berakhir? Memang, di antara semua program yang akan dicoba, akan ada
while True: pass (dan rekan-rekan fungsionalnya) - dan hal-hal tidak akan melampaui memeriksa program seperti itu!
Berbeda dengan paradoks Berry, di mana hasil tangkapannya adalah informalitas notasi, dalam kasus kedua kita memiliki reformulasi terselubung baik dari
"masalah berhenti" . Faktanya adalah bahwa menurut program tidak mungkin untuk menentukan kesimpulannya dalam waktu yang terbatas. Secara khusus, kompleksitas Kolmogorov tidak
dapat dihitung : tidak ada algoritma yang memungkinkan angka tertentu untuk menemukan panjang program terpendek yang menghasilkan angka ini; yang berarti bahwa tidak ada solusi untuk masalah Berry - untuk menemukan untuk nomor tertentu panjang penunjukan kata terpendek.