银弹的数学解释

                              3柯模哥罗夫复杂性
柯模哥罗夫复杂性也被称为算法信息理论，由R. Solomonoff, G. Chaitin 和 A.N. Kolmogorov 在1960首次提出。我们这里仅仅使用其中的一些基本事实；至于更多的介绍我们推荐阅读论文[20]和教材[19]。
该理论的核心内容是比较简单的:要度量一个对象的复杂性，可以通过度量生成该对象的最短程序的长度来实现。它在描述系统的研究中是一种非常普遍的方法，所谓的描述系统就是我们描述或者定义一个对象的系统，像程序语言，逻辑，描述性集合论都是典型的描述系统。
比如说，一个程序的源代码描述了一个程序的行为；一个公理集合描述一类数学结构。
一般来说，我们有一些需要描述的对象，和描述系统 。描述系统 将一个描述 (对于我们来说是一个程序)映射到对象。要描述一个对象的最常用的方法，是我们编写一个可以生成该对象的一个程序。在这里我们也可以给程序送入一些input,我们通常所说的参数。在某个描述系统中，一个带有参数Y的对象X的柯模哥罗夫复杂性的定义如下:

 
在这里描述系统

  是一个程序语言，我们可以把等式(2)看作是寻找一个对于给定参数y输出结果x的最短程序。参数y对于度量  的长度没有什么贡献。忽略参数y,我们可以得到一个更简洁的表述，  这里是一个空字符串。

例如，我们可以选择Java作为描述系统的程序语言，那么对于某个字符串x,那么它的柯模哥罗夫复杂性就是可以输出x的最短Java代码的长度。为了确定是否使用库L可以缩短代码长度，我们可以考虑将Java和库L整合成一个描述系统，称为Java+L,然后比较CJava+L(x) 和CJava(x)的长度。显而易见的是，在这里选择什么语言是无关紧要的。

事实3.1(不变性[19,§2.1]). 存在一个万能机U,当是某个有效的描述系统(例如一个程序语言),那么总存在一个常数c使得对任意X皆成立。

这条事实意味着，万能机U可以将复杂性最优到一个常数因子。因此我们可以忽略下标U,将x的柯模哥罗夫复杂性直接写作C(x),来表示它仅由常数因子所决定。

某些字符串有很短的描述:比如一个有万亿长度的0字符串，可以由一个简单的程序描述出来。有一些字符的描述可能和他们自身一样长，比如从一个真实随机设备中产生的一百万个bit二进制随机字符串。在柯模哥罗夫复杂性中反复出现的一个话题就是,永远不存在足够的描述去给出或者计算出大多数对象的最短描述。在这里我们把对象和描述都看成二进制字符串，我们就可以得出下面这个众所周知的结论:对一个被选定的字符串，要将其压缩的比常量因子更小的概率为0。

事实3.2(不可压缩性[19, §2.2]) 

设是一个整型函数且 .令x是一个随机平均选定的字符串。那么几乎可以保证

事实3.2 指出，可以将字符串压缩到 或者  （反阿克曼函数）的编码系统其存在的可能性为0. 事实3.2的证明仅仅使用了自然数系统地证明，而没有涉及到描述系统的可计算性。因此等式(3)可以应用在任意的描述系统上，甚至描述系统是不可计算的。比如说,如果我们在论述2.4节时允许使用一个无穷不可计算但是可枚举的库，那么事实3.2也是适用的。不过,它并不适用于像H值小于1时的非均匀分布情形。在本文的后半部分,我们应该假定编译后的程序在事实3.2的意义下都是不可压缩的。

推论3.1 在现有的主流计算结构下，编译后的C程序几乎都满足柯模哥罗夫不可压缩性。

注意,在某一个问题域上，”几乎都满足柯模哥罗夫不可压缩性”并不是在讨论某个特定的编译后程序的可压缩性，而是指如果一个人均匀地随机选取一个可用的编译后程序，那么以相同的方法找到一个更短的程序的可能性为0。在后续的章节里,我们主要研究的问题域是那些

非均匀分布的程序,比如H<1,此时这种不可压缩性的概率会有所改善。

我们对推论3.1做了一个不严谨的证明。这个证明指出,在当前的计算架构下,长度为sbit的编译后程序所描述的确切的行为数目的增长方式约为 。这个结果暗示了编译后程序几乎都满足柯模哥罗夫不可压缩性。C语言的特性非常有利于归并一个程序中的二进制块。比如说,一个二进制字符串z = 0110100111011010,可以用下面这种C语言的声明方式来进行编码。

              unsigned char z[2] = {0x69, 0xda};

此外,这种数组的可以按照邻接的二进制数据存放在编译后程序中，因此一个长度为m的二进制字符串会按照m byte精确的存放在编译后程序中。我们可以用一个长度为常数的小程序将这个数组打包。这个程序从内存中读取二进制字符串然后输出到console。每一个m byte长度的二进制字符串都可以用这样一个程序来表示，其最终长度为c+m bytes，这里c是一个常数表示读取打印工作所需要的额外代码消耗。每一个这样的程序都只会执行唯一的行为，因此sbit长度的编译后程序其确切的行为数目是

注意,未编译过的程序都是高度可压缩的。比如，C语言的源代码可以不含有确定的长度,比如NULL字符0x00.这意味着他们可以(至少)压缩 。因此将我们的讨论的问题限制在编译后程序是非常必要的。