Kolmogorov Karmaşıklığı: Bir Dizenin Gerçek Bilgi İçeriği Nedir?

Bir oyun: hangisi "daha basit"?

İki dizi:

A: 01010101010101010101010101010101 (32 karakter)

B: 11010011001100101011110001001010 (32 karakter)

İkisi de 32 karakterli. Shannon entropisi ikisini de "yüksek bilgili" sayar (yarı yarıya 0/1). Ama insan sezgisiyle A basittir: "32 kere '01' yaz" şeklinde tanımlanabilir.

B ne kadar kısa tanımlanabilir? Belki sadece "yukarıdaki 32 biti birebir yaz" şeklinde — kısaltamayız.

Bu sezgiyi matematik olarak niceleyen kavram: Kolmogorov karmaşıklığı.

Tanım

Bir $x$ dizgisinin Kolmogorov karmaşıklığı $K(x)$:

$x$'i çıktı veren en kısa program (Turing makinesinin programı).

Yani $K(x)$ = en kısa $p$ uzunluğu, $U(p) = x$ olacak şekilde, $U$ bir evrensel Turing makinesi.

• Yukarıdaki A için: $K(A) \approx \log_2(32) + c \approx 5 + c$ (çünkü "32 kere 01 yaz" sözünü bilgisayara verirsek küçük program).
• B için: $K(B) \approx 32 + c$ (büyük olasılıkla basitleştirilemez, "olduğu gibi yaz"yla aynı).

Bu fonksiyon, bağımsız olarak üç matematikçi tarafından geliştirildi:

• Ray Solomonoff (1960, ABD) — felsefi indüksiyon teorisinin temeli.
• Andrey Kolmogorov (1965, SSCB) — Olasılık tanımı.
• Gregory Chaitin (1969, IBM/Buenos Aires) — 18 yaşında.

Aynı kavramı üç farklı motivasyonla buldular.

Önemli özellikler

1. Makine-bağımsızlık (asimptotik)

$K_U(x)$, kullanılan Turing makinesi $U$'ya bağlıdır. Ama bağımlılık bir sabite kadar:

$|K_{U_1}(x) - K_{U_2}(x)| \leq c_{U_1, U_2}$

Çünkü bir makine diğerini simüle edebilir; simülatör programı sabit uzunlukta. Bu yüzden Kolmogorov karmaşıklığı bir "evrensel sabit"e kadar iyi tanımlıdır.

2. Hesaplanamazlık

$K(x)$ hesaplanamazdır. Yani genel olarak bir dizgi için Kolmogorov karmaşıklığını bilgisayar bulamaz.

İspat (Berry paradoksu tarzı): Eğer $K$ hesaplanabilir olsaydı, "ilk dizgi $x$ ki $K(x) > 1000$" diye bir program yazabilirdik. Bu program çok kısa — diyelim 200 karakter. O zaman $K(x) \leq 200$. Çelişki.

Bu hesaplanamazlık temel sınırdır. Yine de yaklaşık kullanılabilir.

3. Sıkıştırılabilirlik

$x$ sıkıştırılabilirdir ⟺ $K(x) < |x|$. Yani Kolmogorov karmaşıklığı dizgisinin uzunluğundan küçük.

A dizgisi için $K(A) \ll |A|$ → sıkıştırılabilir.
B dizgisi için $K(B) \approx |B|$ → sıkıştırılamaz.

Rastgelelik tanımı

Algoritmik rastgelelik (Martin-Löf rastgelelik): Bir dizgi $x$ "rastgele" sayılır eğer $K(x) \geq |x| - c$ ise (sabit $c$).

Bu doğal tanımdır:

• Pi sayısının basamakları rastgele görünür ama $K$ küçük (kısa formülle hesaplanabilir).
• Gerçek zar atış serisi $K$ büyük → algoritmik rastgele.

Klasik olasılığa göre $\pi$'nin basamakları istatistiksel olarak rastgeledir (her basamak ~%10 olasılıkta). Ama algoritmik anlamda rastgele değildir.

Bu fark, Kolmogorov karmaşıklığının matematiksel zarafetidir.

Chaitin sabiti $\Omega$

Gregory Chaitin'in inşa ettiği garip bir gerçek sayı:

$\Omega = \sum_{p \text{ duran}} 2^{-|p|}$

(Tüm duran programların ağırlıklı toplamı.)

Özellikleri:

• $\Omega \in (0, 1)$.
• Hesaplanamaz — basamakları algoritma ile üretilemez.
• Algoritmik olarak rastgele — basamak dizisinin Kolmogorov karmaşıklığı her zaman maksimum.
• Bilgi ile dolu: $\Omega$'nın ilk $n$ basamağı bilinirse, $n$ karakterlik tüm halting problemlerini çözer.

$\Omega$ bilinen en garip ve en derin sayılardan biridir. Hesaplanamaz ama tanımı son derece açık.

Solomonoff indüksiyonu

Kolmogorov karmaşıklığının felsefi uygulaması: Solomonoff prior.

Bir veri kümesini açıklayan birden fazla model varsa, en kısa olanı seç (Occam'ın usturası matematik formu).

$P(M \mid \text{data}) \propto 2^{-K(M)} \cdot P(\text{data} \mid M)$

Bu, Bayesyen indüksiyonun ideal halidir: tüm hipotezlere prior ver, en sadeleri ağırlıkla. Modern yapay zeka teorisinin (özellikle AIXI, Marcus Hutter) temeli.

Hesaplanamaz ama felsefi olarak doğru olduğu kabul edilir. Modern derin öğrenme yöntemlerinin de "gerçek hedefe" doğru yönelmesi gerektiği iddia edilen sınır.

Pratik kullanım: sıkıştırma oranı bir K yaklaşımıdır

zip, gzip, xz gibi sıkıştırma araçları:

• Bir dizgiyi sıkıştırırlar.
• Sıkıştırılmış boyut $\approx K(x)$ + sabit.

Yani dosyanın sıkıştırılmış boyutu Kolmogorov karmaşıklığının pratik yaklaşımıdır. Bu, NCD (Normalized Compression Distance) gibi tekniklerin temeli:

• İki dize $x, y$ arasındaki "benzerlik": $\frac{K(xy) - \min(K(x), K(y))}{\max(K(x), K(y))}$.
• Pratikte: sıkıştırma yaklaşıkları ile.

Bu yaklaşımlarla plagiarism detection, DNA benzerlik, müzik tür sınıflandırma ve dil sınıflandırma yapılır.

Shannon entropisi vs Kolmogorov karmaşıklığı

İkisi yakın akraba ama farklı:

Özellik	Shannon	Kolmogorov
Ne	Olasılık dağılımı	Tek dizgi
Hesap	Hesaplanabilir	Hesaplanamaz
Konu	İstatistiksel rastgelelik	Algoritmik rastgelelik
Yıl	1948 (Shannon)	1960-1969 (Solomonoff-Kolmogorov-Chaitin)
Birim	Bit (ortalama)	Bit (en kötü hal)

İki kavram derin bağlantılar: rastgele dizilerin Kolmogorov karmaşıklığı, Shannon entropisinin "dağılım üzerinden" değil "örnek üzerinden" karşılığıdır.

Uygulamalar

1. Veri sıkıştırma teorisi

Modern algoritmaların alt sınır kanıtları.

2. Yapay zeka

Universal AI (Hutter'ın AIXI) Kolmogorov karmaşıklığını temel alır.

3. Biyoinformatik

DNA dizilerinin "benzerlik" ölçümünde NCD.

4. Cybersecurity

Anomali tespiti: ağ trafiğinin "beklenmedik karmaşıklıkları" anomali işareti.

5. Felsefe ve epistemoloji

Bilimsel teorilerin sade olması neden iyidir? Solomonoff Kolmogorov karmaşıklığı sayesinde matematik destekli.

Sonuç

Kolmogorov karmaşıklığı:

• Bir nesnenin "gerçek bilgi içeriği"ni niceler.
• Hesaplanamaz ama felsefi olarak temel.
• Solomonoff-Kolmogorov-Chaitin üçlüsünün eseri.
• Modern AI, biyoinformatik, kriptografi'de pratik yaklaşımlarla kullanılır.
• Rastgelelik, Occam ustası, bilim felsefesi'nin matematik temeli.

Bir dizgi "01010101..." mi yoksa gerçek zar atış serisi mi — bu farkı istatistiksel olarak değil, algoritmik olarak ölçen Kolmogorov karmaşıklığıdır.

Üç matematikçi, üç ülkede, aynı yıl civarında, aynı kavramı buldular. Solomonoff (Boston), Kolmogorov (Moskova), Chaitin (Buenos Aires). Bu eşzamanlılık, Kolmogorov karmaşıklığının doğal bir kavram olduğunu — sanki orada zaten varmış gibi — kanıtlar.