Kolmogorov karmaşıklığı

bullvar_katip · 21 Mayıs 2024

Kolmogorov karmaşıklığı (tanımsal karmaşıklık, Kolmogorov-Chaitin karmaşıklığı, stokastik karmaşıklık, algoritmik entropi veya program boyu karmaşıklığı olarak da bilinir), bilgisayar biliminde, bir metin parçası gibi bir nesneyi tanımlamak için kullanılması gereken bilgi işlemsel kaynakların ölçüsü. Örneğin aşağıdaki 100 karakter uzunluğundaki iki karakter katarı ele alınırsa: 0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101 1100100001100001110111101110110011111010010000100101011110010110001101111111010001100011011001110111 Birinci karakter katarı Türkçe "'01'in 50 tekrarı" ifadesi ile kısaca ve tam olarak tanımlanabilir. İkinci karakter katarının bu şekilde tanımlanması mümkün değildir. Bu karakter katarını tanımlananın en kısa yolu kendisini yazmaktır. Daha şekilsel olarak söylemek gerekirse, bir karakter katarının karmaşıklığı sabit bir tanımlama dilinde o karakter katarının en kısa ifade edilişidir. Aşağıda tanımlama dilinin seçimi ile karmaşıklık arasındaki hassas ilişki ele alınmıştır. Bir karakter katarının Kolmogorov karmaşıklığının karakter katarının uzunluğundan daha büyük olamayacağı gösterilebilir. Kolmogorov karmaşıklıkları, kendi uzunluklarına kıyasla daha kısa olan karakter katarları karmaşık kabul edilmez. Kolmogorov karmaşıklığı kavramı şaşırtıcı ölçüde derin bir kavramdır. Bu kavram kullanılarak Gödel'in eksiklik teoremi ve Turing'in durma problemi ile ilgili imkânsızlık sonuçlarını ifade ve ispat için kullanılabilir. Algoritmik bilgi teorisi, bilgisayar bilimlerinin bir alt alanı olup karakter katarlarının (ve diğer veri yapılarının) Kolmogorov karmaşıklığı ve diğer türden karmaşıklarını incelenmesi ile ilgilidir. Bu çalışma alanı Andrey Kolmogorov, Ray Solomonoff ve Gregory Chaitin tarafından 1960'larda kurulmuştur. Algoritmik bilgi veya Kolmogorov karmaşıklığının pek çok çeşitlemesi vardır. Bunlardan en yaygın olanı kendi kendini ayıran programlara dayanmaktadır ve Leonid Levin (1974) tarafından ortaya konmuştur. Tanım Kolmogorov karmaşıklığını tanımlamak için önce karakter katarları için bir tanımlama dili belirlemeliyiz. Böyle bir tanımlama dili Lisp, Pascal veya Java bytecode gibi programlama dillerinden birine dayanabilir. Eğer P, x çıktısını üreten bir program ise P xin tanımıdır. Tanımlamanın uzunluğu P programının kaynak kodunun bir karakter katarı olarak uzunluğudur. Pnin uzunluğu belirlenirken, P içinde kullanılan altrutinler de hesaba katılmalıdır. P programındaki herhangi bir n sabitinin uzunluğu, nyi temsil etmek için gerekli bit sayısıdır ki bu da (kabaca) logn kadardır. Bir başka yöntem de Turing makineleri (TM) için bir kodlama seçmektir. Burada kodlama, her M Turing makinesini bit dizisi olan <M> ile ilişkilendiren bir fonksiyondur. Eğer M, w girdisine karşılık x çıktısını üreten bir TM ise bu durumda birleştirilmiş <M>w xin bir tanımıdır. Kuramsal analiz için bu yaklaşım şekilsel kanıtlar kurmaya daha yatkındır ve araştırmacılar tarafından tercih edilmektedir. Bu makalede ise biz bu kadar şekilsel olmayan bir yaklaşım kullanacağız. Bir tanımlama dili sabitle. Herhangi bir s karakter katarının en az bir tanımı vardır ve o da şu programdır: function SabitKatarUret return s snin tüm tanımları arasında en kısa olanı d(s) şeklinde gösterilir. Eğer aynı en kısa uzunlukta birden fazla program varsa herhangi birini seç. Bunun için söz gelimi sözlük sırasına göre ilk geleni seç. d(s), snin en kısa tanımıdır. snin Kolmogorov karmaşıklığı, K(s) olarak yazılır ve şu şekilde tanımlanır: Diğer bir deyişle K(s) snin en kısa tanımının uzunluğudur. Şimdi de tanımlama dilinin Kyı nasıl etkilediğine bakalım kullanılan dili değiştirmenin etkisinin sınırlı olduğunu gösterelim. Teorem. Eğer K ve K, L ve L tanımla dilleri kullanılarak elde edilmiş karmaşıklık fonksiyonları ise, o zaman (sadece L ve Lye bağlı) öyle bir c sabiti vardır ki eşitsizliğini sağlar. Bakışımdan ötürü, tüm s bitdizileri için öyle bir c sabiti vardır ki, eşitsizliği sağlanır önermesini ispat etmek yeterlidir. Bunun neden böyle olduğunu anlamak için L dili için yorumlayıcı olarak çalışan ve L dilinde yazılmış bir fonksiyon olsun: function DilYorumla(string p) burada p L dilinde yazılmış bir programdır. Yorumlayıcı şu özelliğe sahiptir: p girdisi üzerinde DilYorumla fonksiyonunu çalıştırmak pyi çalıştırmanın sonucunu döndürür. Dolayısı ile eğer p, L dilinde bir program ve snin en kısa tanımı ise DilYorumla(P) s karakter katarını döndürür. snin bu tanımının uzunluğu aşağıdakilerin toplamıdır: DilYorumla programının uzunluğu Pnin uzunluğu ki bu da tanım itibarıyla K(s)dir. Böylece yukarıda sözü geçen üst sınırın varlığı ispatlanmış olur. Ayrıca bkz. invaryans teoremi. Temel sonuçlar Aşağıda tek bir tanımlama olduğunu kabul edip, snin karmaşıklığını K(s) olarak göstereceğiz. Bir karakter katarının en kısa tanımının katarın kendisinden çok daha uzun olamayacağını görmek zor değildir: syi çıktı olarak veren yukarıdaki SabitKatarUret programı snin kendisinden sabit miktarda daha uzundur. Teorem. Öyle bir c sabiti vardır ki eşitsizliği sağlanır. İlk şaşırtıcı sonuç Knın etkin olarak hesaplanamayacağı gerçeğidir. Teorem. K hesaplanabilir bir fonksiyon değildir. Bir başka deyişle, s karakter katarını girdi olarak alıp çıktı olarak K(s) üretebilecek bir program yazılamaz. Bunu olmayana ergi yöntemi ile gösterelim. Aşağıdaki gibi bir program bulunduğunu var sayalım function KolmogorovKarmasikligi(string s) öyle ki bu program girdi olarak s karakter katarını alıp çıktı olarak da K(s) karmaşıklığını versin. Şimdi de şu programı düşü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 çağırır ve en kısa olanından başlayarak en az n karmaşıklığına sahip bir karakter katarı bulana dek tüm karakter katarlarını dener, sonra da bulduğu karakter katarını döndürür. Dolayısı ile herhangi bir n pozitif tam sayısı verildiğinde Kolmogorov karmaşıklığı en az n kadar büyük olan bir karakter katarı üretir. Bu programın kendisinin uzunluğu sabit bir U değeridir. KarmasikKarakterKatariUret programınının girdisi n tam sayısıdır ve burada n sayısının boyu bunu temsil etmek için gerekli bit sayısı ile ölçülür ki bu da log

dir. Şimdi de aşağıdaki programı ele alalım: function ParadoksalKarakterKatariUret return KarmasikKarakterKatariUret

Bu program KarmasikKarakterKatariUret programini altrutin olarak çağırmaktadır ve n isimli bir serbest parametresi vardır. Program, karmaşıklığı en az n olan bir s karakter katarı üretir. n için uygun bir değer verilirse bir çelişki elde ederiz. Bu değeri seçmek için snin, uzunluğu en fazla olan ParadoksalKarakterKatariUret programı tarafından üretildiğine dikkat edelim; burada C, ParadoksalKarakterKatariUret tarafından eklenmiş sabit bir fazlalıktır. n, log

değerinden daha hızlı büyüdüğü için aşağıdaki eşitsizliği sağlayan bir n değeri vardır Ancak bu durum en az n kadar bir karmaşıklık değeri olduğu tanımı ile çelişir. Dolayısı ile "KolmogorovKarmasikligi" olarak isimlendirilmiş program istenen Kolmogorov karmaşıklığında karakter katarları üretiyor olamaz. Olmayan ergi ile yapılan bu ispat Berry paradoksuna benzer: "n yirmi İngilizce sözcükten daha az sözcük ile tanımlanamayan en küçük tam sayı olsun. Az önce bu sayıyı yirmiden az İngilizce sözcük ile tanımladım." Sıkıştırma Ancak K(s) değeri için üst sınırları hesaplamak basit bir iştir: uygun bir yöntemle s karakter katarını sıkıştır, seçilen dilde sıkıştırma yönteminin tersi olan açma yöntemini yaz, bu açıcı programın kaynak kodunu sıkıştırılmış karakter katarına ekle ve sonuçta elde ettiğin karakter katarının uzunluğunu ölç. Bir s karakter katarı eğer uzunluğu |s| - c değerini geçmeyecek şekilde tanımlanabiliyorsa o zaman c kadar sıkıştırılabilir demektir. Bu da K(s) ≤ |s| - c demektir. Aksi takdirde s karakter katarı c kadar sıkıştırılabilir değildir. En az bir bit kadar bile sıkıştırılamayan karakter katarına kısaca sıkıştırılamaz denir. Güvercin deliği ilkesine göre sıkıştırılamaz karakter katarları mevcut olmak zorundadır çünkü n uzunluğunda 2 adet bit katarı varken sadece 2 tane daha kısa katar vardır ki bunların da boyu n - 1 kadardır. Aynı sebepten ötürü "çoğu" karakter katarı karmaşıktır yani çok fazla sıkıştırılamazlar. Yani K(s), s katarının bit cinsinden uzunluğu olan |s| değerinden çok daha küçük olamaz. Bunu daha detaylı olarak söylemek için belli bir n değeri alalım. Uzunluğu n olan farklı bit katarı vardır. Üniform olasılık dağılımına göre bu bit katarı uzayında n uzunluğundaki her bit katarının ağırlığı 2 kadardır. Teorem. n uzunluğundaki bit katarları uzayındaki üniform olasılık dağılımına göre herhangi bir bit katarının c kadar sıkıştırılamama olasılığı en az 1 - 2 + 2 kadardır. Bu önermeyi ispatlamak için şuna dikkat edelim: n - c uzunluğunu geçmeyen katar tanımlamalarının sayısı şu geometrik dizi ile belirlenir: Böylece n uzunluğunda olup da c kadar sıkıştırılamayan en az kadar bit katarı kalır. Olasılığı belirlemek için bunu 2 ile bölmek yeterlidir. Bu teorem comp.compression FAQ belgesindeki pek çok meydan okuma için temel teşkil eder. Bu teoremin varlığına rağmen zaman zaman bazı kişiler (bunlara çatlak denir) herhangi bir veriyi kayıpsız olarak büyük ölçüde sıkıştırabilen algoritmalar geliştirdiklerini iddia ederler. Bkz. kayıpsız sıkıştırma Chaitin'in eksiklik teoremi Biliyoruz ki çoğu karakter katarı karmaşıktır yani önemli ölçüde "sıkıştırılamaz". Bununla birlikte eğer uzunluğu belli bir eşik değerini geçerse o karakter katarının karmaşık olduğu şekilsel olarak ispatlanamaz. Detaylı olarak söylemek gerekirse doğal sayılar için belli bir S aksiyomatik sistemi alın. Bu aksiyomatik sistem yeterince güçlü olmalıdır yani karakter katarlarının karmaşıklığı ile ilgili A önermelerine F formülleri karşılık getirilebilmelidir ve bunlar da S içinde olmalıdır. Bu karşılık getirme, ilişkilendirme, şu özelliğe sahip olmalıdır: eğer F ifadesi S içindeki aksiyomlardan yola çıkılmak sureti ile ispatlanabiliyorsa o zaman buna karşılık gelen A önermesi doğrudur. Bu şekilleştirme (formalizasyon) Gödel numaralandırması gibi yapay bir kodlama ile yapılabileceği gibi S sisteminin kast edilen yorumuna daha uygun olan bir şekilleştirme ile de yapılabilir. Teorem. Öyle bir L sabiti vardır ki (sadece belli bir aksiyomatik sisteme ve seçilmiş belli bir tanımlama diline bağlı olan) aşağıdaki ifadesinin S aksiyomatik sisteminde ispatlanabileceği bir s karakter katarı olmasın. Hemen hemen sıkıştırılamaz olan karakter katarlarının bolluğundan ötürü bu ifadelerin çoğunun doğru olmak zorunda olduğuna dikkat edin. Bu sonucun ispatı için Berry paradoksundaki kendine gönderme (self-referantial) yapısı kullanılır. Olmayana ergi yöntemi ile teoremdeki iddianın yanlış olduğunu var sayalım, bu durumda: Varsayım (X): Herhangi bir n tam sayısı için öyle bir s katarı vardır ki S sisteminde "K(s) ≥ n" ifadesinin ispatı mevcuttur (ifadenin S sisteminde şekilsel olarak yazılabildiğini var sayıyoruz). S sistemindeki tüm şekilsel ispatları numaralandırmak için girdi olarak n tam sayısını alan ve bir ispatı çıktı olarak üreten aşağıdaki gibi bir prosedür bulabiliriz function NinciIspat(int n) Bu fonksiyon tüm ispatları numaralandırır. Bu ispatların bir kısmı bizim ilgilenmediğimiz formüllerin ispatlarıdır (örneğin Fermat'nın küçük teoremi, Fermat'nın son teoremi gibi ispatlar NinciIspat fonksiyonu tarafından üretilebilir ispatlardır). İspatların küçük bir kısmı ise K(s) ≥ n şeklindeki karmaşıklık formüllerinin ispatlarıdır (burada s ve n S dilindeki sabitlerdir). Öyle bir function NinciIspatKarmasiklikFormulunuIspatlar(int n) programı vardır ki n ispatın K(s) ≥ L karmaşıklık formülünün ispatı olup olmadığını belirler. s karakter katarı ve L tam sayısı şu programlar tarafından hesaplanabilir: function KatarNinciIspat(int n) function KarmasiklikAltSinirNinciIspat(int n) Aşağı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ı verildiğinde bu program S siteminde K(s) ≥ n formülünün ispatını ve buna karşılık gelen katarı bulana dek tüm ispatları dener. Program bizim Varsayım (X) koşulumuz sağlanınca durur. Şimdi bu programın uzunluğuna U diyelim. Öyle bir n tam sayısı vardır ki U + log

+ C < n, burada C aşağıdaki programın getirdiği ek uzunluktur: function IspatlanabilirParadoksalKarakterKatariUret return KarmasikligiIspatlanabilirKarmasikKarakterKatariUret

quit IspatlanabilirParadoksalKarakterKatariUret programı K(s) ≥ n formülünün S sisteminde şekilsel olarak ispatlanabildiği s karakter katarını üretir. K(s) ≥ n ifadesi tek başına doğrudur. Ancak s aynı zamanda uzunluğu U+log

+C olan program tarafından da tanımlanabilir dolayısı ile karmaşıklığı ndan azdır. Bu da çelişkiye yol açar ve Varsayım (X) olarak söylediklerimizin doğru olmadığını gösterir. Chaitin sabitinin özelliklerini ispatlamak için de benzer fikirler kullanılır. İstatistiksel/tümevarımsal çıkarım ve makina öğrenme alanlarındaki en kısa ileti uzunluğu prensibi C.S. Wallace ve D.M. Boulton tarafından 1968 yılında geliştirilmiştir. EKİU Bayesçi (önsel inançları işin içine katar) ve bilgi kuramsaldır. İstatistiksel invaryansın istenen özelliklerine sahiptir (çıkarım yeniden parametikleştirme ile dönüştürülebilir, söz gelimi kutupsal koordinatlardan Kartezyen koordinatlara), istatistiksel tutarlılığı vardır (en zor problemler için bile EKİU herhangi bir modele yakınsar) ve etkindir (EKİU herhangi bir modele en kısa sürede yakınsar). C.S. Wallace ve D.L. Dowe, EKİU ile algoritmik bilgi teorisi (veya Kolmogorov karmaşıklığı) arasındaki şekilsel ilişkiyi 1999 yılında göstermişlerdir. Kaynakça Ming Li and Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, Springer, 1997. Giriş bölümünün tam metni (İngilizce). Yu Manin, A Course in Mathematical Logic, Springer-Verlag, 1977. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997. Rónyai Lajos, Ivanyos Gábor, Szabó Réka, Algoritmusok. TypoTeX, 1999. Dış bağlantılar Andrei Nikolaevich Kolmogorov'un Mirası Chaitin'in yayınları Solomonoff'un IDSIA sayfası Schmidhuber'in algoritmik bilgi genelleştirmeleri Li & Vitanyi'nin ders kitabı Tromp'un lambda calculus bilgisayar modeli Knın somut bir tanımını sunmaktadır David Dowe'in En Kısa İleti Uzunluğ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 Karmaşıklığı basit bir açıklama sunar. Kategori:Bilişim

Ara

Ara

Foruma hoş geldin 👋, Ziyaretçi

Kolmogorov karmaşıklığı

bullvar_katip

Administrator

Benzer konular

Tema özelleştirme sistemi

Tam ekran yada dar ekran

Izgara yada normal mod

Forum arkaplan resimleri

Sidebar blogunu kapat/aç

Yapışkan sidebar kapat/aç

Radius aç/kapat

Foruma hoş geldin 👋, Ziyaretçi