更改

    另外找寻斑图的路径可以沿着逻辑基础数学的传统探究来进行，象弗雷格、希尔伯特所表达的和丘奇、哥德尔、波斯特、罗素、图灵、和怀特海所先行的。最近的，也是和流行更有关联的方法则是回到柯尔莫哥洛夫和蔡汀，他们的研究领域恰巧在于重构单独的物件【35，38】；尤其是，他们聚焦于离散符号系统，而不是（说）实数或其他数学物件。用于表征斑图P的备选项有通用图灵机（Universal Turing machine, UTM）程序——尤其是，刚好生成物件O的最短UTM程序。这个程序的长度被叫作O的柯尔莫哥洛夫和蔡汀复杂度。注意到任何体系——自动机，语法，又或者有什么不是——这些是图灵等价的，而且对那些“长度”的观念是定义优良的，将用于表征体系。自从我们可以将这些一个设备转换到另一个——比如说，从一个波斯特标记系统【39】到图灵机——对第一个系统只使用有限的描述，当使用这种方法来衡量复杂性时，这类约束容易被融合到一块。

    另外找寻斑图的路径可以沿着逻辑基础数学的传统探究来进行，象弗雷格、希尔伯特所表达的和丘奇、哥德尔、波斯特、罗素、图灵、和怀特海所先行的。最近的，也是和流行更有关联的方法则是回到柯尔莫哥洛夫和蔡汀，他们的研究领域恰巧在于重构单独的物件【35，38】；尤其是，他们聚焦于离散符号系统，而不是（说）实数或其他数学物件。用于表征斑图P的备选项有通用图灵机（Universal Turing machine, UTM）程序——尤其是，刚好生成物件O的最短UTM程序。这个程序的长度被叫作O的柯尔莫哥洛夫和蔡汀复杂度。注意到任何体系——自动机，语法，又或者有什么不是——这些是图灵等价的，而且对那些“长度”的观念是定义优良的，将用于表征体系。自从我们可以将这些一个设备转换到另一个——比如说，从一个波斯特标记系统【39】到图灵机——对第一个系统只使用有限的描述，当使用这种方法来衡量复杂性时，这类约束容易被融合到一块。

    特别地，考虑O前面的n个字符On，和生成他们的最短程序Pn。我们询问，下式的极限会怎么样

    特别地，考虑<math>\mathcal{O}</math>前面的n个字符<math>\mathcal{O}_n</math>，和生成他们的最短程序<math>\mathcal{P}_n</math>。我们询问，下式的极限会怎么样

<math>

<math>

\lim_{n \to \infty} \frac{\lvert P_n \rvert} {n},

\lim_{n \to \infty} \frac{\lvert \mathcal{P}_n \rvert} {n},

</math>

</math>

当|P|是程序P的比特长度时？从一方面来看，如果有一个固定长度的程序P能生成O的任意若干比特位，那么这个极限将会消失。在我们感兴趣的绝大多数域里，有理数或无理数——比如π, e,√2——属于这个域。这些数域是非常压缩的：程序P是压缩的描述，所以它能捕捉符合描绘O序列的斑图。如果这个极限趋于1，从另一方面来看，我们拥有一个完全未压缩的描述和结论，按柯尔莫哥洛夫和蔡汀的观点，O是随机的【35-38，40，41】。这个结论正是需要的：柯尔莫哥洛夫和蔡汀框架建立了，至少在形式上，单个物体的随机性，不在提出概率描述或重构事件系综。它之所以能做到这样，是涉及到一个确定性的，算法表征——通用图灵机（UTM）。

当<math>\lvert \mathcal{P} \rvert</math>是程序<math>\mathcal{P}</math>的比特长度时？从一方面来看，如果有一个固定长度的程序<math>\mathcal{P}</math>能生成<math>\mathcal{O}</math>的任意若干比特位，那么这个极限将会消失。在我们感兴趣的绝大多数域里，有理数或无理数——比如<math>π, e,\sqrt{2}</math>——属于这个域。这些数域是非常压缩的：程序<math>\mathcal{P}</math>是压缩的描述，所以它能捕捉符合描绘<math>\mathcal{O}</math>序列的斑图。如果这个极限趋于1，从另一方面来看，我们拥有一个完全未压缩的描述和结论，按柯尔莫哥洛夫和蔡汀的观点，<math>\mathcal{O}</math>是随机的【35-38，40，41】。这个结论正是需要的：柯尔莫哥洛夫和蔡汀框架建立了，至少在形式上，单个物体的随机性，不在提出概率描述或重构事件系综。它之所以能做到这样，是涉及到一个确定性的，算法表征——通用图灵机（UTM）。

    将柯尔莫哥洛夫复杂度应用于自然过程，有一些众所周知的困难。首先，作为数量，它却不能进行通用计算，因为有停机问题【38】。第二，对随机过程它是最大化的。这些可以被建构起来，如同称心的一样，如同刚刚提到的。或者捕捉斑图失败，看个人的目标了。第三，它只能应用于一个过程；再一次地这可能是优点，也可能是缺点。第四，它没有为噪音或失误预留，要求准确地重构。最后，lim n->∞|Pn|/n可能消失，尽管需要运行程序的可计算资源，比如时间和存储，增长到无界。

将柯尔莫哥洛夫复杂度应用于自然过程，有一些众所周知的困难。首先，作为数量，它却不能进行通用计算，因为有停机问题【38】。第二，对随机过程它是最大化的。这些可以被建构起来，如同称心的一样，如同刚刚提到的。或者捕捉斑图失败，看个人的目标了。第三，它只能应用于一个过程；再一次地这可能是优点，也可能是缺点。第四，它没有为噪音或失误预留，要求准确地重构。最后，<math>\lim \nolimits_{n \to \infty} \lvert \mathcal{P}_n \rvert / n</math>可能消失，尽管需要运行程序的可计算资源，比如时间和存储，增长到无界。

    这个障碍并不能阻止研究者在实际任务中放弃使用柯尔莫哥洛夫-蔡汀复杂度——比如测量自然物体（例子在参考文献【42】），作为归纳推理的理论基石【43，44】，也是捕捉斑图的一般意义【45】。如Rissanen【46， p. 49】所说，这个同“用写程序来学习【数据集】的属性，希望能找到最短的一个”类似。

    这个障碍并不能阻止研究者在实际任务中放弃使用柯尔莫哥洛夫-蔡汀复杂度——比如测量自然物体（例子在参考文献【42】），作为归纳推理的理论基石【43，44】，也是捕捉斑图的一般意义【45】。如Rissanen【46， p. 49】所说，这个同“用写程序来学习【数据集】的属性，希望能找到最短的一个”类似。