Algoritmik bilgi kuramı tarafından başlatılan, Kolmogorov , Solomonov ve Chaitin yıllarda 1960 , amaçları ölçmek için ve içerik hak bilgilerini kullanarak, bir veri setinin computability teorisini ve kavramını evrensel makine Turing .
Bu teori, aynı zamanda, bir nesnenin (geniş anlamıyla), onu tanımlamak için çok fazla bilgiye ihtiyaç duyulduğundan daha karmaşık olduğunu düşündüğümüz sürece, bir nesnenin karmaşıklığı fikrini resmileştirmeyi mümkün kılar veya - tersine - bir nesne, tanımı uzun olduğundan daha fazla bilgi içerir. Algoritmik bilgi teorisi bu denkliğe dayanır: Bir nesnenin tanımı bir algoritma (diğer bir deyişle bir Turing makinesi ) ile resmileştirilir ve karmaşıklığı (başka bir deyişle bilgi içeriği) algoritmanın belirli özellikleriyle resmileştirilir: uzunluğu veya hesaplama zamanı.
Bu temeller Shannon'un bilgi teorisinden farklıdır : ikincisi hesaplanabilirlik kavramını kullanmaz ve yalnızca istatistiksel bir veri setiyle ilişkili olarak anlam ifade eder . Bununla birlikte, iki teori uyumludur ve aralarında resmi bağlantılar kurulabilir.
Shannon'un enformasyon teorisinin bilgisayar bilimi, telekomünikasyon, sinyal işleme ve hesaplamalı sinirbilimde birçok uygulaması varken , algoritmik bilgi teorisi biyoloji , fizik ve bilim , hatta felsefe alanlarında başarıyla kullanılmıştır .
Algoritmik bilgi teorisinin ana fikri, bir şeyin daha karmaşık olduğu veya daha fazla bilgiyi içerdiğidir, çünkü açıklaması zor, yani temelde açıklaması uzun . Örneğin, burada nesnelerin üç açıklaması bulunmaktadır:
D1 : “1 m'ye 1 m boyutlarında tamamen beyaz bir duvar. "
D2 : "altta 2 cm genişliğinde, yukarıda 8 cm daha yukarıda, yine 8 cm daha yukarıda, yine 8 cm yukarıda, yine 8 cm yukarıda ve yine 8 cm yukarıda bir yatay kırmızı şerit bulunan, 1 m'ye 1 m'ye tamamen beyaz bir duvar, yine 8 cm yukarıda, yine 8 cm yukarıda, yine 8 cm yukarıda, yine 8 cm yukarıda ve son 8 cm yukarıda. "
D2 ' : “Her 8 cm'de bir aşağıdan yukarıya doğru 2 cm genişliğinde yatay kırmızı şeritlerle 1 m'ye 1 m boyutlarında tamamen beyaz bir duvar. "
Açıklama uzunluğu açısından D1 , D2'den daha kısa olan D2'den daha kısadır . Yani D1 kısa açıklama normal görünüyor, ve anlatılan nesne "daha basit" olması ile ilgilidir. Ancak D2 ve D2 'ile ilgili olarak , açıklanan nesneler aynıdır, ancak D2' , D2'den daha kısadır . Dolayısıyla, bir tanımın ham uzunluğu mükemmel bir şekilde uygun bir ölçü değildir.
"Algoritmik" fikir, daha sonra, açıklanan nesnenin karmaşıklığı olarak, mümkün olan en kısa açıklaması olarak ele alınmalıdır . Tanımın mutlaka kapsamlı olmaması anlamında “algoritmik” fikir - yukarıdaki örnekteki D2 ' gibi - nesneyi elde etmek için bir süreci tanımlayabilir (burada: düzenli aralıklarla yatay bantlar çizme).
Bu nedenle, bir nesne, özelliklerinin kapsamlı bir listesinden daha kısaca tanımlanamadığında daha karmaşık hale gelecektir… Bu son durum, maksimum karmaşıklığın sınır durumunu oluşturur.