算法信息论

算法信息论 (AIT) 是理论计算机科学的一个分支，它关注计算与可计算生成对象（与随机生成对象相对）的信息之间的关系，例如字符串或任何其他数据结构。

换句话说，在算法信息论中表明，计算不可压缩性模仿（除了仅取决于所选择的通用编程语言的常数）信息论中发现的关系或不等式。

按照 Gregory Chaitin 的说法，它是将香农的信息论和图灵的可计算性理论放入鸡尾酒调酒器中，用力摇晃的结果。

除了对可计算生成对象的不可约化信息内容的通用度量进行形式化之外，AIT 的一些主要成就还表明：事实上，算法复杂性遵循（在自定界的情况下）与熵相同的不等式（常数除外）和经典信息论一样； 随机性是不可压缩的； 并且，在随机生成的软件领域内，任何数据结构出现的概率与在通用机器上运行时生成它的最短程序的数量级相当。

AIT 主要研究字符串（或其他数据结构）的不可约信息内容的度量。因为大多数数学对象都可以用字符串来描述，或者作为字符串序列的极限来描述，所以它可以用来研究各种各样的数学对象，包括整数。

AIT 背后的主要动机之一是研究元数学领域中数学对象所携带的信息，例如，如下面提到的不完整结果所示。

其他主要动机来自超越经典信息论对单一和固定对象的局限性，形式化随机性的概念，以及在没有先验概率分布知识的情况下找到有意义的概率推理。这样，众所周知，AIT 基本上建立在三个主要数学概念及其之间的关系之上：算法复杂性、算法随机性和算法概率。

算法信息论主要研究字符串（或其他数据结构）的复杂性度量。 因为大多数数学对象都可以用字符串来描述，或者作为字符串序列的极限来描述，所以它可以用来研究各种各样的数学对象，包括整数。

通俗地说，从算法信息论的角度来看，一个字符串的信息内容等同于该字符串的xxx压缩可能自包含表示的长度。 自包含的表示本质上是一个程序——在一些固定但不相关的通用编程语言中——运行时输出原始字符串。

与经典信息论不同，算法信息论给出了随机字符串和随机无限序列的正式、严格的定义，这些定义不依赖于关于不确定性或似然性的物理或哲学直觉。

随机字符串的集合取决于用于定义 Kolmogorov 复杂性的通用图灵机的选择，但任何选择都会给出相同的渐近结果，因为字符串的 Kolmogorov 复杂性直到加法常数才不变，仅取决于通用图灵机的选择。由于这个原因，随机无限序列的集合独立于通用机器的选择。

算法信息论的一些结果，例如蔡廷不完备性定理，似乎挑战了普通的数学和哲学直觉。其中最值得注意的是 Chaitin 常数 Ω 的构造，它是一个实数，表示当一个自定界通用图灵机的输入由抛硬币提供时停止的概率（有时被认为是概率 一个随机的计算机程序最终会停止）。

尽管 Ω 很容易定义，但在任何一致的可公理化理论中，人们只能计算 Ω 的有限位数，因此它在某种意义上是不可知的，提供了一个让人想起哥德尔不完备性 定理的知识的绝 对限制。