Sonat Süer'in şu yazısına bakabilirsiniz:
https://sonatsuer.github.io/kolmogorov-complexity-1.html
Verilen bir 0,1-dizesinin Kolmogorov karmaşıklığını hesaplayan bir algoritma $A:x \to C(x)$ olduğunu varsayalım.
Bu algoritma ile bir dizenin boyu ile karmaşıklığını etkin olarak karşılaştırabiliriz. $|x| \leq C(x)$ ise kısaca $x$'e sıkıştırılamaz diyelim.
Dolayısıyla doğal sayılardan ikilik dizelere şu kısmi fonksiyonu hesaplayan bir algoritma oluşturabiliriz: $B: n \to \text{ "sıkıştırılamaz n uzunluğundaki ilk dize" }$ (ilk derken dizeleri leksikografik sıraya göre düşünebiliriz: 0, 1; 00, 01, 10, 11 vb.)
Şimdi bu fonksiyonun/algoritmanın girdi boyu log n, yani çıktının karmaşıklığı en fazla log n olabilir (eklenecek O(1)'leri ihmal ediyorum). Oysa çıktının boyu n ve tanım gereği çıktı sıkıştırılamaz. Fonksiyonun hiçbir n için tanımlı olmaması da mümkün değil çünkü tüm dizeler sıkıştırılabilir olamaz, sonsuz tane sıkıştırılamaz dize olmalı (bu cümlenin ispatını bildiğinizi veya sezgisel olarak açık olduğunu varsayıyorum). Çelişki! Demek baştaki varsayımımız yanlışmış. Kolmogorov karmaşıklığını hesaplayan bir algoritma olamazmış.
Biçimsel bir kanıt için sabitleri (O(1)) eklemek gerekiyor, ancak teknik bir zorluk yok çünkü n zaten log n'e asemtotik olarak üstün.