夸克与美洲豹 作者:[美]盖尔曼-第6章
按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
付缺旧砭鸵丫屑阜种鞴坌粤恕览涤诠鄄煺呋蚬鄄焐璞浮Ｄ敲矗导噬希颐钦谔致垡桓龌蚋嗟囊览涤谝桓鱿低扯粤硪桓鱿低车拿枋龅母丛有缘亩ㄒ澹饫铮┬忻枋龅南低臣俣ㄎ桓龈丛邮视ο低常梢允且桓鋈死喙鄄煺摺Ｎ讼衷诘哪康模颐遣环良俣枋鱿低尘褪侨死喙鄄煺摺�
为了使描述长度的概念更加精确，我们应该避免通过显示某一事物来对它进行描述；很显然，显示一个复杂适应系统与显示一个简单系统一样地容易。因此，我们只关心以通信的方式被传递给远处某个人的描述。同样，我们也可以很容易地给某个相当复杂的物体取名为“山姆”或“朱蒂”，从而使得对它的描述大大变短。因此，用于描述的语言必须是事先为大家所公认的，不能为描述而新造一些术语。当然，即便如此，这里也仍然存在着多种随意性与主观性。描述长度将随所使用的语言以及通信者对他们所共享之世界的了解与理解的不同而不同。例如，在描述一头犀牛时，若双方都知道什么是哺乳动物的话，那么关于犀牛的信息就可以缩短。如果要描述一个小行星的轨道，那么双方是否都懂得牛顿引力定律和牛顿第二运动定律，将产生很大的差别——双方是否知道火星、木星与地球的轨道，对描述长度也很重要。简洁性和原始复杂性如果由于一些无用的字、词而使得一个描述很长怎么办呢？我想起了这样一个故事，一个小学教师给她的学生布置家庭作业，要求他们写一篇300 字的作文。有个学生由于整个周末都用于玩耍，没有做作业，结果他在星期一的早上写了这么一段：“昨天晚上，邻居家的厨房里着火了，我把头伸出窗外，大喊，‘起火了！起火了！起火了！？？’”这个小孩将“起火了”重复了很多遍，直到凑足了300 字为止。然而，如果没有300字这一要求，小孩就会写“叫了90 多遍‘起火了’”来表达同样的意思。因此，在讨论复杂性的定义时，我们关心的是用来描述系统的可能的最短信息的长度。
下面几点可以概括起来作为“原始复杂性”的定义：用双方事先共享（且彼此均知道共享这一事实）的语言、知识及理解，将一个已知粗粒化程度的系统描述给远处某人时，所用最短消息的长度。某些用来描述系统的常见方法是产生不出最短消息的。例如，如果我们将系统的各个部分（比如汽车的部件或人体的细胞）分开描述，并讲述这样一些部分怎样组成一个整体，那么，我们忽略了许多压缩消息的机会。在那些机会中，我们可以利用各部分之间的相似性。例如，人体中的大部分细胞有着相同的基因，并有很多其他的共同特征，而同一个组织中的细胞则更加相似。最短的描述应将这些因素考虑进去。算法信息量
某些信息论专家使用一个与原始复杂性极其相似的量，不过他们的定义更专门化，而且自然而然地牵涉到计算机。他们拟想出一个具有给定粗粒度的描述，这个描述用一种给定的语言来表示，然后再用某种标准编码程序译成一串0 和1。每个被选的数1 或0 被称为一个“比特”（bit）。（本来，比特是“二进制数”的缩写，说其为二进制的，是因为只有两种可选的数字，而对通常的十进制数来说，则有10 个：0，1，2，3，4，5，6，7，8，9。）他们关心的是那个比特串或“消息串”（message string）。他们定义的量称为“算法复杂性”、“算法信息量”（algo…rithmicinformation content）或“算法随机性”。当今，“算法”（algorithm）一词指的是一种计算规则，通过意义的延伸，又可以指一个计算程序。下面我们将会看到，算法信息量指的是一种计算机程序的长度。本来，算法一词的意思不是这样的。这个词听起来像是出自希腊语“算术”（arithmetic）一词，但事实上，那只是个假象。“algorithm”中的“th”是由“arithmetic”中的“th”类推而被插入的，实际上它本不属于那里。一个更能反映语源的拼写应该是“algorism”，它是一个人的名字，正是通过这个人所写的书，“零”才被首次引入到西方文化中。他就是9 世纪的阿拉伯数学家穆罕默德·艾宾·穆沙·阿尔花拉子模（MuhammadibnMusa al…Khowarizmi）。这个姓表明，他的家族来自咸海南边花拉子模地区，现为新近独立的乌兹别克斯坦共和国的一部分。他写了一篇数学论文，题目中包含“阿尔加布”（ aljabr）这一阿拉伯的词，意为“移项”，我们现在的“代数”一词就出自这里。最初，“algorism”（计算）一词指的是十进制法，人们认为它主要是通过将阿尔花拉子模的“代数学”翻译成拉丁文而由印度传入欧洲的。
算法信息量（AIC）是本世纪60 年代由三个创始者各自率先使用的。三个人中，一个是伟大的俄罗斯数学家安德里·N·柯尔莫哥洛夫（AndreiN． Kolmogorov），一个是当时只有 15 岁的美国人格里高里·蔡廷（GregoryChaitin），还有一个也是美国人，叫雷·索洛莫洛夫（Ray Solomonoff）。每个人都是假想一个理想的多功能计算机，它可以存贮无限大的信息量（或者信息存贮量有限，但可随需要而任意扩充容量）。这个计算机配备有特殊的硬件和软件。然后他们考虑一个特殊的信息串，并寻求一个计算程序，使计算机打印出这一信息串，随后停机。一个最短的程序的长度就是该信息串的AIC。
我们已经看到，源于粗粒化和用来描述系统的语言等因素的主观性或随意性，是原始复杂性之定义所固有的。在AIC 中，又产生了附加的随意性来源，即用来把对系统的描述转化为一个比特串的特殊编码程序，以及与计算机有关的硬件和软件。
数学信息理论家们并不担心这种随意性，因为他们通常只关心一些极限情形，在那些极限情形下，有限的随意性就变得不那么重要了。他们喜欢考虑一些相似而长度渐增的比特串，研究在长度趋于无限大的过程中，AIC 如何变化。（这使我想起来，计算机科学家们如何喜欢处理大小递增并趋向无穷的一系列相似问题的计算复杂性。）
让我们回到理想化并行处理计算机问题上来，这样一个计算机由一些计算单元组成。我们用点来表示这些单元，用线表示这些单元之间的通信连接。这里，柯尔莫哥洛夫、蔡廷和索洛莫洛夫是不会对仅8 个点中各种可能的连接方式的AIC 感兴趣的。他们关注的是当N 趋向无限大时，N 个点中的连接情况。在这种情况下，由于使用某个计算机而不是另一个，使用某种编码程序而非另一种，使用一种语言而不是另一种等等所造成的差异，而导致AIC 方面的某些差别（例如，最简单的连接方式与最复杂的连接方式之间的差异），相形之下都不那么重要了。一个信息理论家关心的是某个特定的AIC 是否随N 趋向于无穷而不断增长，如果是，增长的快慢如何。他或她不怎么关心某个AIC 与另一个AIC 之间由于系统描述中的种种不定性而引起的无关紧要的差异。
我们可以从那些理论家那里获得一些有趣的经验，那就是，即使我们不限于研究那些趋于无限大的系统，我们也应该懂得，随着比特串逐渐变长，关于简单性与复杂性的讨论变得越来越有意义。在另一种极端情形，即比特串中只有一个比特，谈论简单性与复杂性显然是毫无意义的。信息的定义
现在我们必须对算法信息量与信息作出区分。这方面有一些人，比如，现代信息理论的奠基人克劳德·香农（Claude Shan…non）曾经讨论过。信息主要涉及到从被选物中作出抉择，如果那些被选物可以简化为一序列两种选择，其中每种选择的或然性完全一样，那么，我们可用一种最简单的方式将其表示出来。例如，假若你得知抛硬币的结果是反面而不是正面，那么你就获得了一个比特的信息。如果你获悉三次连续抛币的结果是正面、反面和正面，那说明你已经获得三个比特的信息。
“二十个问题”的游戏在或然性相同或或然性近乎相同的一连串两种选择中，提供了一个表示各种极不相同的信息的极好例子。游戏由两个人来玩，第一个人构思一个东西，然后第二个人要在被告知它是动物、蔬菜、还是无机物之后，用20 或不到20 个问题来猜出这个东西。问题的答案只能是“是”或“否”；每次回答都是一次两种选择。对第二个人来说，他提出的问题要尽可能在两个或然性接近相同的被选物之间作出选择，这将会对自己最有利。例如，在知道该东西是无机物时，提问者不应该直截了当地问它是不是霍普（Hope）钻石。他可以问，“它是天然的（而不是人工制造或改造的）吗？”这里，肯定回答和否定回答的概率是大致相等的。如果回答是“否”，那么下一个问题可以问：“它是一个特殊的物体而非一类物体吗？”当回答“是”与“否”的概率相等时，每个问题将引出一个比特的信息（这是一个问题所能引出的最多的信息）。20 个比特的信息相当于从1，048，576 个或然性相等的被选物中作出一个选择，其中1，048，576 是20 个2 的乘积（2 的20 次方）。这一乘积是长度为20 的各种不同比特串的数目。
要特别提及的是，在讨论AIC 与信息时，比特串的用法是不一样的。在算法信息量情形下，考虑的是单个的比特串（最好是长比特串），它内部的规律是用一个通用计算机打印出该比特串到停机的最短程序长度（用比特表示）来测度的。与之形成对比的是，在信息的情形下，你可能考虑从具有给定长度的所有各种不同的比特串中作出一个选择。若它们的或然性均相同的话，他们的长度就是信息的比特数。
你也可以考虑一组比特串，比如或然性相同的一组，每个比特串都有其特定的AIC 值。在这种情况下，定义一个由比特串的数目及该组比特串的平均的AIC 值所决定的信息数量，往往很有用。压缩和随机串
算法信息量有一个很奇特的性质，为了对它进行讨论，我们有必要先来看看不同消息串的相对“可压缩性”。对于一个有给定长度（不妨假设很长）的比特串来说，我们可以探究，何时其算法复杂性高，何时其算法复杂性低。如果一个长的比特串为110110110110110110110？110110，那么，我们可以通过一个表达“将110 打印若干次”的极短的程序来得到它。这样一个比特串具有一个很低的AIC，尽管它的长度很长。这意味着它具有很大的可压缩性。
与此相对照的是，在数学上可以证明，大多数具有某一给定长度的比特串是不能压缩的。换句话说，能够产生这些串（并进而使计算机停机）的最短程序为，在PRINT 后写上整个数串。具有给定长度的这样一个比特串有着最大的AIC。这儿没有任何规则、算法及理论能够进一步简化这种比特串的描述，从而使之能被用一更短的信息来描述。这样的比特串被称为“随机”串，因为它没有规律可循，因此不能被压缩。随机串具有最大的AIC，这一事实可以解释为什么AIC（算法信息量）又可称为算法随机性。AIC 的不可计算性
AIC 的奇特性在于它的不可计算性。尽管大多数比特串是随机的，但是我们没法准确地知道究竟哪些是随机的。一般来说，我们不能肯定某个给定比特串的AIC 一定不低于我们所认定的。这是因为总可能有一个理论、一种算法能使该比特串被进一步压缩，只是这个理论、算法我们永远也发现不了。更严格地说，我们无法找到能导致进一步压缩的所有理论。格里高里·蔡廷曾在几年前证明过这一论点，他的工作很容易使人想起库特·哥德尔一个著名结论的一部分。哥德尔是一个数学逻辑学家，他在30 年代早期所作出的关于数学公理系统的局限性的发现，曾经震动了整个数学界。在他之前，数学家们曾希望可以设计这样一个数学公理系统，理论上它可以被证明是自治的，并能用来推证所有数学定理的正确性或谬误性。哥德尔证明这些目的一个也不能实现。
像这样的否定性结果往往象征着数学或科学上的巨大进步。我们可以比较一下爱因斯坦关于没有绝对时间或空间，而只有联合时空的发现。事实上，哥德尔和爱因斯坦是好朋友。50 年代早期，在新泽西的普林斯顿高级研究院，我常常看见他们一起步行去工作，但看起来他们这一对给人一种古怪的感觉。哥德尔个子很小，在他的衬托下，爱因斯坦看起来相当高。他们曾经讨论过深奥的数学或物理问题吗？（哥德尔不时地研究一些与广义相对论有关的问题。）或者他们的谈话仅仅是关于天气和他们自身的健康问题？
哥德尔的结论中与我们的讨论有关的部分，是关于不可判定性的问题，即：对于任何一个数学公理系统，原则上总存在一些命题，这些命题在已有的公理基础上不可判定。换句话说，理论上有一些定理既不能被证实，也不能被证伪。
最突出的不可判定的命题是与公理无关的一种陈述。你可以通过引入这样一个陈述作为一个新公理，或引入一个与之相反的陈述，来扩充已有的那组公理。
但是，另外一些不可判定的命题则具有不同的性质。例如，假定一个关于正整数的不可判定的命题的形式如下：“每个大于2 的偶数都有如下性质？？”如果这样一个命题有任何例外，原则上我们可以把它找出来。我们可用足够长的时间，连续检验每个偶数（4，6，8，10，？？），直到发现一个不具备命题中所说性质的数为止。这样就直接证明了该命题是错误的，同时也推翻了它的不可判定性，因为不可判定性的严格意义是，命题不能被证实或证伪。因而，这一命题没有例外情形。一般来说，“真实”这一词的意义是说，该命题是真实的。
下面我们将更加具体地讨论这一点。考虑这样一个特殊的命题，它的正确性经过几个世纪的科学家们的努力也没有得到证明，尽管也没有发现任何例外情况。这个命题就是哥德巴赫猜想（Goldbach’s conjecture），其内容是，每个大于 2 的偶数等于两个素数之和。素数是大于1，且不能被自身和1 以外的任何数整除的数。根据这一点可知，最小的几个素数是2，3，5，7，11，13，17，19，23，29，31 和37。从列出的这些数中可以看出，4 和62 之间的任何偶数都可以用至少一对素数之和来表示。计算机的计算表明，某个相当相当大的数以内的各个偶数都有这样的性质。然而，这样的计算还不能说那个猜想就被证实了，因为对于更大的数它仍然可能失败。只有严密的数学证明才能将猜想变成一个已证明的定理。
没有理由认为哥德巴赫猜想是不可判定的，我们只是假定它是不可判定的。那么由此可知，它应该是真实的，尽管不能证明这一点，因为它可能没有任何例外的情况。任何大于2 的偶数而不能表示为2 个素数之和的存在，将会否证这个猜想，并因此推翻它的不可判定性。
如蔡廷所证明的那样，在问题的背景中往往隐藏着这样一些正确但不可证的理论，或许其中有一个理论能使一个我们认为不可压缩的长信息串能被压缩，或使一个我们认为是最短的信息串能被进一步压缩。因此，一般来说，我们不能确�
