基本介紹
- 中文名：算法資訊理論
- 外文名：Algorithm information theory
- 代表人物：尼古拉耶維奇·柯爾莫哥洛夫
概觀,歷史,準確的定義,
概觀
算法信息理論主要研究字元串（或其他數據結構）的複雜性度量。因為大多數數學對象可以用字元串來描述，或者作為字元串序列的限制，它可以用於研究各種各樣的數學對象，包括整數。
非正式地，從算法信息理論的觀點來看，字元串的信息內容等於該字元串的最壓縮的可能的自包含表示的長度。一個自包含的表示本質上是一個程式 - 在一些固定但不相關的通用程式語言中 - 當運行時，輸出原始字元串。
從這個角度來看，一本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）。
