1701065553
复杂 [:1701064734]
1701065554
香农信息
1701065555
1701065556
科学上许多最基本的思想都是由技术进步促进。19世纪的热力学研究就是由改进蒸汽机时遇到的挑战驱使。而数学家香农（Claude Shannon，图3.6）发展信息论也是受20世纪的通信革命推动，尤其是电报和电话的发展。1940年，香农改进了玻尔兹曼的思想，以适用于更为抽象的通信领域。香农在美国电话电报公司（AT&T）贝尔实验室工作。AT&T当时面临的最重要的问题就是如何通过电报和电话线快速有效地传送信息。
1701065557
1701065558
1701065559
1701065560
1701065561
▲图3.6 香农（1916—2001）（经朗讯公司贝尔实验室许可使用）
1701065562
1701065563
香农从数学上解决了这个问题，从而开创了一个新领域——信息论。1948年，香农发表了论文“通信的数学理论”， [47] 在文中香农给出了信息的一个狭义定义，并且证明了一个非常重要的定理，定理给出了通过给定通道传输的最大可能传输率，无论信道是否存在噪声。这个最大传输率就是信道容量（channel capacity）。
1701065564
1701065565
香农的信息定义中有一个发送者向接收者发送信息。例如图3.7有两个发送者通过电话与接收者交谈的例子。发送者说的每个词都是香农意义上的信息。电话并不理解所说的词，而只是传送编码声音的电脉冲，香农对信息的定义也完全忽略信息的意义，而只考虑发送者向接收者发送信息的速度。
1701065566
1701065567
香农问：“发送者传送了多少信息给接收者呢？”与玻尔兹曼的思想类似，香农将宏观状态（这里是发送者）的信息定义为可以由发送者发送的可能微观状态（可能信息的集合）的数量的函数。我的儿子尼可还在蹒跚学步时，我会让他通过电话同奶奶讲话。他喜欢讲电话，不过只会说一个词——“Da”。他发给奶奶的信息是“Da Da Da Da Da……”换句话说，尼可的宏观状态只有一种可能的微观状态（“Da”序列），因此虽然这个宏观状态很有趣，但信息量却为零。奶奶知道听到的会是什么。我的儿子杰克两岁了，他也喜欢讲电话，不过他的词汇量大些，因此会告诉奶奶他干的事情，经常让奶奶对他讲的话吃惊。显然发送者杰克的信息量要多得多，因为可能的微观状态——即各种不同的信息组成的集合——要多得多。
1701065568
1701065569
1701065570
1701065571
1701065572
▲图3.7 上图：尼可同奶奶交谈的信息量（为零）。下图：杰克同奶奶的交谈有更多的信息量（David Moser绘制）
1701065573
1701065574
香农对信息量的定义与玻尔兹曼对熵更一般化的定义几乎一样。在1948年的经典文章中，香农用信息源的熵定义信息量（这个熵的概念通常被称为香农熵，以区别于玻尔兹曼给出的熵的定义）。
1701065575
1701065576
人们有时候将香农的信息量定义描述为接收者在接收信息时体验到的“平均惊奇度”，其中“惊奇”意指接收者对于发送源将要传送的信息的“不确定度”。奶奶对杰克所说的肯定会比对尼可所说的更觉得惊奇，因为她完全知道尼可会说什么，却不那么容易知道杰克会说什么。因此杰克所说的给她的平均“信息量”要比尼可说的多。
1701065577
1701065578
总体上，根据香农的理论，信息可以是通信的任何单位，可以是一个字母、一个词、一句话，甚至是一个比特（0或1）。发送源的熵（信息量）用信息的可能性定义，而与信息的“意义”无关。
1701065579
1701065580
香农的结果在许多领域都有应用。最广为人知的应用就是编码理论，研究数据压缩问题和可靠传输的编码方法。编码理论对电子通信的所有领域几乎都有影响：移动电话、计算机网络、全球定位系统，等等。
1701065581
1701065582
信息论也是密码学和新兴的生物信息学的基础，生物信息学通过分析基因序列的模式测量熵等信息论度量。信息论也被应用到语言和音乐的分析，以及心理学、统计推断和人工智能等领域。虽然信息论受到热力学和统计力学熵的概念启发，信息论对物理学的各领域是否有反向影响还有争议。1961年，通信工程师和作家皮尔斯（John Pierce）开玩笑说：“让通信理论和物理学联姻的努力 [48] 有趣却没什么结果。”一些物理学家认同他的观点。不过，一些基于香农信息论的物理学新思路（例如量子信息论和信息物理学）正不断发展。
1701065583
1701065584
在后面你会看到，熵、信息量、交互信息、信息动力学等信息论中的思想在对复杂性概念的定义和对各种类型复杂系统的刻画中扮演了重要而富有争议的角色。
1701065585
1701065586
复杂 [:1701064735]
1701065587
第4章 计算
1701065588
1701065589
Quo facto， [49] quando orientur controversiae, non magis disputatione opus erit inter duos philosophos, quam inter duos Computistas.Sufficiet enim calamos in manus sumere sedereque ad abacos, et sibi mutuo dicere：Calculemus！（如果产生了争议，哲学家们用不着像会计师一样相互争执，他们只需要掏出纸和笔，然后说：来，演算一下。）
1701065590
1701065591
——莱布尼茨（转译自罗素译文）
1701065592
1701065593
在普通人眼里，计算就是计算机做的事情，电子表格、文档处理、电子邮件，诸如此类。计算机在人们脑海里就是台式电脑或笔记本，里面有电子电路，一般都带有显示器和鼠标，以前还流行用真空管。对于我们自己的大脑，我们也模糊地觉得有点像计算机，有逻辑演算、记忆存储和输入输出。
1701065594
1701065595
不过如果你读复杂系统方面的学术文献，你会发现计算这个词的用法蛮奇怪：“细胞和组织中的计算” [50] ；“免疫系统的计算” [51] ；“市场的分布式计算的本质和局限” [52] ；“植物中的涌现计算”。 [53] 这样的例子数不胜数。
1701065596
1701065597
自从计算机诞生以来，计算的概念已经走过了很长一段时间，现在许多科学家都将计算视为自然界中很普遍的现象。细胞、组织、植物、免疫系统和金融市场显然和计算机的运作方式不一样，那么他们说的计算到底是什么呢？他们又为什么要这样说呢？
1701065598
1701065599
在第12章我们会讨论这些问题，在此之前我们先了解一下计算思想的历史以及科学家用来理解自然界复杂系统的计算概念的基础。
1701065600
1701065601
复杂 [:1701064736]
1701065602
什么是计算？什么可以计算