算法信息論

算法信息理論主要研究字符串（或其他數據結構）的複雜性度量。因為大多數數學對象可以用字符串來描述，或者作為字符串序列的限制，它可以用於研究各種各樣的數學對象，包括整數。

非正式地，從算法信息理論的觀點來看，字符串的信息內容等於該字符串的最壓縮的可能的自包含表示的長度。一個自包含的表示本質上是一個程序 - 在一些固定但不相關的通用編程語言中 - 當運行時，輸出原始字符串。

從這個角度來看，一本3000頁的百科全書實際上包含的信息少於3000頁完全隨機的字母，儘管百科全書更有用。這是因為要重建整個隨機字母序列，必須或多或少知道每個字母是什麼。另一方面，如果每個元音都從百科全書中刪除，那麼對英語有合理知識的人就可以重建它，就像人們可能從上下文和輔音中重建句子“Ths sntnc hs lw nfrmtn cntnt”一樣。

與經典信息理論不同，算法信息理論給出了隨機字符串和隨機無限序列的正式，嚴格的定義，這些定義不依賴於關於非確定性或可能性的物理或哲學直覺。（隨機字符串的集合取決於用於定義Kolmogorov複雜度的通用圖靈機的選擇，但任何選擇都給出相同的漸近結果，因為字符串的Kolmogorov複雜度不變，只取決於通用圖靈的選擇的附加常數因此，隨機無限序列集與通用機器的選擇無關。）

算法信息理論的一些結果，如Chaitin的不完備性定理，似乎挑戰了常見的數學和哲學直覺。其中最值得注意的是Chaitin常數Ω的構造，這是一個實數，表示當自動定界通用圖靈機的輸入由公平硬幣的翻轉提供時停止的概率（有時被認為是隨機的概率）計算機程序最終會停止）。儘管Ω很容易定義，但在任何一致的公理化理論中，人們只能有限地計算Ω的多個數字，因此它在某種意義上是不可知的，它提供了對知識的絕對限制，這讓人聯想到哥德爾的不完備性定理。雖然Ω的數字無法確定，但Ω的許多屬性是已知的;例如，它是一個算法隨機序列，因此它的二進制數字是均勻分佈的（事實上它是正常的）。

算法信息理論由Ray Solomonoff 創立，他發表了該領域作為算法概率發明的一部分的基本思想 - 一種克服與貝葉斯統計規則應用相關的嚴重問題的方法。他首先在1960年加州理工學院的一次會議上描述了他的結果，並在1960年2月的一份報告中，“關於歸納推理的一般理論的初步報告。”算法信息理論後來由Andrey Kolmogorov獨立開發。1965年和格雷戈裏柴蒂，大約在1966年。

Kolmogorov複雜性或算法信息有幾種變體;最廣泛使用的是基於自我劃分的程序，主要歸功於Leonid Levin（1974）。 Per Martin-Löf也為無限序列的信息理論做出了重要貢獻。 Mark Burgin在由Andrey Kolmogorov（Burgin，1982）出版的一篇論文中介紹了一種基於Blum公理（Blum 1967）的算法信息理論的公理方法。公理化方法包含算法信息理論中的其他方法。可以將算法信息的不同度量視為算法信息的公理定義度量的特定情況。不是為每個特定量度證明類似的定理，例如基本不變定理，而是可以從公理設置中證明的一個相應定理中容易地推導出所有這些結果。這是數學中公理化方法的一般優勢。算法信息理論的公理化方法在書中進一步發展（Burgin 2005）並應用於軟件度量（Burgin和Debnath，2003; Debnath和Burgin，2003）。

主要文章：Kolmogorov複雜性

如果字符串的Kolmogorov複雜度至少是字符串的長度，則稱二進制字符串是隨機的。一個簡單的計數參數顯示任何給定長度的某些字符串是隨機的，幾乎所有字符串都非常接近隨機。由於Kolmogorov複雜性取決於通用圖靈機的固定選擇（非正式地，給出“描述”的固定“描述語言”），隨機字符串的集合確實取決於固定通用機器的選擇。然而，無論固定機器如何，隨機字符串的集合都具有相似的屬性，因此可以（並且經常）將隨機字符串的屬性作為一組進行討論，而無需首先指定通用機器 ^[1]  。

主要文章：算法隨機序列

如果對於所有n，對於某些常數c，無限二進制序列被認為是隨機的，序列長度n的初始段的Kolmogorov複雜度至少為n-c。可以證明，幾乎每個序列（從標準測量的角度來看 - “公平硬幣”或Lebesgue測量 - 在無限二元序列的空間上）都是隨機的。此外，由於可以證明相對於兩個不同的通用機器的Kolmogorov複雜度至多相差恆定，因此隨機無限序列的集合不依賴於通用機器的選擇（與有限串相反）。在Per Martin-Löf之後，這種隨機性的定義通常稱為Martin-Löf隨機性，以區別於其他類似的隨機概念。它有時也被稱為1-隨機性，以區別於其他更強的隨機性概念（2-隨機性，3-隨機性等）。除了Martin-Löf隨機性概念之外，還有遞歸隨機性，Schnorr隨機性和Kurtz隨機性等.Jongge Wang表明所有這些隨機性概念都不同。