Kolmogorov karmaşıklığı

**Kolmogorov karmaşıklığı** (**tanımsal karmaşıklık**, **Kolmogorov-Chaitin karmaşıklığı**, **stokastik karmaşıklık**, **algoritmik entropi** veya **program boyu karmaşıklığı** olarak da bilinir), bilgisayar biliminde, bir metin parçası gibi bir nesneyi tanımlamak için kullanılması gereken bilgi işlemsel kaynakların ölçüsü.

Örneğin aşağıdaki 100 karakter uzunluğundaki iki karakter katarı ele alınırsa:

 0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101

 1100100001100001110111101110110011111010010000100101011110010110001101111111010001100011011001110111

Birinci karakter katarı Türkçe "'01'in 50 tekrarı" ifadesi ile kısaca ve tam olarak tanımlanabilir. İkinci karakter katarının bu şekilde tanımlanması mümkün değildir. Bu karakter katarını tanımlananın en kısa yolu kendisini yazmaktır.

Daha şekilsel olarak söylemek gerekirse, bir karakter katarının karmaşıklığı sabit bir tanımlama dilinde o karakter katarının en kısa ifade edilişidir. Aşağıda tanımlama dilinin seçimi ile karmaşıklık arasındaki hassas ilişki ele alınmıştır. Bir karakter katarının Kolmogorov karmaşıklığının karakter katarının uzunluğundan daha büyük olamayacağı gösterilebilir. Kolmogorov karmaşıklıkları, kendi uzunluklarına kıyasla daha kısa olan karakter katarları karmaşık kabul edilmez.

Kolmogorov karmaşıklığı kavramı şaşırtıcı ölçüde derin bir kavramdır. Bu kavram kullanılarak Gödel'in eksiklik teoremi ve Turing'in durma problemi ile ilgili imkânsızlık sonuçlarını ifade ve ispat için kullanılabilir.

Algoritmik bilgi teorisi, bilgisayar bilimlerinin bir alt alanı olup karakter katarlarının (ve diğer veri yapılarının) Kolmogorov karmaşıklığı ve diğer türden karmaşıklarını incelenmesi ile ilgilidir. Bu çalışma alanı Andrey Kolmogorov, Ray Solomonoff ve Gregory Chaitin tarafından 1960'larda kurulmuştur. Algoritmik bilgi veya Kolmogorov karmaşıklığının pek çok çeşitlemesi vardır. Bunlardan en yaygın olanı kendi kendini ayıran programlara dayanmaktadır ve Leonid Levin (1974) tarafından ortaya konmuştur.

## Tanım
Kolmogorov karmaşıklığını tanımlamak için önce karakter katarları için bir tanımlama dili belirlemeliyiz. Böyle bir tanımlama dili Lisp, Pascal veya Java bytecode gibi programlama dillerinden birine dayanabilir. Eğer **P**, *x* çıktısını üreten bir program ise **P** *x*in tanımıdır. Tanımlamanın uzunluğu **P** programının kaynak kodunun bir karakter katarı olarak uzunluğudur. **P**nin uzunluğu belirlenirken, **P** içinde kullanılan altrutinler de hesaba katılmalıdır. **P** programındaki herhangi bir *n* sabitinin uzunluğu, *n*yi temsil etmek için gerekli bit sayısıdır ki bu da (kabaca) log2*n* kadardır.

Bir başka yöntem de Turing makineleri (TM) için bir kodlama seçmektir. Burada *kodlama*, her **M** Turing makinesini bit dizisi olan  ile ilişkilendiren bir fonksiyondur. Eğer **M**, *w* girdisine karşılık *x* çıktısını üreten bir TM ise bu durumda birleştirilmiş *w* *x*in bir tanımıdır. Kuramsal analiz için bu yaklaşım şekilsel kanıtlar kurmaya daha yatkındır ve araştırmacılar tarafından tercih edilmektedir. Bu makalede ise biz bu kadar şekilsel olmayan bir yaklaşım kullanacağız.

Bir tanımlama dili sabitle. Herhangi bir *s* karakter katarının en az bir tanımı vardır ve o da şu programdır:

  **function** SabitKatarUret()
     **return** *s*

*s*nin tüm tanımları arasında en kısa olanı *d*(*s*) şeklinde gösterilir. Eğer aynı en kısa uzunlukta birden fazla program varsa herhangi birini seç. Bunun için söz gelimi sözlük sırasına göre ilk geleni seç. *d*(*s*), *s*nin *en kısa tanımı*dır. *s*nin **Kolmogorov karmaşıklığı**, *K*(*s*) olarak yazılır ve şu şekilde tanımlanır:
:K(s) = |d(s)|. \quad 
Diğer bir deyişle *K*(*s*) *s*nin en kısa tanımının uzunluğudur.

Şimdi de tanımlama dilinin *K*yı nasıl etkilediğine bakalım kullanılan dili değiştirmenin etkisinin sınırlı olduğunu gösterelim.

**Teorem**. Eğer *K*1 ve *K*2, *L*1 ve *L*2 tanımla dilleri kullanılarak elde edilmiş karmaşıklık fonksiyonları ise, o zaman (sadece *L*1 ve *L*2ye bağlı) öyle bir *c* sabiti vardır ki
:  |K_1(s) - K_2(s)| \leq c, \quad \forall s 
eşitsizliğini sağlar.

Bakışımdan ötürü, tüm *s* bitdizileri için öyle bir *c* sabiti vardır ki,

: K_1(s) \leq K_2(s) + c 

eşitsizliği sağlanır önermesini ispat etmek yeterlidir.

Bunun neden böyle olduğunu anlamak için *L*2 dili için yorumlayıcı olarak çalışan ve *L*1 dilinde yazılmış bir fonksiyon olsun:

   **function** DilYorumla(**string** *p*)

burada *p* *L*2 dilinde yazılmış bir programdır. Yorumlayıcı şu özelliğe sahiptir:

: *p* girdisi üzerinde DilYorumla fonksiyonunu çalıştırmak *p*yi çalıştırmanın sonucunu döndürür.

Dolayısı ile eğer **p**, *L*2 dilinde bir program ve *s*nin en kısa tanımı ise DilYorumla(**P**) *s* karakter katarını döndürür. *s*nin bu tanımının uzunluğu aşağıdakilerin toplamıdır:
# DilYorumla programının uzunluğu
# **P**nin uzunluğu ki bu da tanım itibarıyla *K*2(*s*)dir.

Böylece yukarıda sözü geçen üst sınırın varlığı ispatlanmış olur.

Ayrıca bkz. invaryans teoremi.

## Temel sonuçlar
Aşağıda tek bir tanımlama olduğunu kabul edip, *s*nin karmaşıklığını *K*(*s*) olarak göstereceğiz.

Bir karakter katarının en kısa tanımının katarın kendisinden çok daha uzun olamayacağını görmek zor değildir: *s*yi çıktı olarak veren yukarıdaki SabitKatarUret programı *s*nin kendisinden sabit miktarda daha uzundur.

**Teorem**. Öyle bir *c* sabiti vardır ki 
: K(s) \leq |s| + c, \quad \forall s 
eşitsizliği sağlanır.

İlk şaşırtıcı sonuç *K*nın etkin olarak hesaplanamayacağı gerçeğidir.

**Teorem**. *K* hesaplanabilir bir fonksiyon değildir.

Bir başka deyişle, *s* karakter katarını girdi olarak alıp çıktı olarak *K*(*s*) üretebilecek bir program yazılamaz. Bunu olmayana ergi yöntemi ile gösterelim. Aşağıdaki gibi bir program bulunduğunu var sayalım

   **function** KolmogorovKarmasikligi(**string** *s*)

öyle ki bu program girdi olarak *s* karakter katarını alıp çıktı olarak da *K*(*s*) karmaşıklığını versin. Şimdi de şu programı düşünelim:

   **function** KarmasikKarakterKatariUret(**int** *n*)
      **for** i = 1 to infinity:
         **for** each string s of length exactly i
            **if** KolmogorovKarmasikligi(*s*) >= *n*
               **return** *s*
               **quit**

Bu program KolmogorovKarmasikligi programını bir altrutin olarak çağırır ve en kısa olanından başlayarak en az *n* karmaşıklığına sahip bir karakter katarı bulana dek tüm karakter katarlarını dener, sonra da bulduğu karakter katarını döndürür. Dolayısı ile herhangi bir *n* pozitif tam sayısı verildiğinde Kolmogorov karmaşıklığı en az *n* kadar büyük olan bir karakter katarı üretir. Bu programın kendisinin uzunluğu sabit bir *U* değeridir. KarmasikKarakterKatariUret programınının girdisi *n* tam sayısıdır ve burada *n* sayısının boyu bunu temsil etmek için gerekli bit sayısı ile ölçülür ki bu da log2(*n*)dir. Şimdi de aşağıdaki programı ele alalım:

   **function** ParadoksalKarakterKatariUret ()
       **return** KarmasikKarakterKatariUret(*n*0)

Bu program KarmasikKarakterKatariUret programini altrutin olarak çağırmaktadır ve *n*0 isimli bir serbest parametresi vardır. Program, karmaşıklığı en az *n*0 olan bir *s* karakter katarı üretir. *n*0 için uygun bir değer verilirse bir çelişki elde ederiz. Bu değeri seçmek için *s*nin, uzunluğu en fazla

: U + \log_2(n_0) + C  \quad 

olan ParadoksalKarakterKatariUret programı tarafından üretildiğine dikkat edelim; burada *C*, ParadoksalKarakterKatariUret tarafından eklenmiş sabit bir fazlalıktır. *n*, log2(*n*) değerinden daha hızlı büyüdüğü için aşağıdaki eşitsizliği sağlayan bir *n*0 değeri vardır

: U + \log_2(n_0) + C \leq n_0. \quad 

Ancak bu durum en az *n*0 kadar bir karmaşıklık değeri olduğu tanımı ile çelişir. Dolayısı ile "KolmogorovKarmasikligi" olarak isimlendirilmiş program istenen Kolmogorov karmaşıklığında karakter katarları üretiyor olamaz.

Olmayan ergi ile yapılan bu ispat Berry paradoksuna benzer: "*n* yirmi İngilizce sözcükten daha az sözcük ile tanımlanamayan en küçük tam sayı olsun. Az önce bu sayıyı yirmiden az İngilizce sözcük ile tanımladım."

## Sıkıştırma
Ancak *K*(*s*) değeri için üst sınırları hesaplamak basit bir iştir: uygun bir yöntemle *s* karakter katarını sıkıştır, seçilen dilde sıkıştırma yönteminin tersi olan açma yöntemini yaz, bu açıcı programın kaynak kodunu sıkıştırılmış karakter katarına ekle ve sonuçta elde ettiğin karakter katarının uzunluğunu ölç.

Bir *s* karakter katarı eğer uzunluğu |*s*| - *c* değerini geçmeyecek şekilde tanımlanabiliyorsa o zaman *c* kadar sıkıştırılabilir demektir. Bu da *K*(*s*) ≤ |*s*| - *c* demektir. Aksi takdirde *s* karakter katarı *c* kadar sıkıştırılabilir değildir. En az bir bit kadar bile sıkıştırılamayan karakter katarına kısaca *sıkıştırılamaz* denir. Güvercin deliği ilkesine göre sıkıştırılamaz karakter katarları mevcut olmak zorundadır çünkü *n* uzunluğunda 2*n* adet bit katarı varken sadece 2*n*-1 tane daha kısa katar vardır ki bunların da boyu *n* - 1 kadardır.

Aynı sebepten ötürü "çoğu" karakter katarı karmaşıktır yani çok fazla sıkıştırılamazlar. Yani *K*(*s*), *s* katarının bit cinsinden uzunluğu olan |*s*| değerinden çok daha küçük olamaz. Bunu daha detaylı olarak söylemek için belli bir *n* değeri alalım. Uzunluğu *n* olan *n* farklı bit katarı vardır. Üniform olasılık dağılımına göre bu bit katarı uzayında *n* uzunluğundaki her bit katarının ağırlığı 2-*n* kadardır.

**Teorem**. *n* uzunluğundaki bit katarları uzayındaki üniform olasılık dağılımına göre herhangi bir bit katarının *c* kadar sıkıştırılamama olasılığı en az 1 - 2-*c*+1  + 2-*n* kadardır.

Bu önermeyi ispatlamak için şuna dikkat edelim: *n* - *c* uzunluğunu geçmeyen katar tanımlamalarının sayısı şu geometrik dizi ile belirlenir:

: 1 + 2 + 2^2 + \cdots + 2^{n-c} = 2^{n-c+1}-1.\quad 

Böylece *n* uzunluğunda olup da *c* kadar sıkıştırılamayan en az

: 2^n-2^{n-c+1}+1 \quad 

kadar bit katarı kalır. Olasılığı belirlemek için bunu 2*n* ile bölmek yeterlidir.

Bu teorem comp.compression FAQ  belgesindeki pek çok meydan okuma için temel teşkil eder. Bu teoremin varlığına rağmen zaman zaman bazı kişiler (bunlara çatlak denir) herhangi bir veriyi kayıpsız olarak büyük ölçüde sıkıştırabilen algoritmalar geliştirdiklerini iddia ederler. Bkz. kayıpsız sıkıştırma

## Chaitin'in eksiklik teoremi
Biliyoruz ki çoğu karakter katarı karmaşıktır yani önemli ölçüde "sıkıştırılamaz". Bununla birlikte eğer uzunluğu belli bir eşik değerini geçerse o karakter katarının karmaşık olduğu şekilsel olarak ispatlanamaz. Detaylı olarak söylemek gerekirse doğal sayılar için belli bir *S* aksiyomatik sistemi alın. Bu aksiyomatik sistem yeterince güçlü olmalıdır yani karakter katarlarının karmaşıklığı ile ilgili **A** önermelerine **F****A** formülleri karşılık getirilebilmelidir ve bunlar da **S** içinde olmalıdır. Bu karşılık getirme, ilişkilendirme, şu özelliğe sahip olmalıdır: eğer **F****A** ifadesi **S** içindeki aksiyomlardan yola çıkılmak sureti ile ispatlanabiliyorsa o zaman buna karşılık gelen **A** önermesi doğrudur. Bu şekilleştirme (formalizasyon) Gödel numaralandırması gibi yapay bir kodlama ile yapılabileceği gibi **S** sisteminin kast edilen yorumuna daha uygun olan bir şekilleştirme ile de yapılabilir.

**Teorem**. Öyle bir *L* sabiti vardır ki (sadece belli bir aksiyomatik sisteme ve seçilmiş belli bir tanımlama diline bağlı olan) aşağıdaki

:  K(s) \geq  L \quad 

ifadesinin **S** aksiyomatik sisteminde ispatlanabileceği bir *s* karakter katarı olmasın.

Hemen hemen sıkıştırılamaz olan karakter katarlarının bolluğundan ötürü bu ifadelerin çoğunun doğru olmak zorunda olduğuna dikkat edin.

Bu sonucun ispatı için Berry paradoksundaki kendine gönderme (self-referantial) yapısı kullanılır. Olmayana ergi yöntemi ile teoremdeki iddianın yanlış olduğunu var sayalım, bu durumda:

:**Varsayım (X)**: Herhangi bir *n* tam sayısı için öyle bir *s* katarı vardır ki **S** sisteminde "*K*(*s*) ≥ *n*" ifadesinin ispatı mevcuttur (ifadenin **S** sisteminde şekilsel olarak yazılabildiğini var sayıyoruz).

**S** sistemindeki tüm şekilsel ispatları numaralandırmak için girdi olarak *n* tam sayısını alan ve bir ispatı çıktı olarak üreten aşağıdaki gibi bir prosedür bulabiliriz

   **function** NinciIspat(**int** *n*)

Bu fonksiyon tüm ispatları numaralandırır. Bu ispatların bir kısmı bizim ilgilenmediğimiz formüllerin ispatlarıdır (örneğin Fermat'nın küçük teoremi, Fermat'nın son teoremi gibi ispatlar NinciIspat fonksiyonu tarafından üretilebilir ispatlardır). İspatların küçük bir kısmı ise *K*(*s*) ≥ *n* şeklindeki karmaşıklık formüllerinin ispatlarıdır (burada *s* ve *n* **S** dilindeki sabitlerdir). Öyle bir

   **function** NinciIspatKarmasiklikFormulunuIspatlar(**int** *n*)

programı vardır ki *n*inci ispatın *K*(*s*) ≥ *L* karmaşıklık formülünün ispatı olup olmadığını belirler. *s* karakter katarı ve *L* tam sayısı şu programlar tarafından hesaplanabilir:
    
   **function** KatarNinciIspat(**int** *n*)

   **function** KarmasiklikAltSinirNinciIspat(**int** *n*)

Aşağıdaki programı ele alalım

   **function** KarmasikligiIspatlanabilirKarakterKatariUret(**int** *n*)
      **for** i = 1 to infinity:
         **if**  NinciIspatKarmasiklikFormulunuIspatlar(i) **and** 
             KarmasiklikAltSinirNinciIspat(i) >= *n* 
               **return** KatarNinciIspat(*i*)
               **quit**

Bir *n* tam sayısı verildiğinde bu program **S** siteminde *K*(*s*) ≥ *n* formülünün ispatını ve buna karşılık gelen katarı bulana dek tüm ispatları dener. Program bizim **Varsayım (X)** koşulumuz sağlanınca durur. Şimdi bu programın uzunluğuna *U* diyelim. Öyle bir *n*0 tam sayısı vardır ki *U* + log2(*n*0) + *C* 0, burada *C* aşağıdaki programın getirdiği ek uzunluktur:

    **function** IspatlanabilirParadoksalKarakterKatariUret()
       **return** KarmasikligiIspatlanabilirKarmasikKarakterKatariUret(*n*0)
       **quit**

IspatlanabilirParadoksalKarakterKatariUret programı *K*(*s*) ≥ *n*0 formülünün **S** sisteminde şekilsel olarak ispatlanabildiği *s* karakter katarını üretir. *K*(*s*) ≥ *n*0 ifadesi tek başına doğrudur. Ancak *s* aynı zamanda uzunluğu 
*U*+log2(*n*0)+*C* olan program tarafından da tanımlanabilir dolayısı ile karmaşıklığı *n*0dan azdır. Bu da çelişkiye yol açar ve **Varsayım (X)** olarak söylediklerimizin doğru olmadığını gösterir.

Chaitin sabitinin özelliklerini ispatlamak için de benzer fikirler kullanılır.

İstatistiksel/tümevarımsal çıkarım ve makina öğrenme alanlarındaki en kısa ileti uzunluğu prensibi C.S. Wallace ve D.M. Boulton tarafından 1968 yılında geliştirilmiştir. EKİU Bayesçi (önsel inançları işin içine katar) ve bilgi kuramsaldır. İstatistiksel invaryansın istenen özelliklerine sahiptir (çıkarım yeniden parametikleştirme ile dönüştürülebilir, söz gelimi kutupsal koordinatlardan Kartezyen koordinatlara), istatistiksel tutarlılığı vardır (en zor problemler için bile EKİU herhangi bir modele yakınsar) ve etkindir (EKİU herhangi bir modele en kısa sürede yakınsar). C.S. Wallace  ve D.L. Dowe, EKİU ile algoritmik bilgi teorisi (veya Kolmogorov karmaşıklığı) arasındaki şekilsel ilişkiyi 1999 yılında göstermişlerdir.

## Kaynakça
* Ming Li and Paul Vitányi, *An Introduction to Kolmogorov Complexity and Its Applications*, Springer, 1997. Giriş bölümünün tam metni (İngilizce).
* Yu Manin, *A Course in Mathematical Logic*, Springer-Verlag, 1977.
* Michael Sipser, *Introduction to the Theory of Computation*, PWS Publishing Company, 1997.
* Rónyai Lajos, Ivanyos Gábor, Szabó Réka, *Algoritmusok*. TypoTeX, 1999.

## Dış bağlantılar
* Andrei Nikolaevich Kolmogorov'un Mirası
* Chaitin'in yayınları
* Solomonoff'un IDSIA sayfası 
* Schmidhuber'in algoritmik bilgi genelleştirmeleri 
* Li & Vitanyi'nin ders kitabı 
* Tromp'un lambda calculus bilgisayar modeli K()nın somut bir tanımını sunmaktadır
* David Dowe'in En Kısa İleti Uzunluğu (Minimum Message Length (MML)) ve Occam'ın usturası  sayfaları.
* P. Grunwald, M. A. Pitt and I. J. Myung (ed.), Advances in Minimum Description Length: Theory and Applications, M.I.T. Press, April 2005, ISBN 0-262-07262-9.
* Kolmogorov Karmaşıklığı basit bir açıklama sunar.