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ü.

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.

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) log2n 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 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.

Ancak bu durum en az n0 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."

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 2n adet bit katarı varken sadece 2n-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.

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 FA 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 FA 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.

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).

U+log2(n0)+C olan program tarafından da tanımlanabilir dolayısı ile karmaşıklığı n0dan azdır. Bu da çelişkiye yol açar ve Varsayım (X) olarak söylediklerimizin doğru olmadığını gösterir.

İ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.