Kolmogorov karmaşıklığı
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 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.
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
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:
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 ninci 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 n0 tam sayısı vardır ki U + log2(n0) + C < n0, burada C aşağıdaki programın getirdiği ek uzunluktur:
function IspatlanabilirParadoksalKarakterKatariUret()
      return KarmasikligiIspatlanabilirKarmasikKarakterKatariUret(n0)
      quit
IspatlanabilirParadoksalKarakterKatariUret programı K(s) ≥ n0 formülünün S sisteminde şekilsel olarak ispatlanabildiği s karakter katarını üretir. K(s) ≥ n0 ifadesi tek başına doğrudur. Ancak s aynı zamanda uzunluğu 
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.
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.