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 nesnenin o nesneyi tanımlamak için kullanılması gereken bilgi işlemsel kaynakların bir ölçüsüdür.

Ö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 imkansı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 1960larda 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. Pnin 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) log₂``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 <M> 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ş <M>``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``₁ ve ``K``₂, ``L``₁ ve ``L``₂ tanımla dilleri kullanılarak elde edilmiş karmaşıklık fonksiyonları ise, o zaman (sadece ``L``₁ ve ``L``₂ye 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``₂ dili için yorumlayıcı olarak çalışan ve ``L``₁ dilinde yazılmış bir fonksiyon olsun:

 function DilYorumla(string ``p``)

burada ``p`` ``L``₂ 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``₂ 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
Pnin uzunluğu ki bu da tanım itibarıyle ``K``₂(``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 tamsayı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`` tamsayı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 log₂(``n``)dir. Şimdi de aşağıdaki programı ele alalım:

 function ParadoksalKarakterKatariUret ()

   return KarmasikKarakterKatariUret(``n``₀)

Bu program KarmasikKarakterKatariUret programini altrutin olarak çağırmaktadır ve ``n``₀ isimli bir serbest parametresi vardır. Program, karmaşıklığı en az ``n``₀ olan bir ``s`` karakter katarı üretir. ``n``₀ 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``, log₂(``n``) değerinden daha hızlı büyüdüğü için aşağıdaki eşitsizliği sağlayan bir ``n``₀ değeri vardır

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

Ancak bu durum en az ``n``₀ 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 tamsayı 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 prensibine 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^ = 2^-1.\quad

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

2^n-2^+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`` tamsayı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`` tamsayı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`` tamsayı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`` tamsayı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``₀ tamsayısı vardır ki ``U`` + log₂(``n``₀) + ``C`` < ``n``₀, burada ``C`` aşağıdaki programın getirdiği ek uzunluktur:

 function IspatlanabilirParadoksalKarakterKatariUret()

   return KarmasikligiIspatlanabilirKarmasikKarakterKatariUret(``n``₀)

   quit

IspatlanabilirParadoksalKarakterKatariUret programı ``K``(``s``) ≥ ``n``₀ formülünün S sisteminde şekilsel olarak ispatlanabildiği ``s`` karakter katarını üretir. ``K``(``s``) ≥ ``n``₀ ifadesi tek başına doğrudur. Ancak ``s`` aynı zamanda uzunluğu ``U``+log₂(``n``₀)+``C`` olan program tarafından da tanımlanabilir dolayısı ile karmaşıklığı ``n``₀dan 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.

Linkler

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.

Kolmogorov Karmaşıklığı