Kolmogorov Karmaşıklığı: Bir Şeyin Ne Kadar “Karmaşık” Olduğunu Nasıl Ölçeriz?

Önünüzde iki sayı dizisi olduğunu hayal edin; Kolmogorov Karmaşıklığı kavramını bu bağlamda düşünün.

Birinci dizi:

0101010101010101010101010101010101010101

İkinci dizi:

0110100010111011001010010111001011010010

Size soruyorum: Hangisi daha karmaşık? Elbette ikincisi, değil mi? Birincisi “01” deseninin tekrarından ibaret; ikincisi ise rastgele atılmış yazı tura gibi görünüyor. Peki ama neden? İkisi de aynı uzunlukta, ikisi de sadece sıfır ve birlerden oluşuyor. İkincisinin “daha karmaşık” olduğunu hissetmemizi sağlayan şey tam olarak ne?

İşte Kolmogorov karmaşıklığı, bu sezgiyi matematiksel bir zemine oturtma çabasıdır. Cevap şaşırtıcı derecede zariftir: Bir şey, onu üreten en kısa talimat ne kadar uzunsa o kadar karmaşıktır.

Birinci diziyi üretmek için gereken talimat çok kısadır: “01’i kırk kez yaz.” İkinci diziyi üretmek içinse, o diziyi olduğu gibi ezberleyip yazdırmaktan daha kısa bir yol yok gibidir. Talimat, dizinin kendisi kadar uzun. İşte karmaşıklığın özü budur: Bir nesnenin karmaşıklığı, onu tarif etmenin en kısa yolunun uzunluğudur.

Bu fikir ilk bakışta basit görünür ama altını kazdığınızda, matematiğin en derin kuyularından birine düşersiniz: Rastgelelik nedir? Bilgi nedir? Hangi şeyleri bilebiliriz, hangilerini asla bilemeyiz?

Fikir: Sıkıştırmanın Ötesinde

Gündelik hayatta bu fikrin bir versiyonunu zaten kullanıyoruz.

Bilgisayarınızda bir metin dosyasını ZIP’lediğinizde ne olur?

Çünkü metnin içinde tekrarlanan desenler vardır.

Sıkıştırma algoritması bu desenleri bulup yerine daha kısa kodlar koyar.

Bu durumu Kolmogorov Karmaşıklığı açısından da açıklayabiliriz.

Ama şunu deneyin: Gerçekten rastgele bir veri dosyasını (örneğin iyi bir rastgele sayı üreticisinin çıktısını) ZIP’lemeye çalışın. Neredeyse hiç küçülmez. Hatta bazen biraz büyür. Çünkü rastgele veride sömürülecek bir desen, yakalanacak bir düzen yoktur. Rastgelelik, tanımı gereği, sıkıştırılamaz olandır.

Kolmogorov Karmaşıklığı işte bu sıkıştırma fikrini en uç noktasına taşır.

Bir dosyayı ZIP’lemek yerine, onu bir bilgisayar programına dönüştürdüğünüzü düşünün.

Program çalıştığında dosyayı üretsin.

Program ne kadar kısaysa, dosya o kadar basit demektir.

Olabilecek en kısa programın uzunluğu, o dosyanın karmaşıklığıdır.

Küçük Bir Tarih: Üç Adam, Bir Fikir

Bu fikir, 1960’ların başında neredeyse aynı anda üç farklı kişi tarafından, üç farklı amaçla ortaya atıldı:

• Ray Solomonoff (1926–2009), yapay zekaya matematiksel bir temel arıyordu. Bir veri dizisinin en kısa açıklamasının, o dizinin geleceğini tahmin etmenin en iyi yolu olduğunu fark etti.
• Andrey Kolmogorov (1903–1987), olasılık teorisinin devi, “rastgelelik” kavramını olasılıktan bağımsız olarak tanımlamak istiyordu. Bir dizi, onu üreten en kısa program kendisinden kısaysa rastgele değildir; değilse rastgeledir, diye düşündü.
• Gregory Chaitin (1947–), daha genç bir matematikçi olarak aynı fikre ulaştı ve onu Gödel’in ünlü eksiklik teoremine bağlayarak matematiğin temellerine dair şaşırtıcı sonuçlar çıkardı.

Bugün bu alana algoritmik bilgi kuramı (algorithmic information theory) denir. Kolmogorov, konuyu sistematik biçimde ele aldığı için ölçü onun adıyla anılır; Solomonoff ve Chaitin’in katkıları da en az onunki kadar temeldir.

Pi Sayısı: Karmaşık Görünen, Basit Olan

Kolmogorov karmaşıklığının gücünü gösteren en güzel örneklerden biri pi sayısıdır. Pi’nin basamaklarını yazın:

3.141592653589793238462643383279502884197...

Bu basamaklar tamamen rastgele görünür. İstatistiksel testlerin neredeyse tamamından “rastgele bir dizi” olarak geçerler; her rakam yaklaşık eşit sıklıkta görünür, hiçbir öngörülebilir desen yoktur. Ama pi’nin Kolmogorov karmaşıklığı çok küçüktür! Çünkü pi’yi milyonlarca basamağa kadar üretebilen kısacık programlar yazılabilir. Birkaç satırlık bir formül (örneğin bir Machin formülü ya da Chudnovsky algoritması), istediğiniz kadar pi basamağı üretir.

Yani pi’nin basamakları istatistiksel olarak rastgele ama algoritmik olarak basittir. Bu ayrım, Kolmogorov karmaşıklığının bize kazandırdığı en değerli içgörülerden biridir: “Rastgele görünmek” ile “rastgele olmak” aynı şey değildir. Gerçek rastgelelik, istatistiksel testlerle değil, sıkıştırılamazlıkla tanımlanır.

Teknik Bölüm: Tanımı Kesinleştirmek

Şimdi konuyu biraz matematikselleştirelim.

Bir “bilgisayar programı” derken neyi kastettiğimizi kesinleştirmemiz gerekir. Matematikçiler bunun için Turing makinesi kavramını kullanır. Turing makinesi, bir şerit üzerinde semboller okuyup yazan, sonlu sayıda durumu olan soyut bir makinedir. Bugünkü bütün bilgisayarlar, prensipte bir Turing makinesinin yapabildiği her şeyi yapabilir. Bu yüzden “en kısa program” derken “en kısa Turing makinesi programı” demek güvenlidir.

File:Example of a Turing makine.svg

Bir Turing makinesinin şematik gösterimi: sonsuz bir şerit, bir okuma-yazma kafası ve sonlu sayıda durum. Kolmogorov karmaşıklığının tanımı böyle soyut bir makineye dayanır.

Şimdi bir x dizisi (string) alalım. x‘in Kolmogorov karmaşıklığı şöyle tanımlanır:

K(x) = x‘i üreten en kısa programın uzunluğu.

Daha kesin olarak: Bir U evrensel Turing makinesi (evrensel programlanabilir bilgisayar) seçeriz. U(p) = x olacak şekilde bir p programı varsa ve bu programların en kısasının uzunluğu |p| ise:

K_U(x) = min { |p| : U(p) = x }

Bu tanımda bir tuhaflık var: U makinesine bağlı olması. Python bilgisayarıyla JavaScript bilgisayarı farklı sonuç verir mi? Teknik olarak evet, ama burada devreye değişmezlik teoremi (invariance theorem) girer:

İki farklı evrensel makine U ve V arasındaki fark, yalnızca sabit bir c kadardır:
K_U(x) ≤ K_V(x) + c

Yani makine seçimi, karmaşıklığı bir sabite kadar etkiler. Uzun diziler için bu sabit önemsizleşir. Bu yüzden K(x)‘i, makineden bağımsız bir büyüklük olarak düşünebiliriz. Bu teorem, Kolmogorov karmaşıklığını anlamlı kılan temel taştır.

Temel Özellikler

Kolmogorov karmaşıklığının birkaç temel özelliği vardır; bunlar hem sezgiseldir hem de derin sonuçlara kapı açar.

1. Hiçbir dizi kendisinden çok daha karmaşık olamaz.
Her x dizisi için, “x’i olduğu gibi yazdır” diyen bir program vardır. Bu programın uzunluğu kabaca |x| artı sabit bir ek kadardır. Yani:

K(x) ≤ |x| + O(1)

En kötü durumda bile, diziyi ham haliyle gömüp yazdırabilirsiniz.

2. Çoğu dizi neredeyse tamamen sıkıştırılamaz.
Bu belki de en şaşırtıcı sonuçtur. Uzunluğu n olan 2^n tane dizi vardır. Ama uzunluğu n - 10‘dan kısa olan programların sayısı yalnızca 1 + 2 + 4 + ... + 2^{n-11} < 2^{n-10} tanedir. Yani en fazla 2^{n-10} dizi, n - 10dan daha kısa bir programla üretilebilir. Bu, 2^n dizinin ufacık bir kesridir. Sonuç: Dizilerin ezici çoğunluğu rastgeledir, yani sıkıştırılamaz. Rastgelelik bir istisna değil, kuraldır.

3. Karmaşıklık hesaplanamaz.
K(x)‘i hesaplayan bir algoritma yazamazsınız. İstediğiniz kadar akıllı bir program yazın, hiçbir zaman bir dizinin gerçek Kolmogorov karmaşıklığını garantili olarak bulamaz. Bunun nedeni, “bu program durur mu?” sorusunun (durma problemi) çözülemez olmasıdır. Daha kısa bir program arayışı, bazı programların sonsuza kadar çalışıp çalışmayacağını bilmeyi gerektirir — ve bu, Turing’in 1936’da kanıtladığı gibi, prensipte imkânsızdır.

Berry Paradoksu: Hesaplanamazlığın Derin Nedeni

Bu hesaplanamazlığın arkasında güzel bir paradoks yatar. Şu cümleyi düşünün:

“Yüz kelimeden daha azıyla tanımlanamayan en küçük doğal sayı.”

Bu cümle, bir doğal sayıyı tanımlıyor gibi görünüyor. Ama cümlenin kendisi yüz kelimeden az! Yani o sayı, yüz kelimeden azıyla tanımlanabiliyor — tanım gereği tanımlanamaz olması gerekirken. Bu, Berry paradoksudur. Paradoksun kaynağı, “tanımlanabilirlik” kavramının kendisinin kaygan olmasıdır.

Chaitin, Kolmogorov karmaşıklığının hesaplanamazlığının tam olarak bu paradoksun formalı bir versiyonu olduğunu gösterdi. Eğer K(x)‘i hesaplayabilseydik, “Karmaşıklığı n’den büyük olan en küçük dizi”yi bulan bir program yazabilirdik. Ama bu programın kendisi kısa olurdu (neyi içerir, artı küçük bir sabit), bu da o dizinin karmaşıklığının aslında n’den küçük olmasına yol açardı — çelişki. Yani karmaşıklığı hesaplayabilmek, mantıksal bir çelişkiye düşmeden mümkün değildir.

Chaitin’in Ω Sayısı: Rastgeleliğin Somutlaşmış Hali

Chaitin, bu fikirlerden yola çıkarak matematiğin en tuhaf nesnelerinden birini inşa etti: Ω (Omega) sayısı.

Ω, rastgele seçilen bir programın durma olasılığıdır. Şöyle tanımlanır: Bütün geçerli programları kısalıklarına göre sıralarız. Ω, duran programların toplam “ağırlığıdır”:

Ω = Σ 2^{-|p|}   (p duran programlar üzerinden)

Bu sayı 0 ile 1 arasında bir gerçek sayıdır. Ve şaşırtıcı özellikleri vardır:

• Ω’nın basamakları, tanımı gereği algoritmik olarak rastgeledir. Yani Ω’nın ilk n basamağını üreten program, n’den kısa olamaz. Ω, sıkıştırılamaz.
• Ama Ω iyi tanımlıdır! Tek ve belirli bir sayıdır; rastgele bir süreçle üretilmemiştir. Sadece, onun hakkında bilgi edinmek imkânsızdır.
• Ω’nın basamaklarını bilmek, durma problemini çözmek demektir. Yani Ω’nın ilk birkaç bin basamağını bilseydiniz, matematiğin en ünlü açık problemlerini (örneğin Riemann hipotezinin doğruluğunu) otomatik olarak çözebilirdiniz.

Ω, “rastgele” ile “tanımlı” kavramlarının birbirine zıt olmadığının en çarpıcı kanıtıdır. Bir şey hem tamamen belirli hem de tamamen öngörülemez olabilir.

Koşullu Karmaşıklık ve Bilgi

Şimdi bir adım ileri gidelim. x‘in y verildiğinde koşullu karmaşıklığı şöyle tanımlanır:

K(x | y) = y'yi girdi olarak alıp x'i üreten en kısa programın uzunluğu

Bu kavramla “bilgi” kavramını genelleştirebiliriz. y‘nin x hakkında ne kadar bilgi taşıdığı şudur:

I(x : y) ≈ K(x) - K(x | y)
````x` dizisi (string) alalım. `x`'in **Kolmogorov karmaşıklığı** şöyle tanımlanır:

> `K(x) = x`'i üreten en kısa programın uzunluğu.

Daha kesin olarak: Bir `U` evrensel Turing makinesi (evrensel programlanabilir bilgisayar) seçeriz. `U(p) = x` olacak şekilde bir `p` programı varsa ve bu programların en kısasının uzunluğu `|p|` ise:

K_U(x) = min { |p| : U(p) = x }

Bu tanımda bir tuhaflık var: `U` makinesine bağlı olması. Python bilgisayarıyla JavaScript bilgisayarı farklı sonuç verir mi? Teknik olarak evet, ama burada devreye **değişmezlik teoremi** (invariance theorem) girer:

> İki farklı evrensel makine `U` ve `V` arasındaki fark, yalnızca sabit bir `c` kadardır:
> `K_U(x) ≤ K_V(x) + c`

Yani makine seçimi, karmaşıklığı bir sabite kadar etkiler. Uzun diziler için bu sabit önemsizleşir. Bu yüzden `K(x)`'i, makineden bağımsız bir büyüklük olarak düşünebiliriz. Bu teorem, Kolmogorov karmaşıklığını anlamlı kılan temel taştır.

---

### Temel Özellikler

Kolmogorov karmaşıklığının birkaç temel özelliği vardır; bunlar hem sezgiseldir hem de derin sonuçlara kapı açar.

**1. Hiçbir dizi kendisinden çok daha karmaşık olamaz.**
Her `x` dizisi için, "x'i olduğu gibi yazdır" diyen bir program vardır. Bu programın uzunluğu kabaca `|x|` artı sabit bir ek kadardır. Yani:

K(x) ≤ |x| + O(1)

En kötü durumda bile, diziyi ham haliyle gömüp yazdırabilirsiniz.

**2. Çoğu dizi neredeyse tamamen sıkıştırılamaz.**
Bu belki de en şaşırtıcı sonuçtur. Uzunluğu `n` olan `2^n` tane dizi vardır. Ama uzunluğu `n - 10`'dan kısa olan programların sayısı yalnızca `1 + 2 + 4 + ... + 2^{n-11} < 2^{n-10}` tanedir. Yani en fazla `2^{n-10}` dizi, `n - 10`dan daha kısa bir programla üretilebilir. Bu, `2^n` dizinin ufacık bir kesridir. **Sonuç: Dizilerin ezici çoğunluğu rastgeledir, yani sıkıştırılamaz.** Rastgelelik bir istisna değil, kuraldır.

**3. Karmaşıklık hesaplanamaz.**
`K(x)`'i hesaplayan bir algoritma yazamazsınız. İstediğiniz kadar akıllı bir program yazın, hiçbir zaman bir dizinin gerçek Kolmogorov karmaşıklığını garantili olarak bulamaz. Bunun nedeni, "bu program durur mu?" sorusunun (durma problemi) çözülemez olmasıdır. Daha kısa bir program arayışı, bazı programların sonsuza kadar çalışıp çalışmayacağını bilmeyi gerektirir — ve bu, Turing'in 1936'da kanıtladığı gibi, prensipte imkânsızdır.

---

### Berry Paradoksu: Hesaplanamazlığın Derin Nedeni

Bu hesaplanamazlığın arkasında güzel bir paradoks yatar. Şu cümleyi düşünün:

> *"Yüz kelimeden daha azıyla tanımlanamayan en küçük doğal sayı."*

Bu cümle, bir doğal sayıyı tanımlıyor gibi görünüyor. Ama cümlenin kendisi yüz kelimeden az! Yani o sayı, yüz kelimeden azıyla tanımlanabiliyor — tanım gereği tanımlanamaz olması gerekirken. Bu, **Berry paradoksudur**. Paradoksun kaynağı, "tanımlanabilirlik" kavramının kendisinin kaygan olmasıdır.

Chaitin, Kolmogorov karmaşıklığının hesaplanamazlığının tam olarak bu paradoksun formalı bir versiyonu olduğunu gösterdi. Eğer `K(x)`'i hesaplayabilseydik, "Karmaşıklığı n'den büyük olan en küçük dizi"yi bulan bir program yazabilirdik. Ama bu programın kendisi kısa olurdu (neyi içerir, artı küçük bir sabit), bu da o dizinin karmaşıklığının aslında n'den küçük olmasına yol açardı — çelişki. Yani karmaşıklığı hesaplayabilmek, mantıksal bir çelişkiye düşmeden mümkün değildir.

---

### Chaitin'in Ω Sayısı: Rastgeleliğin Somutlaşmış Hali

Chaitin, bu fikirlerden yola çıkarak matematiğin en tuhaf nesnelerinden birini inşa etti: **Ω (Omega) sayısı.**

Ω, rastgele seçilen bir programın durma olasılığıdır. Şöyle tanımlanır: Bütün geçerli programları kısalıklarına göre sıralarız. Ω, duran programların toplam "ağırlığıdır":

Ω = Σ 2^{-|p|} (p duran programlar üzerinden)

Bu sayı 0 ile 1 arasında bir gerçek sayıdır. Ve şaşırtıcı özellikleri vardır:

- Ω'nın basamakları, **tanımı gereği algoritmik olarak rastgeledir**. Yani Ω'nın ilk n basamağını üreten program, n'den kısa olamaz. Ω, sıkıştırılamaz.
- Ama Ω **iyi tanımlıdır**! Tek ve belirli bir sayıdır; rastgele bir süreçle üretilmemiştir. Sadece, onun hakkında bilgi edinmek imkânsızdır.
- Ω'nın basamaklarını bilmek, durma problemini çözmek demektir. Yani Ω'nın ilk birkaç bin basamağını bilseydiniz, matematiğin en ünlü açık problemlerini (örneğin Riemann hipotezinin doğruluğunu) otomatik olarak çözebilirdiniz.

Ω, "rastgele" ile "tanımlı" kavramlarının birbirine zıt olmadığının en çarpıcı kanıtıdır. Bir şey hem tamamen belirli hem de tamamen öngörülemez olabilir.

---

### Koşullu Karmaşıklık ve Bilgi

Şimdi bir adım ileri gidelim. `x`'in **y verildiğinde koşullu karmaşıklığı** şöyle tanımlanır:

K(x | y) = y’yi girdi olarak alıp x’i üreten en kısa programın uzunluğu

Bu kavramla "bilgi" kavramını genelleştirebiliriz. `y`'nin `x` hakkında ne kadar bilgi taşıdığı şudur:

I(x : y) ≈ K(x) – K(x | y)
““xdizisi (string) alalım.x`’in Kolmogorov karmaşıklığı şöyle tanımlanır:

K(x) = x‘i üreten en kısa programın uzunluğu.

Daha kesin olarak: Bir U evrensel Turing makinesi (evrensel programlanabilir bilgisayar) seçeriz. U(p) = x olacak şekilde bir p programı varsa ve bu programların en kısasının uzunluğu |p| ise:

K_U(x) = min { |p| : U(p) = x }

Bu tanımda bir tuhaflık var: U makinesine bağlı olması. Python bilgisayarıyla JavaScript bilgisayarı farklı sonuç verir mi? Teknik olarak evet, ama burada devreye değişmezlik teoremi (invariance theorem) girer:

İki farklı evrensel makine U ve V arasındaki fark, yalnızca sabit bir c kadardır:
K_U(x) ≤ K_V(x) + c

Yani makine seçimi, karmaşıklığı bir sabite kadar etkiler. Uzun diziler için bu sabit önemsizleşir. Bu yüzden K(x)‘i, makineden bağımsız bir büyüklük olarak düşünebiliriz. Bu teorem, Kolmogorov karmaşıklığını anlamlı kılan temel taştır.

Temel Özellikler

Kolmogorov karmaşıklığının birkaç temel özelliği vardır; bunlar hem sezgiseldir hem de derin sonuçlara kapı açar.

1. Hiçbir dizi kendisinden çok daha karmaşık olamaz.
Her x dizisi için, “x’i olduğu gibi yazdır” diyen bir program vardır. Bu programın uzunluğu kabaca |x| artı sabit bir ek kadardır. Yani:

K(x) ≤ |x| + O(1)

En kötü durumda bile, diziyi ham haliyle gömüp yazdırabilirsiniz.

2. Çoğu dizi neredeyse tamamen sıkıştırılamaz.
Bu belki de en şaşırtıcı sonuçtur. Uzunluğu n olan 2^n tane dizi vardır. Ama uzunluğu n - 10‘dan kısa olan programların sayısı yalnızca 1 + 2 + 4 + ... + 2^{n-11} < 2^{n-10} tanedir. Yani en fazla 2^{n-10} dizi, n - 10dan daha kısa bir programla üretilebilir. Bu, 2^n dizinin ufacık bir kesridir. Sonuç: Dizilerin ezici çoğunluğu rastgeledir, yani sıkıştırılamaz. Rastgelelik bir istisna değil, kuraldır.

3. Karmaşıklık hesaplanamaz.
K(x)‘i hesaplayan bir algoritma yazamazsınız. İstediğiniz kadar akıllı bir program yazın, hiçbir zaman bir dizinin gerçek Kolmogorov karmaşıklığını garantili olarak bulamaz. Bunun nedeni, “bu program durur mu?” sorusunun (durma problemi) çözülemez olmasıdır. Daha kısa bir program arayışı, bazı programların sonsuza kadar çalışıp çalışmayacağını bilmeyi gerektirir — ve bu, Turing’in 1936’da kanıtladığı gibi, prensipte imkânsızdır.

Berry Paradoksu: Hesaplanamazlığın Derin Nedeni

Bu hesaplanamazlığın arkasında güzel bir paradoks yatar. Şu cümleyi düşünün:

“Yüz kelimeden daha azıyla tanımlanamayan en küçük doğal sayı.”

Bu cümle, bir doğal sayıyı tanımlıyor gibi görünüyor. Ama cümlenin kendisi yüz kelimeden az! Yani o sayı, yüz kelimeden azıyla tanımlanabiliyor — tanım gereği tanımlanamaz olması gerekirken. Bu, Berry paradoksudur. Paradoksun kaynağı, “tanımlanabilirlik” kavramının kendisinin kaygan olmasıdır.

Chaitin, Kolmogorov karmaşıklığının hesaplanamazlığının tam olarak bu paradoksun formalı bir versiyonu olduğunu gösterdi. Eğer K(x)‘i hesaplayabilseydik, “Karmaşıklığı n’den büyük olan en küçük dizi”yi bulan bir program yazabilirdik. Ama bu programın kendisi kısa olurdu (neyi içerir, artı küçük bir sabit), bu da o dizinin karmaşıklığının aslında n’den küçük olmasına yol açardı — çelişki. Yani karmaşıklığı hesaplayabilmek, mantıksal bir çelişkiye düşmeden mümkün değildir.

Chaitin’in Ω Sayısı: Rastgeleliğin Somutlaşmış Hali

Chaitin, bu fikirlerden yola çıkarak matematiğin en tuhaf nesnelerinden birini inşa etti: Ω (Omega) sayısı.

Ω, rastgele seçilen bir programın durma olasılığıdır. Şöyle tanımlanır: Bütün geçerli programları kısalıklarına göre sıralarız. Ω, duran programların toplam “ağırlığıdır”:

Ω = Σ 2^{-|p|}   (p duran programlar üzerinden)

Bu sayı 0 ile 1 arasında bir gerçek sayıdır. Ve şaşırtıcı özellikleri vardır:

• Ω’nın basamakları, tanımı gereği algoritmik olarak rastgeledir. Yani Ω’nın ilk n basamağını üreten program, n’den kısa olamaz. Ω, sıkıştırılamaz.
• Ama Ω iyi tanımlıdır! Tek ve belirli bir sayıdır; rastgele bir süreçle üretilmemiştir. Sadece, onun hakkında bilgi edinmek imkânsızdır.
• Ω’nın basamaklarını bilmek, durma problemini çözmek demektir. Yani Ω’nın ilk birkaç bin basamağını bilseydiniz, matematiğin en ünlü açık problemlerini (örneğin Riemann hipotezinin doğruluğunu) otomatik olarak çözebilirdiniz.

Ω, “rastgele” ile “tanımlı” kavramlarının birbirine zıt olmadığının en çarpıcı kanıtıdır. Bir şey hem tamamen belirli hem de tamamen öngörülemez olabilir.

Koşullu Karmaşıklık ve Bilgi

Şimdi bir adım ileri gidelim. x‘in y verildiğinde koşullu karmaşıklığı şöyle tanımlanır:

K(x | y) = y'yi girdi olarak alıp x'i üreten en kısa programın uzunluğu

Bu kavramla “bilgi” kavramını genelleştirebiliriz. y‘nin x hakkında ne kadar bilgi taşıdığı şudur:

I(x : y) ≈ K(x) - K(x | y)

Yani, y‘yi bilmek x‘i üretmeyi ne kadar kısaltıyorsa, y o kadar çok bilgi içeriyor demektir. Bu, Shannon’ın klasik bilgi kuramındaki karşılıklı bilgi kavramının algoritmik versiyonudur. Shannon’ın kuramı ortalama bilgiyle ilgilenir; Kolmogorov’unki ise tek tek nesnelerin bilgisiyle. Bu yüzden Kolmogorov karmaşıklığı bazen “Shannon’ın kuramının bireyselleştirilmiş hali” olarak anılır.

Uygulamalar: Nerelerde Karşımıza Çıkıyor?

Bu soyut fikir, şaşırtıcı sayıda alanda pratik yankı bulur.

1. Occam’ın Usturası ve Bilimsel Yöntem.
Bilimde rakip iki teori varsa, daha basit olanı tercih ederiz. Ama “basit” ne demek? Kolmogorov karmaşıklığı buna bir cevap sunar: Daha basit teori, veriyi daha kısa programla açıklayan teoridir. Aslında Solomonoff’un orijinal motivasyonu buydu: Veriyi en kısa açıklayan hipotez, geleceği en iyi tahmin eden hipotezdir. Buna Solomonoff tümevarımı denir ve modern yapay zekânın teorik temellerinden biri sayılır.

2. Minimum Tanım Uzunluğu (MDL).
İstatistik ve makine öğrenmesinde, model seçimi için MDL ilkesi kullanılır. Bir veri setini açıklamak için gereken toplam uzunluk = modelin uzunluğu + verinin model verildiğinde kalan açıklama uzunluğu. Bu toplamı minimize eden model seçilir. Bu, aşırı uyum (overfitting) sorununa karşı prensipli bir çözümdür.

3. Sıkıştırma ve Veri Madenciliği.
Bir veri setini ne kadar sıkıştırabildiğiniz, içinde ne kadar yapı olduğunu ölçer. Sıkıştırma tabanlı benzerlik ölçüleri, metin sınıflandırma, müzik türü tespiti, hatta biyolojik dizilerin karşılaştırılmasında kullanılır.

4. Biyoloji ve DNA.
DNA, doğanın yazdığı bir programdır. Bir organizmanın genomunun Kolmogorov karmaşıklığı, onun “biyolojik karmaşıklığının” bir ölçüsü olarak tartışılır. Bir amipin genomu, bir insanınkinden daha mı “basittir”? Genom uzunluğu bundan daha kötü bir ölçüdür; sıkıştırılabilirlik çok daha bilgilendirici olabilir. (Elbette pratikte gerçek K değerini hesaplayamayız, ama yaklaşık sıkıştırıcılar fikir verir.)

5. Kriptografi.
İyi bir şifreleme, çıktıyı sıkıştırılamaz hale getirmelidir. Eğer şifreli metin sıkıştırılabiliyorsa, içinde yapı var demektir ve bu bir güvenlik açığıdır. Rastgelelik, kriptografinin can damarıdır — ve Kolmogorov, rastgeleliğin en titiz tanımını verir.

Sınırlar ve Uyarılar

Dürüst olmak gerekirse, Kolmogorov karmaşıklığının pratikte kullanımı sınırlıdır. Bunun en önemli nedeni, yukarıda gördüğümüz gibi, hesaplanamaz olmasıdır. Gerçek K(x) değerini asla bilemeyiz; ancak ZIP, gzip, bzip2 gibi sıkıştırıcılarla üstten yaklaşabiliriz. Bu yaklaşımlar faydalıdır ama her zaman eksiktir — o kısacık, mükemmel sıkıştırıcı programı asla bulamayabiliriz.

İkinci bir incelik: K(x) mutlak bir sayı değildir; makine seçimine göre bir sabite kadar değişir. Pratikte bu sabit küçük olsa da, teorik titizlik açısından “mutlak karmaşıklık” diye bir şeyin olmadığını bilmek önemlidir.

Sonuç: Karmaşıklığın Şiiri

Kolmogorov karmaşıklığı bize şunu söyler: Karmaşıklık, bir nesnenin kendisinde değil, onu tarif etmenin zorluğundadır. Pi sayısının milyarlarca basamağı, birkaç satırlık bir tariften doğar. Rastgele bir dizi ise, kendisinden başka hiçbir şeyle tarif edilemez — kendi kendisinin en kısa açıklamasıdır.

Bu, neredeyse felsefi bir içgörüdür. Evrenin yasaları birkaç denklemle yazılabiliyorsa, evren “basit”tir; yazılamıyorsa, evren kendi kendisinin en kısa açıklamasıdır. Bilim, doğanın kısa programını bulma çabasıdır. Ve Kolmogorov karmaşıklığı, bu çabanın ne kadar başarılı olabileceğini ölçen cetveldir.

Belki de en güzel yanı şudur: Bu cetveli asla tam olarak okuyamayız. Karmaşıklığı ölçme işinin kendisi, ölçülemeyecek kadar karmaşıktır. Matematik, kendi sınırlarını böyle zarif bir şekilde çizer.