Kolmogorov karmaşıklığı - Kolmogorov complexity

Bu görüntü Mandelbrot fraktal kümesinin bir bölümünü göstermektedir . Bu görüntüdeki her pikselin 24 bit rengini basitçe saklamak 23 milyon bayt gerektirir, ancak küçük bir bilgisayar programı Mandelbrot kümesinin tanımını ve görüntünün köşelerinin koordinatlarını kullanarak bu 23 MB'yi yeniden üretebilir. Bu nedenle, bu bit eşlemi kodlayan ham dosyanın Kolmogorov karmaşıklığı, herhangi bir pragmatik hesaplama modelinde 23 MB'den çok daha azdır . PNG'nin genel amaçlı görüntü sıkıştırması, onu yalnızca 1,6 MB'a düşürür; bu, ham verilerden daha küçük, ancak Kolmogorov karmaşıklığından çok daha büyüktür.

Gelen algoritmik bilgi teorisi (bir alt alan bilgisayar bilimi ve matematik ) Kolmogorov karmaşıklığı bir nesnenin, örneğin bir metin parçası gibi bir kısa uzunluğu bilgisayar programı (önceden tespit edilmiş bir de programlama dili çıkış olarak nesne üretir). Nesneyi belirtmek için gereken hesaplama kaynaklarının bir ölçüsüdür ve algoritmik karmaşıklık , Solomonoff-Kolmogorov-Chaitin karmaşıklığı , program boyutu karmaşıklığı , tanımlayıcı karmaşıklık veya algoritmik entropi olarak da bilinir . Adını bu konuda ilk kez 1963 yılında yayınlayan Andrey Kolmogorov'dan almıştır .

Kolmogorov karmaşıklığı kavramı, Cantor'un köşegen argümanına , Gödel'in eksiklik teoremine ve Turing'in durma problemine benzer imkansızlık sonuçlarını ifade etmek ve kanıtlamak için kullanılabilir . Özellikle, her metnin Kolmogorov karmaşıklığı için bir alt sınır hesaplayan hiçbir program P , esasen P'nin kendi uzunluğundan daha büyük bir değer döndüremez (bkz. bölüm § Chaitin'in eksiklik teoremi ); bu nedenle tek bir program sonsuz sayıda metin için tam Kolmogorov karmaşıklığını hesaplayamaz.

Tanım

32 küçük harf ve rakamdan oluşan aşağıdaki iki dizeyi göz önünde bulundurun :

abababababababababababababababab , ve

4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

İlk dize, 17 karakterden write ab 16 timesoluşan kısa bir İngilizce açıklamasına sahiptir, yani " " . İkincisinin (aynı karakter kümesini kullanarak) dizenin kendisini yazmaktan başka, yani 38 karakterden oluşan " " basit bir açıklaması yoktur . Bu nedenle, ilk dizgiyi yazma işleminin ikincisini yazmaktan "daha az karmaşık" olduğu söylenebilir. write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

Daha resmi olarak, bir dizgenin karmaşıklığı , bazı sabit evrensel tanımlama dillerinde dizgenin mümkün olan en kısa açıklamasının uzunluğudur (karmaşıklığın duyarlılığı, açıklama dili seçimine göre aşağıda tartışılmaktadır). Herhangi bir dizenin Kolmogorov karmaşıklığının, dizenin uzunluğundan birkaç bayttan daha büyük olamayacağı gösterilebilir. Kolmogorov karmaşıklığı dizenin boyutuna göre küçük olan yukarıdaki abab örneği gibi dizeler karmaşık olarak kabul edilmez.

Kolmogorov karmaşıklığı herhangi bir matematiksel nesne için tanımlanabilir, ancak basitlik için bu makalenin kapsamı dizelerle sınırlıdır. Öncelikle stringler için bir tanımlama dili belirlememiz gerekiyor. Böyle bir tanımlama dili, Lisp , Pascal veya Java gibi herhangi bir bilgisayar programlama diline dayalı olabilir . Eğer P bir dizge veren bir program x , o zaman P bir açıklamasıdır x . Açıklamanın uzunluğu, bir karakter dizisi olarak sadece P'nin bir karakterdeki bit sayısı ile çarpımı uzunluğudur (örneğin, ASCII için 7 ).

Alternatif olarak, Turing makineleri için bir kodlama seçebiliriz , burada kodlama her Turing Makinesi M'yi bir bit dizisi < M > ile ilişkilendiren bir fonksiyondur . Eğer M Turing makinesi olan, girdi üzerinde ağırlık , çıkışlar dize x , daha sonra birleştirilmiş bir dizeye < M > W bir açıklamasıdır x . Teorik analiz için, bu yaklaşım, ayrıntılı biçimsel ispatlar oluşturmaya daha uygundur ve genellikle araştırma literatüründe tercih edilir. Bu makalede, gayri resmi bir yaklaşım tartışılmaktadır.

Herhangi bir dize s'nin en az bir açıklaması vardır. Örneğin, yukarıdaki ikinci dize program tarafından verilir:

function GenerateString2()
    return "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

ilk dize (çok daha kısa) sözde kodla çıktılanırken:

function GenerateString1()
    return "ab" × 16

Bir tanımı ise D ( s , bir String) in en az bir uzunlukta (yani, en az bit kullanılarak), bir adlandırılan en az açıklama ve s ve uzunluğu d ( s minimum bit yani sayı () tanım), s'nin Kolmogorov karmaşıklığıdır , K ( s ) ile yazılır . Sembolik,

K ( ler ) = | d ( s )|.

En kısa açıklamanın uzunluğu, açıklama dilinin seçimine bağlı olacaktır; ancak değişen dillerin etkisi sınırlıdır ( değişmezlik teoremi adı verilen bir sonuç ).

değişmezlik teoremi

gayri resmi muamele

Aşağıdaki anlamda optimal olan bazı tanımlama dilleri vardır: bir nesnenin bir tanımlama dilindeki herhangi bir açıklaması verildiğinde, bahsedilen tanımlama sabit bir ek yük ile optimal tanımlama dilinde kullanılabilir. Sabit, yalnızca ilgili dillere bağlıdır, nesnenin açıklamasına veya açıklanan nesneye değil.

İşte optimal bir tanımlama dili örneği. Bir açıklama iki bölümden oluşacaktır:

• İlk bölüm başka bir tanımlama dilini tanımlar.
• İkinci kısım, nesnenin o dilde bir açıklamasıdır.

Daha teknik terimlerle, bir açıklamanın ilk kısmı bir bilgisayar programıdır (özellikle: nesnenin dili için bir derleyici, açıklama dilinde yazılmıştır), ikinci kısım ise nesneyi çıktı olarak üreten o bilgisayar programının girdisidir.

Değişmezlik teoremi şu şekildedir: Herhangi bir tanımlama dili L verildiğinde , optimal tanımlama dili en az L kadar verimlidir ve bir miktar sabit ek yük vardır.

Kanıt: L' deki herhangi bir D tanımı, önce L'yi bir bilgisayar programı P olarak tanımlayarak (kısım 1) ve ardından orijinal tanım D' yi bu programa girdi olarak kullanarak (kısım 2) en uygun dilde bir açıklamaya dönüştürülebilir . Bu yeni tanımlamanın toplam uzunluğu D' (yaklaşık olarak):

| D' | = | P | + | D |

P'nin uzunluğu D'ye bağlı olmayan bir sabittir . Bu nedenle, açıklanan nesneden bağımsız olarak en fazla sabit bir ek yük vardır. Bu nedenle, optimal dil bu katkı sabitine kadar evrenseldir .

Daha resmi bir tedavi

Teorem : Eğer K ₁ ve K ₂ Turing tam tanımlama dilleri L ₁ ve L _2'ye göre karmaşıklık fonksiyonları ise, o zaman bir c sabiti vardır  - bu sadece seçilen L ₁ ve L ₂ dillerine bağlıdır - öyle ki

∀ s . − c ≤ K ₁ ( s ) − K ₂ ( s ) ≤ c .

Kanıt : Simetri ile, tüm s dizileri için bir c sabiti olduğunu kanıtlamak yeterlidir.

K ₁ ( s ) ≤ K ₂ ( s ) + c .

Şimdi, L ₁ dilinde , L ₂ için yorumlayıcı görevi gören bir program olduğunu varsayalım :

function InterpretLanguage(string p)

burada p , L _2'deki bir programdır . Tercüman aşağıdaki özellik ile karakterize edilir:

Koşu InterpretLanguagegirişi p çalışan sonucunu döndürür s .

Bu nedenle, P , s öğesinin minimal bir açıklaması olan L _2'deki bir programsa , ( P ) s dizesini döndürür . s'nin bu açıklamasının uzunluğu , aşağıdakilerin toplamıdır: InterpretLanguage

1. CInterpretLanguage sabiti olarak alabileceğimiz programın uzunluğu .
2. Tanımı gereği K ₂ ( s ) olan P'nin uzunluğu .

Bu, istenen üst sınırı kanıtlar.

Tarih ve bağlam

Algoritmik bilgi teorisi , Kolmogorov karmaşıklığını ve dizeler (veya diğer veri yapıları ) üzerindeki diğer karmaşıklık ölçümlerini inceleyen bilgisayar bilimi alanıdır .

Kolmogorov Karmaşıklığı kavramı ve teorisi, ilk olarak 1960 yılında yayınlayan Ray Solomonoff tarafından keşfedilen ve algoritmik olasılık icadının bir parçası olarak "Genel Bir Endüktif Çıkarım Teorisi Üzerine Bir Ön Rapor" da açıklayan çok önemli bir teoreme dayanmaktadır . 1964 yayınlarında, "Endüktif Çıkarımın Resmi Bir Teorisi", Bölüm 1 ve Bölüm 2, Bilgi ve Kontrol'de daha eksiksiz bir açıklama yaptı .

Andrey Kolmogorov daha sonra bu teoremi bağımsız olarak Problems Inform'da yayınladı . 1965'te iletim . Gregory Chaitin bu teoremi J. ACM'de de sunar  – Chaitin'in makalesi Ekim 1966'da sunuldu ve Aralık 1968'de revize edildi ve hem Solomonoff'un hem de Kolmogorov'un makalelerinden alıntı yaptı.

Teorem, dizeleri açıklamalarından (kodlarından) çözen algoritmalar arasında en uygun olanı olduğunu söylüyor. Bu algoritma, tüm diziler için, diğer algoritmaların izin verdiği kadar kısa kodlara, algoritmalara bağlı olan ancak dizilerin kendilerine bağlı olmayan bir toplama sabitine kadar izin verir. Solomonoff, bu algoritmayı ve dizinin sonraki basamaklarının tümevarımsal çıkarımının temel alınabileceği bir dizinin "evrensel olasılığını" tanımlamaya izin verdiği kod uzunluklarını kullandı. Kolmogorov bu teoremi, karmaşıklık, rastgelelik ve bilgi dahil olmak üzere dizilerin çeşitli işlevlerini tanımlamak için kullandı.

Kolmogorov, Solomonoff'un çalışmalarından haberdar olduğunda, Solomonoff'un önceliğini kabul etti. Birkaç yıl boyunca, Solomonoff'un çalışmaları Sovyetler Birliği'nde Batı Dünyasından daha iyi biliniyordu. Bununla birlikte, bilim camiasındaki genel fikir birliği, bu tür karmaşıklığı bir dizinin rastgeleliği ile ilgilenen Kolmogorov ile ilişkilendirmek iken, Algoritmik Olasılık, evrensel önsel olasılık dağılımını icat ederek tahmine odaklanan Solomonoff ile ilişkilendirildi. . Tanımlayıcı karmaşıklığı ve olasılığı kapsayan daha geniş alana genellikle Kolmogorov karmaşıklığı denir. Bilgisayar bilimcisi Ming Li, bunu Matta etkisinin bir örneği olarak değerlendirir : "... sahip olan herkese, daha fazlası verilecektir..."

Kolmogorov karmaşıklığının veya algoritmik bilginin birkaç başka çeşidi vardır. En yaygın olarak kullanılanı, kendi kendini sınırlayan programlara dayanmaktadır ve esas olarak Leonid Levin'e (1974) dayanmaktadır .

Blum aksiyomlarına dayanan Kolmogorov karmaşıklığına aksiyomatik bir yaklaşım (Blum 1967), Mark Burgin tarafından Andrey Kolmogorov tarafından yayınlanmak üzere sunulan makalede tanıtıldı.

Temel sonuçlar

Aşağıdaki tartışmada, K ( s ) s dizgisinin karmaşıklığı olsun .

Programı - Bir dize en kısa tanımının katarın kendisinden daha çok daha büyük olamayacağını görmek zor değildir GenerateString2çıkışlar yukarıda ler daha sabit bir miktar daha büyüktür s .

Teorem : Öyle bir c sabiti vardır ki

∀ s . K ( s ) ≤ | s | + c .

Kolmogorov karmaşıklığının hesaplanamazlığı

K'yi hesaplamak için bir programda naif bir girişim

İlk bakışta , aşağıdaki gibi herhangi bir s için K ( s ) değerini hesaplayabilen bir program yazmak önemsiz görünebilir :

function KolmogorovComplexity(string s)
    for i = 1 to infinity:
        for each string p of length exactly i
            if isValidProgram(p) and evaluate(p) == s
                return i

Bu program, en kısadan başlayarak tüm olası programları yineler (tüm olası dizeleri yineleyerek ve yalnızca geçerli programları dikkate alarak). Her program, o program tarafından üretilen sonucu bulmak için yürütülür ve s girdisiyle karşılaştırılır . Sonuç, programın uzunluğuyla eşleşirse döndürülür.

Ancak, p test edilen programlardan bazıları , örneğin sonsuz döngüler içeriyorsa, sonlandırılmayacağı için bu çalışmayacaktır . Durma probleminin hesaplanamazlığı nedeniyle, tüm bu programları çalıştırmadan önce bir şekilde test ederek tüm bu programlardan kaçınmanın bir yolu yoktur .

Dahası, hiç bir program, bu kadar karmaşık olsa da, K fonksiyonunu hesaplayamaz . Bu, aşağıda kanıtlanmıştır.

Ait uncomputability biçimsel kanıtı K

Teorem : Keyfi olarak büyük Kolmogorov karmaşıklığı dizileri vardır. Biçimsel olarak: her n ∈ ℕ için K ( s ) ≥ n olan bir s dizisi vardır .

Kanıt: Aksi takdirde, sonsuz sayıda olası sonlu dizilerin tümü, karmaşıklığı n bitin altında olan sonlu sayıda program tarafından üretilebilir .

Teorem : K hesaplanabilir bir fonksiyon değil . Başka bir deyişle, girdi olarak herhangi bir s dizesini alan ve çıktı olarak K ( s ) tamsayısını üreten bir program yoktur .

Aşağıdaki dolaylı kanıt , programları belirtmek için basit bir Pascal benzeri dil kullanır ; Kanıt basitliği için açıklamasının (yani bir yorumlayıcının ) uzunluğuna sahip olduğunu varsayın .1 400 000 bit. Çelişki için bir program olduğunu varsayalım

function KolmogorovComplexity(string s)

girdi olarak bir s dizesi alır ve K ( s ) değerini döndürür . Tüm programlar sonlu uzunluktadır, bu nedenle, basitliği kanıtlamak için, şunu varsayın:7 000 000 000 bit. Şimdi, aşağıdaki uzunluk programını düşünün1288 bit:

function GenerateComplexString()
    for i = 1 to infinity:
        for each string s of length exactly i
            if KolmogorovComplexity(s) ≥ 8000000000
                return s

KolmogorovComplexityBir alt program olarak kullanarak , program en kısadan başlayarak, en az Kolmogorov karmaşıklığına sahip bir dize döndürene kadar her dizeyi dener.8 000 000 000 bit, yani daha kısa herhangi bir program tarafından üretilemeyen bir dize8 000 000 000 bit. Ancak, s üreten yukarıdaki programın toplam uzunluğu yalnızca7 001 401 288 bit, bu bir çelişkidir. (Eğer kodu KolmogorovComplexitydaha kısaysa çelişki kalır. Daha uzunsa, kullanılan sabit GenerateComplexStringher zaman uygun şekilde değiştirilebilir.)

Yukarıdaki izolasyon benzer bir çelişki kullanan Berry paradoksu : " _{1 2} küçük ₃ pozitif ₄ tamsayıdır ₅ olduğu ₆ olamaz ₇ olmak ₈ tanımlandığı ₉ içinde ₁₀ az ₁₁ den ₁₂ yirmi ₁₃ İngilizce ₁₄ kelime". Olmayan bir hesaplanabilirliği göstermek de mümkündür K durdurulması problem hesaplanamama indirgeme ile , H , çünkü K ve H olan Turing eşdeğer .

Programlama dili topluluğunda mizahi bir şekilde " tam istihdam teoremi " olarak adlandırılan ve mükemmel bir boyut optimize edici derleyici olmadığını belirten bir doğal sonuç vardır.

Kolmogorov karmaşıklığı için zincir kuralı

Kolmogorov karmaşıklığı için zincir kuralı şunu belirtir:

K ( X , Y ) ≤ K ( X ) + K ( Y | X ) + O (log( K ( X , Y ))).

Bu üretir kısa programı bildiren X ve Y ise daha fazla yeniden üretmek için bir program daha büyük bir logaritmik terimi daha X ve yeniden üretmek için bir program , Y verilen X . Bu ifadeyi kullanarak, Kolmogorov karmaşıklığı için bir karşılıklı bilgi analogu tanımlanabilir .

Sıkıştırma

Bu üst sınır hesaplamak için basittir K ( s , sadece -) sıkıştırmak dizge s , seçilen dilde karşılık gelen açıcı uygulanması, uygun bir yöntemle sıkıştırılır dizeye açıcı birleştirmek, ve elde edilen dize uzunluğunu ölçmek - somut verilen dilde kendi kendine açılan bir arşivin boyutu .

Bir dize s bir numara tarafından sıkıştırılabilir olan c kimin uzunluğu aşmayan bir açıklama varsa | s | - c bit. Bu, K ( s ) ≤ | s | - c . Aksi takdirde, s c ile sıkıştırılamaz . 1 ile bir dize sıkıştırılamaz basitçe olduğu söylenir sıkıştırılamaz  - tarafından hasıraltı prensibi her sıkıştırılmış dize tek sıkıştırılmamış dize eşleştiren çünkü geçerlidir, sıkıştırılamaz dizeleri var olmalıdır 2 olmadığından, ⁿ uzunluğunun bit dizeleri n , ancak sadece 2 ⁿ − 1 daha kısa dize, yani uzunluğu n'den az olan dizeler (yani 0, 1, ..., n − 1 uzunluğunda ).

Aynı nedenle, çoğu dizi, önemli ölçüde sıkıştırılamayacakları anlamında karmaşıktır – K ( s leri ) | 'den çok daha küçük değildir. s |, s'nin bit cinsinden uzunluğu . Bunu kesinleştirmek için n değerini sabitleyin . 2 Var ⁿ uzunluğunun farklı bit katarı n . Homojen olasılık tam olarak eşit ağırlık 2, bu bit katarı atar uzayında dağılımı ^{- N} uzunluğu her bir dize n .

Teorem : n uzunluğundaki bit dizilerinin uzayı üzerindeki tek tip olasılık dağılımı ile, bir dizginin c ile sıkıştırılamaz olma olasılığı en az 1 - 2 ^{- c +1} + 2 ^{- n'dir} .

Teoremi kanıtlamak için, n - c'yi geçmeyen uzunluk tanımlarının sayısının geometrik seri tarafından verildiğine dikkat edin:

1 + 2 + 2 ² + … + 2 ^{n − c} = 2 ^{n − c +1} − 1.

en azından kalır

2 ⁿ - 2 ^{n - c +1} + 1

c ile sıkıştırılamayan n uzunluğunda bit dizileri . Olasılığı belirlemek için 2 ^n'ye bölün .

Chaitin'in eksiklik teoremi

Kolmogorov karmaşıklığı K ( ler ) , ve iki hesaplanabilir alt sınır fonksiyonları prog1(s), prog2(s). Yatay eksen ( logaritmik ölçek ) , uzunluğa göre sıralanmış tüm s dizilerini sıralar; dikey eksen ( doğrusal ölçek ) Kolmogorov karmaşıklığını bit olarak ölçer . Çoğu dizi sıkıştırılamaz, yani Kolmogorov karmaşıklığı uzunluklarını sabit bir miktarda aşıyor. Resimde neredeyse dikey eğimler olarak görünen 9 sıkıştırılabilir dize gösterilmiştir. Nedeniyle Chaitin eksiklik teoremi (1974), giriş dizesi bağımsız bir sabit limitli, geçemez Kolmogorov karmaşıklık bir alt sınır işlem herhangi bir programın çıkışı, s .

Yukarıdaki teoreme göre ( § Sıkıştırma ), çoğu dizi, önemli ölçüde "sıkıştırılmış" bir şekilde tanımlanamayacakları anlamında karmaşıktır. Ancak, belirli bir dizgenin karmaşık olduğu gerçeği, dizgenin karmaşıklığı belirli bir eşiğin üzerindeyse, resmi olarak kanıtlanamayacağı ortaya çıkıyor. Kesin resmileştirme aşağıdaki gibidir. İlk olarak, doğal sayılar için belirli bir aksiyomatik sistem S'yi düzeltin . Aksiyomlaştırılması belirli iddialar etmek, böylece yeterince güçlü olmak zorunda A şeritlerinin karmaşıklığı ile ilgili, bir formül ilişkilendirebilir F _bir bölgesindeki S . Bu ilişkilendirme aşağıdaki özelliklere sahip olmalıdır:

Eğer E _bir aksiyomlarından kanıtlanabilir olan S , daha sonra karşılık gelen onaylama bir doğru olmalıdır. Bu "biçimselleştirme", bir Gödel numaralandırmasına dayalı olarak gerçekleştirilebilir .

Teorem : Bir L sabiti vardır (ki bu sadece S'ye ve tanımlama dilinin seçimine bağlıdır ), öyle ki , deyimi için bir s dizisi yoktur.

K ( s ) ≥ L       ( S'de resmileştirildiği gibi )

S içinde kanıtlanabilir .

Kanıt Fikir : Bu sonucun kanıtı, Berry'nin paradoksunda kullanılan kendine referans veren bir yapı üzerinde modellenmiştir . İlk olarak S içindeki ispatları sıralayan bir program elde ediyoruz ve girdi olarak bir L tamsayısını alan ve K ( x ) ≥ L ifadesinin S içindeki ispatlar içindeki x dizgilerini yazdıran bir P prosedürü belirliyoruz . Sonra ayarlayarak L bu prosedür uzunluğundan daha büyük için P'nin , bir programın gerekli uzunluğu yazdırmak için buna sahip x belirtilen K ( x ) ≥ L en azından olarak L miktarı daha küçük olacaktır L dize beri x , P prosedürü ile basılmıştır . Bu bir çelişkidir. Bu izolasyon sistemi için mümkün değildir Bu nedenle S kanıtlamak için K ( X ) ≥ L için L için, özellikle, isteğe bağlı olarak büyük bir L prosedürü uzunluğundan daha büyük P (sonlu).

Kanıt :

Biz tüm resmi delillerinden etkili numaralandırma bulabilirsiniz S bazı prosedür ile

function NthProof(int n)

hangi girdi n olarak alır ve bir miktar kanıt verir. Bu fonksiyon tüm kanıtları numaralandırır. S dilindeki her olası ispat bazı n için üretildiğinden, bunlardan bazıları burada önemsemediğimiz formüllerin ispatlarıdır . Bunlardan bazıları bir şekilde karmaşıklığı formülleri K ( ler ) ≥  n burada s ve n, dilinde sabitlerdir S . bir prosedür var

function NthProofProvesComplexityFormula(int n)

ki belirler N inci geçirmez aslında bir karmaşıklık, formül kanıtlar K ( ler ) ≥  L . s dizgileri ve L tamsayıları sırasıyla prosedürle hesaplanabilir:

function StringNthProof(int n)

function ComplexityLowerBoundNthProof(int n)

Aşağıdaki prosedürü göz önünde bulundurun:

function GenerateProvablyComplexString(int n)
    for i = 1 to infinity:
        if NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) ≥ n
            return StringNthProof(i)

Bir n verildiğinde , bu prosedür , bazı L  ≥  n için K ( s ) ≥  L formülünün resmi sistemi S'de bir dizi ve bir ispat bulana kadar her ispatı dener ; eğer böyle bir kanıt yoksa sonsuza kadar döngüye girer.

Son olarak, tüm bu prosedür tanımlarından oluşan programı ve bir ana çağrıyı düşünün:

GenerateProvablyComplexString(n0)

burada n ₀ sabiti daha sonra belirlenecektir. Genel program uzunluğu U +log ₂ ( n ₀ ) olarak ifade edilebilir , burada U bir sabittir ve log ₂ ( n ₀ ) , ikili rakamlarla kodlandığı makul varsayımı altında n ₀ tamsayı değerinin uzunluğunu temsil eder. . n _0'ı program uzunluğundan daha büyük olarak seçeceğiz , yani n ₀ > U +log ₂ ( n ₀ ). Bu, yeterince büyük n ₀ için açıkça doğrudur , çünkü sol taraf n _0'da doğrusal olarak büyürken , sağ taraf n _0'da logaritmik olarak sabit U sabitine kadar büyür .

O zaman , dolaylı bir argümanla görülebileceği gibi, S'de L ≥ n ₀ olan " K ( s )≥ L " formunun hiçbir kanıtı elde edilemez : Eğer ≥ n ₀ değeri döndürülebilirse , o zaman içerideki döngü sonunda sona erer ve bu prosedür bir dize döneceğini s şekilde ComplexityLowerBoundNthProof(i)GenerateProvablyComplexString

Bu bir çelişkidir, QED

Sonuç olarak, seçilen n ₀ değerine sahip yukarıdaki program sonsuza kadar döngü yapmalıdır.

Benzer fikirler, Chaitin sabitinin özelliklerini kanıtlamak için kullanılır .

Minimum mesaj uzunluğu

Minimum mesaj uzunluğu ilkesi, istatistiksel ve tümevarımsal çıkarım ve makine öğrenimi, 1968'de CS Wallace ve DM Boulton tarafından geliştirilmiştir . MML, Bayesçidir (yani, önceki inançları içerir) ve bilgi-teoriktir. İstatistiksel değişmezlik (yani kutupsal koordinatlardan Kartezyen koordinatlara geçiş gibi bir yeniden parametrelendirme ile çıkarım dönüşümleri), istatistiksel tutarlılık (yani çok zor problemler için bile MML herhangi bir temel modele yakınsar) ve verimlilik (örn. yani MML modeli, mümkün olan en kısa sürede herhangi bir gerçek temel modele yakınsayacaktır). CS Wallace ve DL Dowe (1999), MML ile algoritmik bilgi teorisi (veya Kolmogorov karmaşıklığı) arasında resmi bir bağlantı olduğunu gösterdi.

Kolmogorov rastgeleliği

Kolmogorov rasgeleliği , bir dizgiyi (genellikle bitlerden oluşan ), ancak ve ancak o dizgiyi üretebilen her bilgisayar programı en azından dizginin kendisi kadar uzunsa rasgele olarak tanımlar . Bunu kesinleştirmek için evrensel bir bilgisayar (veya evrensel Turing makinesi ) belirtilmelidir, böylece "program" bu evrensel makine için bir program anlamına gelir. Bu anlamda rastgele bir dize "sıkıştırılamaz", çünkü dizeyi dizenin kendisinden daha kısa bir programa "sıkıştırmak" imkansız. Her evrensel bilgisayar için, her uzunlukta algoritmik olarak rastgele en az bir dizi vardır. Bununla birlikte, belirli bir dizgenin rastgele olup olmadığı, seçilen belirli evrensel bilgisayara bağlıdır. Bunun nedeni, evrensel bir bilgisayarın kendi içinde sabit kodlanmış belirli bir dizeye sahip olabilmesi ve bu evrensel bilgisayarda çalışan bir programın kısa bir bit dizisi (yani dizenin kendisinden çok daha kısa) kullanarak bu sabit kodlanmış dizeye başvurabilmesidir. .

Bu tanım, sonlu bir alfabeden sonsuz diziler için bir rastgelelik kavramını tanımlamak için genişletilebilir . Bu algoritmik olarak rastgele diziler , üç eşdeğer şekilde tanımlanabilir. Bir yol, etkili bir ölçü teorisi analoğu kullanır ; bir diğeri etkili martingaller kullanır . Üçüncü yol, eğer ilk bölümlerinin öneksiz Kolmogorov karmaşıklığı yeterince hızlı büyürse, sonsuz bir diziyi rastgele olarak tanımlar - n uzunluğundaki bir başlangıç ​​bölümünün karmaşıklığı her zaman en az n - c olacak şekilde bir c sabiti olmalıdır . Bu tanım, sonlu bir dizi için rastgelelik tanımından farklı olarak, önek içermeyen Kolmogorov karmaşıklığını tanımlamak için hangi evrensel makinenin kullanıldığından etkilenmez.

entropi ile ilişkisi

Dinamik sistemler için, yörüngelerin entropi oranı ve algoritmik karmaşıklığı, Brudno'nun bir teoremi ile ilişkilidir, bu eşitlik hemen hemen herkes için geçerlidir . ${\görüntüleme stili K(x;T)=h(T)}$${\görüntüleme stili x}$

Markov bilgi kaynaklarının çıktısı için Kolmogorov karmaşıklığının bilgi kaynağının entropisi ile ilgili olduğu gösterilebilir . Daha kesin olarak, bir Markov bilgi kaynağının çıktısının Kolmogorov karmaşıklığı, çıktının uzunluğu ile normalleştirilir, neredeyse kesin olarak (çıktının uzunluğu sonsuza giderken) kaynağın entropisine yakınsar .

Koşullu sürümler

İki dizinin koşullu Kolmogorov karmaşıklığı , kabaca , prosedüre yardımcı girdi olarak y verilen x'in Kolmogorov karmaşıklığı olarak tanımlanır . ${\görüntüleme stili K(x|y)}$

Bilinen/girdi olarak x'in uzunluğu verilen x'in karmaşıklığı olan bir uzunluk-koşullu karmaşıklık da vardır . ${\görüntüleme stili K(x|L(x))}$

Ayrıca bakınız

• algoritmik bilgi teorisinde önemli yayınlar
• dut paradoksu
• kod golf
• Veri sıkıştırma
• Tanımlayıcı karmaşıklık teorisi
• gramer indüksiyon
• endüktif çıkarım
• Kolmogorov yapı işlevi
• Levenştein mesafesi
• Solomonoff'un endüktif çıkarım teorisi

Notlar

Referanslar

daha fazla okuma

• Blum, M. (1967). "Makinelerin boyutunda" . Bilgi ve Kontrol . 11 (3): 257. doi : 10.1016/S0019-9958(67)90546-3 .
• Brudno, A. (1983). "Entropi ve dinamik bir sistemin yörüngelerinin karmaşıklığı". Moskova Matematik Derneği'nin İşlemleri . 2 : 127–151.
• Kapak, Thomas M.; Thomas, Sevinç A. (2006). Bilgi teorisinin unsurları (2. baskı). Wiley-Interscience. ISBN'si 0-471-24195-4.
• Lajos, Rónyai; Gabor, İvanyos; Reka, Szabo (1999). Algoritmusok . TypoTeX. ISBN'si 963-279-014-6.
• Li, Ming; Vitanyi, Paul (1997). Kolmogorov Karmaşıklığına Giriş ve Uygulamaları . Springer. ISBN'si 978-0387339986.
• Yu, Manin (1977). Matematiksel Mantıkta Bir Ders . Springer-Verlag. ISBN'si 978-0-7204-2844-5.
• Sipser, Michael (1997). Hesaplama Teorisine Giriş . PWS. ISBN'si 0-534-95097-3.

Dış bağlantılar

• Andrei Nikolaevich Kolmogorov'un Mirası
• Chaitin'in çevrimiçi yayınları
• Solomonoff'un IDSIA sayfası
• Algoritmik bilgilerin genellemeler tarafından J. Schmidhuber
• "Li Vitanyi 1997 İncelemesi" .
• Tromp, John. "John'un Lambda Analizi ve Birleştirici Mantık Oyun Alanı" . Tromp'un lambda hesabı bilgisayar modeli, K() için somut bir tanım sunar]
• Kolmogorov Karmaşıklığına dayalı Evrensel Yapay Zeka ISBN  3-540-22139-5 , M. Hutter : ISBN  3-540-22139-5
• David Dowe 'ın Asgari Mesaj Uzunluğu (MML) ve Occam'ın ustura sayfaları.
• Grunwald, P.; Pitt, MA (2005). Myung, IJ (ed.). Asgari Açıklama Uzunluğundaki Gelişmeler: Teori ve Uygulamalar . MİT Basın. ISBN'si 0-262-07262-9.