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 xin 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, nyi 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 xin 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

snin 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), snin en kısa tanımıdır. snin 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) snin en kısa tanımının uzunluğudur.

Şimdi de tanımlama dilinin Kyı 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 pyi çalıştırmanın sonucunu döndürür.

Dolayısı ile eğer p, L₂ dilinde bir program ve snin en kısa tanımı ise DilYorumla(P) s karakter katarını döndürür. snin bu tanımının uzunluğu aşağıdakilerin toplamıdır:

1. DilYorumla programının uzunluğu
2. Pnin uzunluğu ki bu da tanım itibarıyla 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, snin 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: syi çıktı olarak veren yukarıdaki SabitKatarUret programı snin 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ç Knı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 log₂(n)dir. Şimdi de aşağıdaki programı ele alalım:

  function ParadoksalKarakterKatariUret ()
      return KarmasikKarakterKatariUret(n0)

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 snin, 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 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ⁿ 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 ⁿ 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ⁿ ile bölmek yeterlidir.

Bu teorem comp.compression FAQ 11 Ekim 2006 tarihinde Wayback Machine sitesinde arşivlendi. 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₀ tam sayısı vardır ki U + log₂(n₀) + C < n₀, burada C aşağıdaki programın getirdiği ek uzunluktur:

   function IspatlanabilirParadoksalKarakterKatariUret()
      return KarmasikligiIspatlanabilirKarmasikKarakterKatariUret(n0)
      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 14 Haziran 2006 tarihinde Wayback Machine sitesinde arşivlendi. 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)17 Mayıs 2008 tarihinde Wayback Machine sitesinde arşivlendi..
• 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ı 14 Haziran 2006 tarihinde Wayback Machine sitesinde arşivlendi.
• Schmidhuber'in algoritmik bilgi genelleştirmeleri 18 Mayıs 2006 tarihinde Wayback Machine sitesinde arşivlendi.
• Li & Vitanyi'nin ders kitabı 14 Mayıs 2006 tarihinde Wayback Machine sitesinde arşivlendi.
• Tromp'un lambda calculus bilgisayar modeli K()nın somut bir tanımını sunmaktadır
• David Dowe12 Şubat 2006 tarihinde Wayback Machine sitesinde arşivlendi.'in En Kısa İleti Uzunluğu (Minimum Message Length (MML))9 Şubat 2006 tarihinde Wayback Machine sitesinde arşivlendi. ve Occam'ın usturası 16 Mayıs 2006 tarihinde Wayback Machine sitesinde arşivlendi. sayfaları.
• P. Grunwald, M. A. Pitt and I. J. Myung (ed.), Advances in Minimum Description Length: Theory and Applications19 Haziran 2006 tarihinde Wayback Machine sitesinde arşivlendi., M.I.T. Press, April 2005, ISBN 0-262-07262-9.
• Kolmogorov Karmaşıklığı basit bir açıklama sunar.