更新时间：2022-08-25 16:58
算法信息论（Algorithmic information theory）是使用理论计算机科学的工具，研究复杂性概念的学科领域。它是信息理论的一环，关注计算与信息之间的关系。按照Gregory Chaitin的说法，它是“把香农的信息论和图灵的可计算论放在调酒杯使劲摇晃的结果。”
算法信息理论主要研究字符串（或其他数据结构）的复杂性度量。因为大多数数学对象可以用字符串来描述，或者作为字符串序列的限制，它可以用于研究各种各样的数学对象，包括整数。
非正式地，从算法信息理论的观点来看，字符串的信息内容等于该字符串的最压缩的可能的自包含表示的长度。一个自包含的表示本质上是一个程序 - 在一些固定但不相关的通用编程语言中 - 当运行时，输出原始字符串。
从这个角度来看，一本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复杂性取决于通用图灵机的固定选择（非正式地，给出“描述”的固定“描述语言”），随机字符串的集合确实取决于固定通用机器的选择。然而，无论固定机器如何，随机字符串的集合都具有相似的属性，因此可以（并且经常）将随机字符串的属性作为一组进行讨论，而无需首先指定通用机器。
主要文章：算法随机序列
如果对于所有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表明所有这些随机性概念都不同。