第3章

Great Principles of Computing

信　　息

通信的内容语义与通信工程无关。

——Claude E. Shannon

软件并不只是交互设备，更生成了一个用户生活空间。

——Terry Winograd

自从数学家、通信工程师克劳德·香农（Claude E. Shannon）在20世纪40年代发现信息论以来，关于信息的研究迅速发展。信息论中的一个关键准则就是信息和含义是有区别的，这就使得机器可以忽略含义而去处理信息本身。然而，整个通信和计算的目的是传达并产生有含义的结果，这又将如何实现呢？

软件设计师、科学家和消费者都希望软件能够生成虚拟世界、社交网络、音乐、新发现、财务预测、情书和令人激动的图片等，甚至更多。例如，一只股票的报价表在财务外行看来可能是数字乱码，而对于专业投资者来说却有着极大的价值。当所研究的基本对象具有一定主观性时，我们又该如何界定信息科学呢？

这些问题看起来有些自相矛盾，因为信息论认为含义和计算机器无关——这似乎和人们使用计算系统的经验是矛盾的。此外，在很多人看来信息的概念似乎又是模糊和抽象的，难以理解信息系统实际是如何工作的。这一章的目的就是说明信息是非常真实的，是以一种物理可见的模式存在的（见图3.1）。我们调研了信息论中必然会提到的有关表示和传输信息的概念、信息论如何与可计算性理论相结合、信息论的局限又在何处。经典的信息论无法解释信息的含义以及新信息的产生，而这个调研则说明了其中的原因。我们通过描述一个含义保留变换的模型来解决这个明显的悖论。

信息的表示

人类在通信时是非常灵活的。这里有四个例子，其中前两个例子阐明了什么是显式含义：

1）当我们指向某个物体并告诉朋友这个物体的含义时，这个物体就“携带”了信息，因为从现在开始我们的朋友无论何时看到这个物体，这个含义都会在大脑中触发。

2）当我们发现某些现象模式重复出现时，就会为这样的重现模式命名。当我们再次看到这样的模式出现时，便可以预测结果。因此，这个模式就携带了可预知结果的信息。科学的目的就是发现自然界中重现的现象，而工程的目的就是将这些重复的模式转变为可利用的技术。

接下来的两个例子说明了什么是隐式含义：

3）社会群体会定义一些重现方式来交流信息。例如，很多司机将要进入高速公路时，会一边缓慢地靠近高速通道一边开启方向灯，但并没有成文的规定要求他们这样做。

4）人们日常生活中的很多习惯和惯例是没有命名但携带信息的。例如，在大多数文化中，“过来”的手势传递的就是让别人靠近你的信息。

科学家和工程师的工作就是构建技术来处理显式的信息，也就是建立信息的物理表示与预期含义的关联，如使用电磁信号对人的声音进行编码。这样，我们通过声明表示与含义之间关联的方式来产生信息，然后通过在存储器中存储这些表示方式并且用不同的变换规则来处理这些信息。

千百年来，社会学家和哲学家努力探索隐式的信息，通常很少有一致的看法。而工程师对于显式信息的处理则要简单许多。

人工智能试图跨越显式信息和隐式信息的边界，工程师正在寻找既能识别隐式信息又易于人类理解的信息表示方式。

无论是显式还是隐式的信息，这些信息的存在都建立于人类认知的一致。我们理解某种表示的含义，因为要么有人直接告诉我们如何解释它，要么我们间接通过经验学习到。

计算机和通信工程师将信息编码成电磁信号进行传输。例如麦克风将人的声音转变为电信号，然后通过一个磁盘记录这个信号的副本，最后扩音器将这个磁盘中的信号转变为声波。无线发射机将声音信号叠加在射频信号中，通过射频的幅度来表达这个信号，而接收机只要减去原本的射频信号就可以提取出声音信号。工程师对于如何编码信息表示方式及其含义必须准确一致，否则这套物理系统就会出错。

计算机和通信工程师使用比特（二进制数字）作为信息的基本单位。香农在20世纪40年代中期引入了“比特”，那时是计算机时代的初期。尽管使用十进制来构造的硬件元件也可以使用，并且早期也有一些计算机使用这些硬件，然而采用二进制元件因更加可靠而逐渐变成行业标准。香农发现二进制计算电路的功能可以用逻辑公式来表示，该公式中只包含“真”或“假”两种变量。因此，比特模式可以表示计算机电路。电路处理的数字就是这些二进制数字，也就是电路表示的数字本身（见图3.2）。自20世纪50年代以来，计算机完全变成了二进制，无论是逻辑电路还是其数据存储。

图3.2　儿童使用卡片来快速学习二进制数字。上图：每张卡片都比其右边的卡片多一倍的点数。4个儿童列成一排，引导他们通过举起卡片来表示不同的数字。下图：当第一个和第四个儿童举起卡片而第二、三个儿童藏起卡片时，数字9出现了。通过这种方式，儿童很容易掌握二进制。由于任何信号都可以数字化为二进制数字，任何文本文件也可以被编码成二进制数字，因此位成为了信息表示和量化的通用方式（由Tim Bell和Mike ellows提供，csunplugged.org/videos）

香农还证明了实际上大部分通信系统中的连续信号也可以数字化，而数字化引起的一些微不足道的误差完全可以忽略，稍后将简要说明。

所有的数据形式，包括数字、信号、逻辑公式、文本等，都可以表示成位模式，位成为衡量信息量的标准单位。现代词语中的“24位颜色”“100MB通信”“32位电脑”和“256位密钥”等都包含位的概念。在20世纪60年代，计算机制造商开始使用“字节”（即一组8位信息）来表示ASCII扩展码中的单个字母、数字或标点符号。后来，计算机处理的数据呈指数增长，于是人们开始使用新的希腊文前缀来命名这些数据（见表3.1）。其中每一个前缀都表示前一项前缀的1000倍（或1024倍，210）。在20世纪60年代，磁盘和内存容量通常用千字节来衡量，到了80年代，便用千兆字节来衡量，而那时的NASA（美国国家航空航天局）却一直苦恼于如何存储每日卫星接收到的1TB的数据量。到了2014年，“大数据”用于描述PB级字节的数据量，同时每年因特网的数据量都超过了1ZB字节。思科公司（2012）预测网络规模和数据将持续以指数形式增长。

通信系统

通信系统是最简单的信息系统，在1948年一篇名为《通信的数学理论》的文章中，香农提出了通信系统的第一个理论模型（Shannon 1948）（见图3.3）。其本质是如下过程：消息源发送一条消息，编码器按照编码本规定为这条信息生成一个独有的信号；信道作为中间媒介从源到端运载这个信号；接收端的解码器使用同样的编码本将这个信号转换成初始形式——消息就到达接收处了。香农的模型适用于任何使用编码、解码、传输、存储或是查询信号数据的系统，甚至可以作为科学发现的模型：将自然界看作现象（消息）的源头，而传输媒介（即通道）就是探索的过程（Dretske 1981）。

 

图3.3　克劳德·香农（1916—2001）描述了一个信息系统模型，它是当今信息论的基石。消息源代表所有可能要发送的消息的集合，信道是存储和运载信号的媒介，编码是将消息转换为信号，解码是将信号还原为消息，编码本包含了消息与信号互相转换的规则，噪声是指任何改变信号的事物

噪声是通信模型中的一个重要元素。任何在传输通道中改变信号，从而导致解码出错误消息的干扰都是噪声。通信技术中噪声的例子比比皆是：雾气和黑暗干扰了船只之间的信号通信；电报站之间过长的距离减弱了信号的强度；雷电干扰了调频广播的传输；DVD上的划痕会导致读取失败；环境的声音淹没了演讲的声音。

值得注意的是，在通信系统中，编码和加密是不一样的。加密是一个额外的步骤，在消息到达编码器之前将消息转换成密文，这样只有拥有密钥的接收器才能够读取消息。在这种情况下，通信系统的工作就是将密文准确地传输给接收方，如果接收方具有密钥则可以进行解密。

正如前文所提到的，香农将他的数学模型在二进制位上进行标准化，他认为所有的信号都能够用二进制位表示，这一过程在字面上被称为数字化，即将模拟信号转变为数字信号。数字化并不是生成信息的一个完全拷贝，而是一种近似化过程，因为其常常会丢失一些信息。显而易见的例子有许多，如物体边缘参差不齐的像素化照片，同时也有一些情形是非常微妙不那么直观的。物理现象中的定量分析，比如火星探测器的轨道位置，实际上不能通过计算机的有限运算进行精确表达。舍入误差会随着计算步骤而逐渐累加，导致整个计算的精确度出现问题，使火星着陆器面临危险。更糟糕的是，一些计算步骤会放大错误。如两个几乎相等的数可以认为它们的差近似为零，在用这个近似的差除另一个数时会导致严重错误。数学软件的设计师设计了很多巧妙的技术，来防止这些数字化错误破坏计算结果。

Harry Nyquist可谓当代的香农，他指出了上述普遍规律中的一个重要例外：通信系统可以免受数字化错误的影响（Nyquist 1928）。每一个连续、带宽有限的信号都可以无损地数字化，只要用至于两倍于最高频率的采样率进行采样。例如音频光盘（CD），为了使得质量没有明显损失，要每秒记录44?100（44.1千赫）个采样点，因为几乎没人能听到高于22?000赫兹的声音。

香农认为，由于我们可以对任何信号进行数字采样，同时也由于真实的通信系统具有有限的带宽，那么将通信模型限制为二进制序列，不会有任何损失。这不但简化了数学运算，而且使得这一结论适用于所有实际信道。

作为一个实例，一段简单的编码就可以说明通信模型的各种特性。假设一个消息源只传输消息的1/4，我们把完整的消息定为A、B、C、D，为这些字母分配2位的编码：

A：11

B：10

C：01

D：00

只能表示四种消息的编码在自然界中并不少见，我们细胞中的DNA序列就是一种只使用四个字母的自然消息源——G、A、T和C，它们是DNA中四种核苷酸的首字母。

如果消息源想传输序列“CAB”，那么就在信道中传输“011110”这个位序列，接收端会逆向这个过程，即在编码本中查找每一对位码然后输出对应的字母。

在任何关于编码的讨论中，我们都需要在编码长度（码字的位长）和信道抗扰能力间做出权衡。短的编码更高效、传输更快并且占用较小的存储空间，然而短编码非常容易受到噪声的干扰，信道中仅仅一位的改变就会将码字完全改变。例如，如果信道将A的第一个位编码变为0，接收端就会收到01，然后解码成C而不是A。其中一个解决方案就是使用奇偶校验位来提示接收端是否收到错误信息，当原编码中有偶数个1时，奇偶校验位为偶数，反之则为奇数。下述编码就是在原始编码中添加第3位为奇偶校验：

A：110

B：101

C：011

D：000

现在信道噪声将A的第一位编码变成0后，接收端收到010时，会发现编码错误，因为010这个编码是无效编码。概括来说，1位的错误会导致1的数量变为奇数，从而标识这是一个未编码的模式。

然而，单一的奇偶校验位并不能标识出哪一位被改变了。上例中，接收端知道010是一个无效的编码，但是并不知道这三个编码（A、C或者D）中的哪一个被这个位错误改变了。通过添加冗余的编码，解码器不仅可以检测是否有错误编码，还可以定位具体受影响的消息位。试想下面的例子，在原来编码的基础上添加了3个位：

A：11111

B：10010

C：01001

D：00100

这个编码满足如下准则：加上额外的编码位，每一个码字都与别的所有码字至少有3位不同。若有1位发生错误，接收端收到编码后会发现这个错误编码与正确编码只有1位不同，但是与其他的字母编码却有2位甚至更多的不同。这样解码器就可以检测并修正只有1位发生错误的编码情况。

通信工程师理查德·海明（Richard Hamming）在1950年首先提出码字之间的距离计算方式。两个码字之间的距离就是不同位码的个数，这就是后来有名的“海明距离”。海明指出，若要纠正k个字符，编码就必须包含足够的位使得码字之间的最小距离至少为2k + 1。他也发明了一系列编码，也就是现在的海明码。海明码在2k - 1位的码字中嵌入k个校验码，然后使用一种简单的方法来构造电路用以将受损的比特位转换为原来的编码值。最有名的一种海明编码是（7，4）编码，在4个数据位中嵌入3个校验位，构成7位的编码。在计算机处理器和存储器之间传输数据时，海明码被广泛用于纠错。

当噪声在码位上随机分布时，海明码能够正常工作。然而，在某些信号中噪声可能会爆发性地出现，比如日晕会影响某些深空信号数秒，光碟上的划痕会损坏一系列邻近的凹点，这些噪声被称为突发错误。另一种类型的编码——Reed-Solomon码便是用于检测和消除突发错误的。它的数学计算更加复杂，但是也和海明码一样很容易用高速数字电路实现。

不同于信号，位并没有实际物理意义。1位可以表示可察的任何两种属性之一。比如，工程师可能让“1”代表激光束在DVD表面某点的反射，而“0”则代表没有反射；或者“1”代表晶体管的输出是5V，而“0”则可能代表输出是3V；或者“1”代表一特定频率（比如400Hz）出现在一段音乐录音中，而“0”则代表不是该频率。位是一种抽象表达，用来声明我们想让系统做什么。工程师将这些物理的“东西”（材料）进行组装，用以完成所定义的功能。

物理系统中的信息总是要由物理状态来表达，而读写和变换这些信息也需要花费时间和精力，因此通信和计算从来都逃脱不了物理世界的限制。计算机芯片工程师知道蓄热和尺寸大小（芯片上所有电路元件的平均尺寸）等是影响他们能把电路做成多小的实际限制所在。同时每一个操作的时间消耗量则限制了可用时间内可计算的指令数。尽管新的算法在常规难题优化上有极大的改善，但计算量极大的一些问题仍然非常棘手，因为其物理运算所需要的时间大大超出我们的可等待范围。例如，在目前广泛应用的RSA加密系统中，为了寻找构成600位密钥的两个因子，即使利用目前最快的计算机也需要几百年的时间。

这些年，存储和计算能力呈指数增长。在香农发表其文章的同一年，在同一个地方——贝尔实验室，电子计算机就开始使用新发明的晶体管来取代真空管。电路设计师能够压缩晶体管的大小，每18～24个月的时间就能够无额外费用地将接近两倍的晶体管放在同样大小的物理空间。这种压缩体积的过程已持续了50年，使得每10年就有了100倍计算能力的增加，这个趋势就是广为人知的摩尔定律。英特尔的创始人之一——戈登·摩尔（Gordon Moore）在他1965年的论文中首次描述了摩尔定律（Moore 1965）。

摩尔定律带给人们两种效应和影响。一个是惊人的计算能力，这对于20世纪40年代的计算科学先驱们来说如魔法一般；另一个是正如James Gleick（2011）所称的如洪水般的信息。第一种影响——每一个传输和存储信息的更小物理机制，都会导致第二种影响——信息的极大丰富。人们被巨量的信息淹没，无法消化信息，变得不知所措。

庞大的计算能力导致了一个流行的错觉，那就是计算机所操作的是位而非原子，因此计算结构在尺寸和能量上没有物理限制（Negroponte 1996）。从物理的角度来看，这个概念是完全错误的。因为抽象的位必须依靠物理介质来记录，而且机器要通过介质来获取位信息。这个记录的过程将我们带回了原子世界：没有它们我们无法完成计算。我们可以在极小的物理元件上进行快速的计算、传输和存储，但从来无法消除它们的时间和功耗。

信息的测量

香农设计了一个用于测量信息源中所含信息的方法，因为他想知道信息源中最短码的长度。编码的位数量并不能作为一个衡量标准，正如我们在上文中所看到的，单个信息源可以用任意数量的不同编码来表示。他的结论是一个好的衡量标准应该是消息集合中最短编码的长度，若编码再短一些则无法传输消息源的所有信息。

他认为衡量信息不应该依赖人类所观察到的编码的含义，而应该忽略信息的上下文，寻求编码、传输和解码的固定工作机制。邮政服务遵循相似的准则：他们的分发和传输系统从不依赖于所运输的信封中的内容。香农非凡的洞察力表现在“将信息的接收等同于不确定性的减少”。他定义信息为判断信息源正在传送哪个消息所需要回答的是非（yes-no）问题的最小数量。我们越了解某个信息源可能会发送什么消息，那么看到这条消息时所获得的信息量就越少。

假设你知道某人将会只回答一个是非问题，但提前无法得知回答者的答案，那么回答者通过回答解决了你的不确定性。香农认为回答者只给了你一位的信息（1或0），即从两种可能答案中选择其中一个。当答案有两个以上时，需要更多的位来区分发送的消息。

假设我们想在电话簿中找到含有某个朋友名字的那一页，那么需要多少位来对页数进行编码呢？一个聪明的方法回答了这个问题：我们从中间打开电话簿，然后询问哪一半含有朋友的名字（由于使用字母顺序编写电话簿，这个问题就很容易回答）。然后我们把含有名字的那一半电话簿再分割成两半，询问同样的问题。重复这个步骤，直到只剩一页，这个朋友的名字就应该在那一页上。这个重复的问题（“哪一半”或者说“是否在左边一半”）让我们快速定位。对于一本有512页的电话簿，第一个问题留下了256页来搜索，第二个问题留下128页，然后64，32，16，8，4，2，最后是1。需要9个“哪一半”问题来寻找包含名字的那一页。因此，当找到包含朋友名字的那一页时，我们获取了9位的信息量。

在构建编码时，人们需要思考消息的发生概率。塞缪尔·莫斯（Samuel Morse）发明了莫斯密码，并将之应用于19世纪30年代他参与发明的电报中。他分配最短的编码（单个点）来表示字母e，因为e是在英文中使用最频繁的字母（大约12%）。他将最长的编码分配给字母j，因为j是最少使用的字母之一（约0.15%）。这样的分配减少了传输的平均长度。图3.4说明了用以识别一个消息的问题可以用来定义信息编码，以及关于消息发生概率的先验知识会减少编码量。

假设我们有一长度为Li、概率为Pi的码字集合。那么编码的平均长度就是

对于图3.4中的编码，公式计算出第一种编码的平均长度是2位，而第二种编码的平均长度是1.75位。

在最优编码中，码字的长度即最小的L是多少呢？香农在他1948年论文的附录中回答了这个问题。他表示最优码字的长度是以2为底的码字出现概率的对数的相反数，即-log2Pi。因此，最优编码的平均长度是

 

这个公式和热力学的熵公式具有同样的形式，也有着相似的解释。熵是衡量系统状态的混乱程度或是不确定性的指标。一个系统的状态越混乱，熵就越高。最大的混乱度发生在所有的状态都有同等发生概率的情况下，最大的有序度则发生在某一种状态非常确定而其他的状态都绝不会发生的情况下。

香农认为熵是信息源中固有信息的衡量标准。一个信息源由一组可能的消息和消息发生的概率构成。熵只取决于消息的概率而不是它们的编码，熵可以确定最短可能编码的平均长度。任何更短的编码都将导致混淆从而无法得到唯一的解码结果。如下面的例子：

A：1

B：0

C：01

D：10

 

图3.4　香农将一个消息中的信息量定义为将该消息从消息源中筛选出来需要回答的是非问题数，这些问题是用来减少“哪个是被发送消息”的不确定性的。试想，如果我们要从四个人中发现被某任务选中的人，则可以使用一个简单的决策树（上图），我们问：“是Alice或者Bob吗？”如果答案为是，则决策选择左边的子树。再问一个问题“是Alice吗？”，答案就揭晓了。每个个体的编码就是指向他/她的是非问题答案的路径。如果知道某个个体被选中的概率（下图括号里的数字），那么我们可以构造一个等级决策树，从而使得编码长度不等。例如，如果Alice是最有可能被选中的，我们就把编码1分配给他。Bob是下一个最有可能的，则分配编码为01，然后是Charlie和Diana，他们有相同的选中概率，则都被编码为3位

如果以上这些消息出现的概率分别是0.5、0.25、0.125和0.125，平均编码长度就是1.25位。然而，接收方对于1001代表ABBA，ABC，DBA还是DC却无法分辨。这条消息的熵（根据上面的公式计算得出）是H = 1.75，界定了编码是否能够解析的阈值。这条编码的平均长度是1.25位，低于此阈值，所以编码无法解析。

哈夫曼（Huffman）编码是一种快速在熵阈值内进行位编码的方法（图3.5）。

图3.5　1951年麻省理工学院的大卫·哈夫曼（David Huffman）设计了一套编码算法，在已知消息概率的情况下，此编码算法能够使得平均编码长度最小。该算法首先将每个消息都视为一棵单独的树。然后不断地将两棵具有最小概率的树进行合并，合并后树的概率为两棵子树的概率和。对于一个具有n条消息的编码，需要n次合并，形成最后的树。在本例中，Charlie和Diana首先合并，然后他们合并后的树和Bob合并，最后和Alice合并。树中的每条路径定义了每一条消息的二进制位编码。哈夫曼的方法所生成的编码能够将平均编码长度控制在熵阈值范围内。若所有的消息具有相等的概率，则生成图3.3前面所示的编码，若概率不相等，则生成后面这种编码

从另外一个角度来看，熵的阈值定义了信道是否可信。如果消息源每隔T秒传送一则新消息，最短编码的平均长度是H，那么这个消息源就产生了每秒传送H / T位的需求。如果信道的带宽是H / T位每秒或者更高，那么发送方所传送的所有位都能够到达接收端。若信道的带宽小于H /T位每秒，某些位就可能丢失，接收端就无法恢复原始消息。

文件压缩是信息论的一个重要应用，因为其可以减少存储空间和缩短传输时间。在大部分计算机程序中都使用标准码来表示文本，包括传统的固定长度编码ASCII和现代的变长编码Unicode。这两种情况下每个字母都使用了相同长度的编码，因而，通过寻找重复模式并基于文件上下文用更短的编码代替这些模式，文本文件可被大幅压缩。例如，一个包含很多字母“e”的文件，可以用新的更短小的编码替换它的编码来压缩文件。新的编码取决于“e”在文件中的出现频率——在“e”频繁出现的文件中，这个编码可能是3位，而在“e”不那么频繁出现的文件中，这个编码可能是5位。文件压缩算法会生成一个新编码到原始编码的转换表。“.zip”和“.rar”格式就采用了这种策略。这种压缩策略的设计也不会将信息“压缩”至低于熵的阈值。因为若是低于阈值，则无法保证完全恢复原始信息，这种策略被称为无损压缩。

另一种策略是有损压缩。有损压缩方法具有更大的压缩率，但无法完全恢复原始文件。例如，MP3音频压缩通过丢弃绝大部分人听不到的频率来压缩音频，其压缩率大约为10，但是没法恢复丢弃的频率。JPEG图像压缩舍弃了部分人眼基本会忽略的颜色信息位，当然也没法恢复这些原始的图像位。这些压缩方案使得DVD、在线电影和唱片等能够以更低廉的价格卖给消费者。这些方法在感知质量上的小小损失，对于减少文件大小而言通常被认为是一种很好的折中。

信息的转换

一个单纯的通信系统只是简单地将信息从一处传输到另一处，但是计算机会做更多的工作，即转换信息。转换就带来了更多可能，其中最显著的产品就是新信息的出现。简单的转换包括将一个数平方、计算π至指定小数位数、对一列数字按照升序排列，每一次转换都是将一种信息模式作为输入，并创建一种信息模式作为输出。

因为二进制模式可以被解析为数，所以一次转换在数学上看来就像是一个输入数到输出数的映射函数。能够被机器计算的函数被称为可计算函数。图灵和他同时代的人们用这个概念来定义计算。图灵表示一个简单的抽象计算机——图灵机，足以实现任何可计算的函数（Turing 1937）。图灵机遵循一个非常简单的指令程序来实现这些转换。因为每一条指令显然可以被机器实现，那么计算机转换二进制的时候并不考虑它们的含义。这类似于香农所强调的，信道可以被设计得完全可靠并且不考虑传输信息的含义。

当我们稍微深入了解机器如何转换输入时，就会发现程序设计的一个重要方面，称之为含义保留（meaning-preserving）。设想两个数a和b相加，两个数相加意味着什么呢？这意味着我们要遵循一系列加法算法的步骤。这个步骤包括连续对a和b的两个对应的数字位相加，然后将其进位结果传递到更高位。我们对于属于｛0，1，2，…，9｝中的数字对有明确的加法规则，并且会产生进位0或者1。当为这个算法设计程序时，我们需要注意让每条指令都能够产生正确的加法结果。如果成功了，我们可以相信机器能够正确做出两个数的加法。若失败了，我们会说机器坏了。

换句话说，设计过程本身就是将我们脑中的加法过程转换为机器执行加法的指令模式，加法的含义就存在于机器和其算法的设计之中。

这对于任何其他的可计算函数也是适用的。我们把大脑中想法的具体含义转换成可计算的函数，将它输出到程序中，从而控制机器实现这个想法。这个过程也就是将具有我们想法含义的函数转变为对机器的设计。

从这个角度看，机器和通信系统不考虑二进制数据含义进行信息处理的概念有些站不住脚。算法和机器被工程师和程序员植入了含义，我们设计机器从而使得每个计算步骤和输出都是我们想要的含义，假设输入也具有我们想要的含义。仔细精确的设计就是为了不用担心机器曲解我们想要表达的含义。

计算机将计算函数和信道结合，一个信道将输入送到执行计算函数的机器，另一个信道将输出送到目的地。这种情况下信道和计算机似乎只完成了运输和操作信息位的工作。然而从人类的角度来看，计算带来了新的信息，无论计算机输出比输入更多还是更少的信息。例如，前文提到的一个计算π的函数，在输入一个三位数“900”时能生成900位的π的值，输出扩展了300倍的信息量。一个排序函数的输出和输入具有同样的位数，但是具有不同的顺序。一个平均函数能够计算出少量的数字来代表大量数据的平均值。

数字表示和机器操作都依赖于物理过程，每个机器操作都需要花费少量的时间和功耗。有些我们希望计算的函数需要花费太多的步骤以至于在有生之年无法等到机器返回结果。计算所需的物理处理严重限制了我们能够计算的内容。

计算的逻辑也会带来限制，其中最有名的就是我们想计算但无法计算的函数。图灵在1936年提到了停机问题——不存在一个程序，可以检查任何程序并且判断其在给定输入上是否包含无限循环。一个现在的实例是恶意软件检测，即不存在一个程序能够检测任意给定程序是否嵌入了恶意软件检测程序。我们在第6章检验计算的物理和逻辑局限性的时候，还会再回到这个话题。

即使当我们将注意力限制在可以计算并且很快返回有用结果的函数，也可以发现一些有趣的问题。当一个函数在计算我们没有见过的数据位时，这些数据位是新的信息吗（见图3.6）？或者它们只是现有信息的结果？DNA包含信息吗？很多生物学家认为包含。若DNA是一种信息，那它的信息源和接收端又是什么呢？如果对DNA解码，我们能得到什么信息呢？解码的DNA可以用来寻找治愈遗传疾病的治疗方案，也可以识别犯罪现场的行为人。将DNA与数据库匹配仅仅揭示了现有的信息还是生成了新的信息呢？经典的信息论无法回答这样的问题。

图3.6　哈勃太空望远镜的集光传感器阵列编码TB级数据并传输到地球，这些数据再被处理成为图像。计算理论将这个图像处理过程描述为方程Y = F（X），其中输入数据X在函数计算后产生输出图像Y。这个机器实现的功能（将信号发给它，它又生成信号）不依赖于望远镜传输的信息的含义，然而人类看到Y输出的是一张美丽的图片——船底座星云的实际展示（图片来源：NASA）

交互系统

许多计算机程序是交互系统：接收新的输入，在很多点上生成新的输出，除非被干预或者程序崩溃，它们可能会无休止地做这些工作。交互系统无处不在，每一个操作系统都是一个交互系统，比如一辆汽车的GPS系统、Facebook、一个在线商家的服务器，或者互联网的域名解析系统。互联网本身也是一个全球的数据交换和协调行动的交互系统。交互系统的一个显著特征就是持续不断地运行，同时没有程序结束。相反，函数系统在计算出答案后，程序结束运行。

多年来，计算机科学家们激烈地争论交互计算是否比函数计算更强大（Goldin et al. 2010）。近年来专家们一致同意交互式计算更加强大。作为当代的难题，如何有语义地为数字图像打标签解释了这个原因，因为这个问题的解决方法依赖于交互：游戏构造了人机交互来实现人和机器都无法单独完成的功能（见图3.7）。交互系统所生成的输出是已知机器无法做到的。

图3.7　在2004年卡耐基梅隆大学（CMU）的Luis von Ahn 和 Laura Dabbish发表的一篇论文中，描述了一个新颖的电脑游戏ESP。在游戏中，玩家被两两分组，给予同一张图片并要求用单词来描述这张图片的内容，游戏的目标是找到同伴（不知道也看不到）也使用过的相同单词。公共的单词就成为这张图片被搜索时的新标签。游戏将人和电脑组队去计算一个图片识别函数，没有人知道如何单独使用计算机进行计算。像其他函数一样，这个函数也转换信息，不过这个含义现在是由玩家来交互地完成

解决悖论

在上面的讨论中，我们注意到一些关于信息的看似矛盾的结论：

1）工程师设计的通信系统能够在不理解信息含义的情况下运行，那么人类信息接收者如何收到含义呢？

2）工程师所设计的计算机系统能够在不了解程序与二进制模式数据含义的情况下转换信息，那么这些系统如何生成新的信息呢？

3）程序员设计的程序能够在对其数据无知的情况下运行，那么人类用户是基于什么有意义地解释程序的输出呢？

4）建立连接（如放置一个网页链接[Berners-Lee 2000]）会产生新的信息吗？

5）如果设计一个计算机程序来生成欺骗性信息，那它的输出还算是信息吗？

6）加密消息中的信息又在哪里？

7）如果一个计算机程序完成了新的科学发现，那么它是创造了新的信息还是仅仅传递了人类不了解的已知信息呢？

信息学常见的理论和观点都不能回答这些问题。比如，我们说符号“携带”信息，这只会引出新的问题，携带的信息在哪里？如何嵌入和提取信息？另一个例子是嵌入在社会传统中的含义通过机器的输出所触发，这种含义只会有助于引发第三个问题。还有另一个例子是“标记对象”模型（Rocchi 2012），该模型将标记和含义将结合，但仅对显式信息有效。

含义保留的变换解决了所有的悖论。人们有意设计出软件程序来支持实践、建立连接、隐藏信息或者寻找新的信息，这些含义是设计师设计机器反馈的所有结果，因此人类用户会认为这是预期的反应。当某个机器没有给出预期的行为时，设计师和用户都会认为它损坏了。

这些悖论总会在初期显现，因为计算机科学家总希望机器拟人化，比如，我们说一个机器能够理解它的输入，或者机器对于输出很有创造性。而当别人深入了解我们的程序和机器时，他们只能看到机械步骤。这些步骤中他们看不到“理解”甚至“创造性”。理解和含义来源于设计者，是他们设计了机器的模式并在使用时产生预期的含义。

信息和发现

当我们说计算机发现了新的模式时我们想说明什么呢？设想一个程序能够发现数据的趋势，首先提供一组在以往性能实验中观察到的输入输出对（x，y）给程序，然后利用统计回归，程序找到了最好的参数a和b表示一条直线来拟合这个数据：y = ax + b，程序的输出是直线的常规表达。这个输出对于了解如何利用直线进行预测的用户是有意义的。很容易设计另一个程序来使用具有参数a和b的直线来预测y，而y是由新的输入x生成的。

这就是一个设计师使用数学知识从一系列数据中计算最佳拟合参数的过程，计算中的步骤是机械的，输出对于那些了解数据中直线趋势模型的人们是有意义的。这些意义来源于设计师，而不是数据的处理。

对于不了解数据中直线模型趋势的人，也就不知道输出的含义。但是这并不意味着输出的含义是主观的，只意味着设计师没有打算让程序对这些用户产生任何意义。

在20世纪80年代，研究者开始使用强大的计算机筛选大数据集来试图发现一些模式。他们使用贝叶斯（Bayesian）推理（这是一个复杂的数据分析方法）来推算最有可能产生数据的一系列条件。贝叶斯推理基于贝叶斯条件概率统计公式：

 

它说明的是给定证据E，假设H的概率就是：给定假设H后该证据E的概率，乘以假设H的概率，再除以证据E的概率。图3.8给出了一个简单的示例，医生已知病人头疼，试图诊断他是否患有流感。

这种情况下的发现是一个新的假设。程序能够生成一系列假设，然后根据手中已知的情况，按照贝叶斯定律计算每一个假设的概率，把其中最有可能的假设作为这个“发现”。

在这种情况下，设计者结合贝叶斯定律和搜索方法，在给定数据下找到最大可能的假设。这个程序的输出就是那些明白假设和数据“含义”的用户所预期的，用户将决定是否将这些假设视作一个发现。

图3.8　韦恩图演示了如何利用贝叶斯定律评估一个很难判断的假设。在所有人口的集合K中包含一个子集F，代表患有流感的人，还有一个子集H，代表患有头疼的人。医生看到一个病人抱怨头疼，担心自己患上流感。根据贝叶斯定律P(F|H) = P(H|F)·P(F) / P(H)。医学数据告诉医生，患有头疼的概率P(H) = 0.4，患有流感的概率P(F) = 0.2，在患有流感的人中患有头疼的概率是P(H|F) = 2 / 3，因此P(F|H) = (2 / 3)·0.2 / 0.4 = 1 / 3，即三分之一。在没有任何信息的时候，患有流感的概率是0.2，但若已知患头疼，患有流感的概率则上升到0.33

在经典的信息论中，我们说贝叶斯推理发挥作用，是通过已知消息源的数据来决定消息源的内容。在消息通信中，香农合理假设消息源的内容为先验信息。在科学发现中，消息源中包含的一系列概率最初是未知的，推理过程使得消息和它们的概率可知。贝叶斯推理是一个自动将消息源中的观察数据转换为消息源内容的方法。

总结

自古以来，人类就开始编码信号，使其可以在不同的媒介中进行传输。在20世纪40年代，香农的信息论提出了四大准则：

每一个通信系统都可以被建模成一个噪声通道，其携带着被编码的信号，该信号表达着消息源中的消息。

消息源的熵决定了消息源最短的可解析编码的长度，哈夫曼编码是和熵一致的一种编码（信息熵小于一个比特）。

充分冗余的比特位能够添加到任意编码中，以此来克服信道中的噪声，并且能同时保证百分之百准确的接收。

利用更短的编码替换模式，文件能够被压缩到更小的尺寸。

这些原则使得通信和计算机工程师能够设计数字系统，这些系统在传输过程中不会丢失信息，并且噪声引入的错误也可以被消除。

一些不理解香农理论的企业家认为“比特而非原子”的理论能够预示一个激增的新兴经济体，但他们的梦想是不会实现的，因为真正的通信和计算系统的基础来源于将数据记录表示成物理信号和状态，而计算和传输需要消耗时间和能量。我们在计算上花费了很多能量：互联网的连接点和数据中心消耗了世界近6%的电力。我们不能寄希望于假定能通过比特而不是原子来解决棘手问题就忽略了这个问题：比特背后的原子也是很重要的。

正如摩尔定律所预示，我们存储信息的能力成指数增加，我们阐明信息含义的压力也在不断地增加，而香农信息论的定义无法解决这个问题。这看似是个悖论：系统如何在不考虑信息含义的情况下处理信息，同时还能在用户的体验中产生含义。

含义保留的变换融合了机器的无意义机制和能让机器产生含义的人类经验。程序设计师编制指令，从而能在用户群体产生预期含义的输出；每一条指令的执行，逐步将部分计算结果接近预期的输出。让我们为程序设计师这个角色鼓掌，是他们给了我们有意义的软件和硬件。

致谢

这一章改编自Peter Denning和Tim Bell的“信息悖论”（2012），其发表于《美国科学家》。