Masalah kompresi data, dalam bentuk paling sederhana, dapat berhubungan dengan angka dan notasinya. Angka dapat dilambangkan dengan angka ("sebelas" untuk angka 11), ekspresi matematika ("dua di angka dua puluh" untuk 1048576), ekspresi string ("lima sembilan" untuk 99999), nama diri ("jumlah binatang itu" untuk 666, "tahun kematian Turing" untuk tahun 1954), atau kombinasi sewenang-wenangnya. Sebutan apa pun cocok sehingga lawan bicara dapat dengan jelas menentukan nomor mana yang sedang kita bicarakan. Jelasnya, beritahu lawan bicara Anda "faktorial delapan" lebih efisien daripada notasi setara "empat puluh ribu tiga ratus dua puluh". Pertanyaan logis muncul di sini: notasi terpendek apa untuk suatu bilangan tertentu?
Filsuf Bertrand Russell menerbitkannya pada tahun 1908 , yang menyentuh masalah notasi bilangan dari sisi berlawanan: Berapakah bilangan terkecil yang tidak memerlukan delapan puluh huruf?
Angka seperti itu harus ada: dari delapan puluh huruf dan spasi Rusia Anda hanya dapat membuat 3480 sebutan, yang berarti bahwa dengan menggunakan delapan puluh huruf Anda dapat menentukan tidak lebih dari 3480 angka. Artinya tidak mungkin menentukan bilangan tertentu tidak lebih dari 3480 dengan cara ini.
Artinya nomor ini akan sesuai dengan peruntukannya "angka terkecil yang delapan puluh huruf saja tidak cukup", yang hanya memiliki 78 huruf! Di satu sisi, nomor ini harus ada; sebaliknya, jika nomor ini ada, maka peruntukannya tidak sesuai dengannya. Paradoks!
Cara termudah untuk mengabaikan paradoks ini adalah dengan mengacu pada informalitas notasi verbal. Misalnya, jika hanya sekumpulan ekspresi tertentu yang diperbolehkan dalam notasi, maka "angka terkecil yang delapan puluh huruf saja tidak cukup" tidak akan menjadi notasi yang valid, padahal notasi praktis berguna seperti itu "faktorial delapan" akan tetap dapat diterima.
Apakah ada cara formal untuk mendeskripsikan urutan (algoritma) tindakan pada angka? Ada, dan berlimpah - disebut bahasa pemrograman. Alih-alih notasi verbal, kita akan menggunakan program (misalnya, dengan Python) yang menampilkan angka yang diperlukan. Misalnya, untuk lima sembilan program ini cocok print("9"*5). Kami akan terus tertarik pada program terpendek untuk nomor tertentu. Durasi program seperti itu disebut angka; itu adalah batas teoretis di mana suatu bilangan tertentu dapat dikompresi.
Daripada menggunakan paradoks Berry, kita sekarang dapat mempertimbangkan paradoks serupa: Berapa angka terkecil yang tidak dapat dihasilkan oleh program kilobyte?
Kami akan beralasan dengan cara yang sama seperti sebelumnya: ada 2561024 kilobyte teks, yang berarti tidak lebih dari 2561024 angka yang dapat dihasilkan oleh program kilobyte. Artinya bilangan tertentu yang tidak lebih besar dari 2561024 tidak dapat diturunkan dengan cara ini.
Tapi mari kita tulis sebuah program dengan Python yang menghasilkan semua teks kilobyte yang mungkin, menjalankannya untuk dieksekusi, dan jika mereka mengeluarkan angka, maka tambahkan angka ini ke kamus teks yang dapat dijangkau. Setelah memeriksa seluruh 2561024 kemungkinan, tidak peduli berapa lama waktu yang dibutuhkan, program akan mencari angka terkecil yang hilang dari kamus dan mencetak angka tersebut. Tampaknya jelas bahwa program seperti itu akan masuk ke dalam satu kilobyte kode - dan akan menampilkan angka yang sama yang tidak dapat dihasilkan oleh program kilobyte!
Apa masalahnya sekarang? Hal ini tidak dapat lagi dikaitkan dengan informalitas notasi!
Jika Anda bingung dengan kenyataan bahwa program kami akan memerlukan sejumlah besar memori untuk berfungsi - kamus (atau array bit) yang terdiri dari 2561024 elemen - maka Anda dapat melakukan hal yang sama tanpanya: untuk masing-masing angka 2561024, secara bergantian , telusuri semua 2561024 program yang memungkinkan, hingga tidak ada program yang cocok. Tidak masalah bahwa pencarian seperti itu akan berlangsung lama: setelah memeriksa kurang dari (2561024)2 pasang nomor dan program, pencarian itu akan berakhir dan menemukan nomor yang sangat disayangi itu.
Atau tidak akan selesai? Memang diantara semua program yang akan dicoba pasti ada while True: pass (dan analog fungsionalnya) - dan masalahnya tidak akan lebih jauh dari menguji program semacam itu!
Berbeda dengan paradoks Berry, yang kendalanya terletak pada informalitas notasi, dalam kasus kedua kita mempunyai reformulasi yang terselubung. . Faktanya adalah tidak mungkin menentukan keluarannya dari suatu program dalam waktu yang terbatas. Khususnya, kompleksitas Kolmogorov : tidak ada algoritme yang memungkinkan, untuk suatu bilangan tertentu, menemukan panjang program terpendek yang mencetak bilangan ini; yang berarti tidak ada solusi untuk masalah Berry - untuk menemukan panjang sebutan verbal terpendek untuk suatu bilangan tertentu.
Sumber: www.habr.com