算法信息論 (AIT) 是理論計算機科學的一個分支，它關注計算與可計算生成對象（與隨機生成對象相對）的信息之間的關系，例如字符串或任何其他數據結構。 換句話說，在算法信息論中表明，計算不可壓縮性模仿（除了僅取決于所選擇的通用編程語言的常數）信息論中發現的關系或不等式。 按照 Gregory Chaitin 的說法，它是將香農的信息論和圖靈的可計算性理論放入雞尾酒調酒器中，用力搖晃的結果。

除了對可計算生成對象的不可約化信息內容的通用度量進行形式化之外，AIT 的一些主要成就還表明：事實上，算法復雜性遵循（在自定界的情況下）與熵相同的不等式（常數除外） 和經典信息論一樣； 隨機性是不可壓縮的； 并且，在隨機生成的軟件領域內，任何數據結構出現的概率與在通用機器上運行時生成它的最短程序的數量級相當。

AIT 主要研究字符串（或其他數據結構）的不可約信息內容的度量。 因為大多數數學對象都可以用字符串來描述，或者作為字符串序列的極限來描述，所以它可以用來研究各種各樣的數學對象，包括整數。 AIT 背后的主要動機之一是研究元數學領域中數學對象所攜帶的信息，例如，如下面提到的不完整結果所示。 其他主要動機來自超越經典信息論對單一和固定對象的局限性，形式化隨機性的概念，以及在沒有先驗概率分布知識的情況下找到有意義的概率推理（例如，是否獨立同分布，馬爾可夫， 甚至靜止）。 這樣，眾所周知，AIT 基本上建立在三個主要數學概念及其之間的關系之上：算法復雜性、算法隨機性和算法概率。

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

通俗地說，從算法信息論的角度來看，一個字符串的信息內容等同于該字符串的xxx壓縮可能自包含表示的長度。 自包含的表示本質上是一個程序——在一些固定但不相關的通用編程語言中——運行時輸出原始字符串。

從這個角度來看，一本 3000 頁的百科全書實際上包含的信息少于 3000 頁完全隨機的字母，盡管事實上百科全書的用處要大得多。 這是因為要重建整個隨機字母序列，必須知道每個字母是什么。 另一方面，如果從百科全書中刪除每個元音，具有合理英語知識的人可以重建它，就像可以根據上下文和出現的輔音重建句子 Ths sntnc hs lw nfrmtn cntnt 一樣。

與經典信息論不同，算法信息論給出了隨機字符串和隨機無限序列的正式、嚴格的定義，這些定義不依賴于關于不確定性或似然性的物理或哲學直覺。 （隨機字符串的集合取決于用于定義 Kolmogorov 復雜性的通用圖靈機的選擇，但任何選擇都會給出相同的漸近結果，因為字符串的 Kolmogorov 復雜性直到加法常數才不變，僅取決于通用圖靈機的選擇 . 由于這個原因，隨機無限序列的集合獨立于通用機器的選擇。）

算法信息論的一些結果，例如蔡廷不完備性定理，似乎挑戰了普通的數學和哲學直覺。 其中最值得注意的是 Chaitin 常數 Ω 的構造，它是一個實數，表示當一個自定界通用圖靈機的輸入由拋硬幣提供時停止的概率（有時被認為是概率 一個隨機的計算機程序最終會停止）。 盡管 Ω 很容易定義，但在任何一致的可公理化理論中，人們只能計算 Ω 的有限位數，因此它在某種意義上是不可知的，提供了一個讓人想起哥德爾不完備性定理的知識的xxx限制。