计算机科学如何定义和度量信息？

对于确定性计算，输出中呈现的信息必然也以某种方式呈现在输入中——信息必须来自某处。计算机不会产生信息；它们被重排、计算、复制和删除，但不会无中生有。古谚“太阳底下无新事”道出了确定性计算的精髓。第1章曾说过，对字符串信息量最简单的度量是长度。不过这个简单的度量没有反映出确定性计算不会产生信息的事实。显然许多计算产生的输出要比输入长。

有一种被计算机学家广泛使用的度量，它来自一个认识，就是有许多方式都可以计算出特定的输出。实际上，有无穷多种方式。如果你不信，想一想有多少算术题的答案为8。4+4=8，2+6=8，12-4=8，440-432=8，还有很多，要多少有多少。但是对于任何给定的输出（答案），使用指定的语言，至少有一个最短的输入，即没有更短的输入能产生同样的输出。可能有几个最短输入，都有同样的长度，但总存在一个最短长度，没有长度比它低的输入能产生给定的输出。

为了让你信服，考虑上面的例子，答案为8的所有算术题。显然，4+4（3个符号）比12-4（4个符号）或440-432（7个符号）短。有10个3符号的算术题的输出为数字8:0+8，1+7，2+6，3+5，4+4，8-0，9-1，1×8，2×4和8÷1。它们的长度一样，并且没有比这更短的。如果用二进制编码，这10个表达式的长度不一样，但上面的原理仍然成立:对任何输入，给定计算机和语言，存在某个输入长度，低于这个长度没有输入能产生给定的输出。

20世纪60年代末，苏联数学家柯尔莫哥洛夫将这个认识形式化，并据此给出了不同于香农度量的信息定义。这个度量被称为算法复杂性或柯尔莫哥洛夫复杂性，其基础是通用计算机。前面说过通用计算机是可编程的，因此，它能执行其他计算机能执行的任何计算。你的电脑就是一台通用计算机。功能简单的计算器则不是。

大体上，一个二进制串（0和1组成的串）的算法信息量就是输出为这个串的特定通用计算机的最短输入的长度。这个输入的长度依你选择的计算机和语言的不同而有所不同，但柯尔莫哥洛夫从数学上证明了这个长度的差异不会超过一个常数，这个常数只取决于选择的电脑，与输出无关。这意味着对于很长的输出（远远大于常数），无论采用什么通用计算机（和语言），得出的算法信息量基本是一样的。如果我们选择的机器接受自然语言命令，输入程序“重复1000次01”产生的输出由2000个交替的0和1组成（2000比特长）。这个程序如果直接转化成二进制大约需要50个0和1（50比特）。因此我们可以确定这个2000比特的输出的算法信息量不超过50比特。如果选择其他语言，上限可能可以降低，但绝不会低于15比特，因为重复的串（01）、命令“重复”和数字1000都对算法信息量有贡献。

算法信息与香农信息的共通之处是确定性计算不能创造信息。输出的信息量可以比输入少，但绝不会多。因此算法信息符合我们的直觉，即信息无法无中生有。

如果用一个对象的长度减去其算法信息，差值就是信息的“冗余”或“可压缩性”。这表明一个巧妙的对象表示可以比对象本身短多少仍可以通过适当的确定性计算恢复出对象。压缩文档比原文档短，但可以恢复出原来的0和1的排列。

随机性的概念很难给出精确的数学定义，算法信息提供了一个有力的定义。如果算法信息量和符号序列的长度相等（准确说是差异小于由使用的计算机决定的一个小常数），则序列的结构被认为是算法随机的。这意味着任何确定性计算如果要将这样的序列压缩得更短，都会不可逆地损失一些信息。具有这种属性的序列没有冗余，被认为是随机的。

这种随机性定义揭示出算法信息一个有趣的特性。当比较两个相同长度的序列时，最接近随机的那一个具有最高的信息量。当我们考虑复杂事物时，通常不会认为它们是随机的，而是具有复杂的特定结构。为了认识随机性与复杂性的关系，想一想重现一个特定的序列需要准确说明每一个符号。序列0101010101……（重复1000次01）有许多重复成分。因此可以写一个很短的程序输出这个序列。随机事物缺乏重复性，因此要输出一个特定的随机序列的程序就必须以某种方式包含序列本身。复杂事物的特点是有许多细节，要产生所有这些细节需要很长的程序，因此复杂的事物其算法信息度量有可能也高，但并不总是如此。