《夸克与美洲豹》第八节

本节先给出“原始复杂性”的定义：用双方共享的语言，把一个已知粗粒度的系统描述给远处的人，所需最短消息的长度；逐个部件分开描述会错过利用相似性进行压缩的机会。

本节先给出“原始复杂性”的定义：用双方共享的语言，把一个已知粗粒度的系统描述给远处的人，所需最短消息的长度；逐个部件分开描述会错过利用相似性进行压缩的机会。接着引入“算法信息量”（AIC）：把系统描述编码成0和1的比特串，AIC即能打印出该串并停机的最短程序长度，由柯尔莫哥洛夫、蔡廷、索洛莫洛夫于60年代各自提出。编码方式、计算机软硬件等因素会带来随意性，理论家通常只关心比特串趋于无限长时AIC的增长情况，此时这些差异可忽略。

随后区分AIC与信息：信息关乎在等概率的两选一中作抉择，如抛硬币和“二十个问题”游戏，20个比特相当于从2的20次方个等概率对象中作出选择；AIC则针对单个比特串，测度其内部规律。规律性强的串可压缩、AIC低；数学上可证大多数串不可压缩，称为随机串，AIC最大。AIC的奇特之处在于不可计算：蔡廷证明我们无法确知哪些串是随机的，总可能存在尚未发现的进一步压缩方法，这与哥德尔否定公理系统完备性的结论相呼应。