Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
749 kez görüntülendi

Kolmogorov Karmasikliginin hesaplanamaz fonksiyon(algoritma) oldugunun ispatinin acik bir halini paylasir misiniz?

Teorik Bilgisayar Bilimi kategorisinde (37 puan) tarafından  | 749 kez görüntülendi

Algorithmic Randomness and Complexity vs. Kitaplarında bulabilirsin

1 cevap

1 beğenilme 0 beğenilmeme
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.
(54 puan) tarafından 
tarafından düzenlendi
20,274 soru
21,803 cevap
73,474 yorum
2,427,488 kullanıcı