Kompleksitas Kolmogorov: Mengapa Anda membutuhkan lebih banyak byte daripada string itu sendiri?

Saya sedang membaca entri Wikipedia tentang Kolmogorov Complexity ( berkat pertanyaan ini ), yang menyatakan:

Dapat ditunjukkan bahwa kompleksitas Kolmogorov dari string apa pun tidak boleh lebih dari beberapa byte lebih besar dari panjang string itu sendiri.

Mengapa Anda perlu lebih dari string itu sendiri untuk menggambarkannya?

Nilai pasti dari kompleksitas Kolmogorov tergantung pada bahasa yang dipilih untuk mewakili string. Bahasa ini harus lengkap Turing, jadi mewakili semua string karena mereka sendiri bukanlah pilihan.

Menurut prinsip pigeonhole, jika setidaknya ada satu untaian panjang paling banyak yang representasinya lebih pendek dari dirinya sendiri, maka ada juga setidaknya satu untaian panjang paling banyak n yang representasinya lebih panjang dari dirinya sendiri. (Representasi adalah algoritma kompresi.)$n$$n$

Anda dapat memiliki bahasa deskripsi di mana setiap string memiliki representasi yang paling banyak satu bit lebih lama daripada dirinya sendiri: mulai setiap representasi dengan bit yang menunjukkan "cetak secara harfiah" atau "interpretasikan". Tidak semua bahasa deskripsi sesederhana itu.

$C$$C$

Deskripsi string yang dipertimbangkan di sini adalah input ke beberapa mesin Turing universal. Anda dapat menganggapnya sebagai program C. String hello worldtidak, dengan sendirinya, membentuk program C, tapi yang berikut ini tidak: int main(int argc, char *argv[]) { printf("hello world"); }. Seperti yang Anda lihat, overhead tetap tetapi tidak nol.