第2章 计算

什么是计算？

当你在早上启动汽车，发动机会“决定”多少汽油和空气进入气缸；随着发动机升温，油气比例发生变化。踩下油门，比例再次改变。这是怎么实现的？当你听音乐或上网时，所用的设备又是怎样的原理？所有这些事情的背后都是计算机在起作用。今天已经很难摆脱计算机的影响。计算机计算账单，无需胶卷生成照片，追踪你的喜好，预测天气。计算机是操作信息的机器，计算机科学则是研究这种活动的局限和潜力的学科。这一章我们会探讨计算的概念。我希望你能认识到计算不仅仅是计算机中发生的事情，许多物理活动都与计算密不可分。

计算机科学的基础是信息。信息可以被编码为符号，通常是向某人或某物传递意义的序列。第1章介绍了信息的一种度量：香农信息。这种度量对于一些目的很有用，比如确定存储一些你感兴趣的信息需要多少物理空间，或将其远距离传送需要多大带宽。这一章我还会介绍另一种度量——算法信息，它对计算机理论也特别有用。

理解计算的概念的一个可行途径是将所有计算都视为一个过程，过程以编码模式（通常是符号序列）为输入，经过一系列变化，最终产生输出。输出可能有输入所不具备的用途。这个大致的思想表示在图2.1中。

图2.1 计算的3个部分

这引出了几个问题：操作信息是什么意思？计算中会损失信息吗？新的信息来自哪里？计算机要能“操作信息”的必要条件是什么？要回答这些问题，我们需要一些背景知识。

我们从物理中“系统”的思想开始。系统是具有边界的某种事物。虚空不是系统；数学上的点或几何平面这类抽象思想也不是。宇宙可能是也可能不是系统，取决于其是否有边界。所有比有限宇宙小比亚原子粒子大的事物都是系统，也是更大系统的一部分。系统通常由多个部分组成，各部分之间可以有不同的组合方式。我们将组合方式称为系统的“状态”。在第1章我们看到，状态如果可以相互区分，就能够携带信息。至于信息是否有用则是另一个问题，取决于是否存在另一个系统通过与原系统的特定状态互动产生特定的变化。以开车为例，你自己是一个系统，车是另一个系统。两个系统互动。坐在驾驶席上脚踩油门踏板的你处于某个状态。脚踩下去你就变成另一个状态；这个新的状态导致汽车系统转变成一个新的更快的状态。你的某些状态就对汽车系统有意义；还有一些比如闭上一只眼睛或挥动左手则没有。在物理的世界里，意义来自系统状态的互动。如果没有互动，就没有意义。要具有意义，一个系统的特定状态必须对另外的系统有特定的影响。

在信息科学中，意义经常与表示的概念联系到一起。计算的背后有一条原理是一个状态可以表示为另一个状态。这里的状态不必是在同一个系统。举两个例子，你在键盘上敲的字可以表示为计算机里的电压和电流；人类艺术家演奏的音乐可以表示为DVD上的银点样式。当某种表示影响到了你，它就对你有意义。

计算机程序是由能导致计算机内部发生特定的状态序列并产生输出的命令组成。在计算机科学中，完成某件事的命令序列被称为算法。在其他场景中可能被称为食谱或指令。指令和算法表示完成任务的方法。大部分计算机算法都接受数据输入并产生针对某种场合的输出。数据和算法都包含信息。数据可以视为外部世界某方面的表示。这样来看，计算就是将对方法的表示（算法）作用于对世界某方面的表示（数据）产生内部表示（机器状态）的序列，并得到最终的表示（输出）。无论哪种表示，都是某个系统的物理状态，也都可以理解为信息。这可能让人感觉很抽象，但让人吃惊的是，这可以用物理设备实现，并最终解释为什么信息在许多场合中对我们如此重要。计算机就是可以呈现许多内部状态的设备。在计算机中，内部状态与输入状态互动产生新的内部状态。最终状态就是输出。

计算的现代概念已经发展了几十年。在有计算机之前，人们通过演算解数学题，数学家和哲学家则希望能用机器模拟这个过程。20世纪30年代后期，年轻的英国数学家阿兰·图灵建立了现代计算机科学的数学基础。数年后他领导一个英国团队成功破解了德军密码。图灵对第二次世界大战的贡献很重要但鲜为人知，以至于在战后很难找到工作。直到他在1954年自杀后，他对战争的贡献才被广泛认可。图灵最大的科学成就源自对人如何解算术题的仔细分析。例如用58432除以83。大部分人都可以不借助计算器通过一些简单步骤演算出结果。小学就教了这个。表2.1列出了20个步骤，只要照着做就能得到正确答案。就连我这样在小学时讨厌长除运算的人都记得这些冗长的步骤。如果你不想一行行读这张表，就不用读它。

表2.1 58432÷83的20个简单分解步骤

任何人只要遵循这些步骤就能得到正确答案。他们无需“理解”他们在做什么，也无需具有在第3、第11和第14步一猜即中的天赋。他们只需知道判断一个数比另一个数大还是小，以及做乘法和减法。如果他们不知道乘法，也可以将乘法还原成重复相加（步骤会增加）。图灵认为任何计算，无论多复杂，都能通过顺序执行极为简单的步骤解决——甚至比表2.1中的步骤还要简单。由于这些步骤很简单，不需要什么聪明才智，因此可以设计一台（不会思维的）机器来执行这些步骤。然后他展示了如何设计一台这样的机器。为了纪念他，他提出的这个想法现在被称为图灵机，所有计算机专业的学生都会学。现代计算机的设计已经有了很大变化，但仍然是基于图灵的思想。原则上，图灵机可以通过顺序执行适当的无需思维的简单步骤来解决任何可计算的问题。

第一台实用的计算机在第二次世界大战期间被建造，通过反复解数值问题计算炮弹弹道，通过系统地对数百万种可能性进行测试破译军用密码。无论具体的设计和执行计算的细节如何，所有计算机执行的都是一长串极为简单的步骤。它们的优势在于能高效准确地执行这些步骤。

表2.1给出的20个步骤就是一个算法。算法的一个显著特征是它们的逻辑结构超越了对它们进行编码的物理系统。这意味着算法的结果独立于执行算法的机器。用丹尼特的话说，无论是“在纸上、在羊皮上、在计算机里……还是在天上”，长除问题的答案都是一样的。这是因为算法可以用不同的物理媒介甚至不同的语言表示。其超越性来自符号序列可以被复制、重排、转换成其他符号形式，而不会失去信息本身的意义或逻辑结构。算法的一个重要特征是必须有结果。一系列命令如果不能产生输出就不是算法，也没有意义。

计算机接受的程序（算法）是用由顺序排列的符号组成的语言写出来的。输入符号的顺序驱使机器做特定的事情。例如，在许多计算机语言中，命令“x=3”会使得计算机将数字3存储在标号为x的存储器中，随后的命令“print x”就会使得计算机将x的内容（例如3）送到打印机或屏幕上。符号的顺序决定一切；“rpint x”或“x print”都无法让数字3出现在屏幕或打印纸上。

计算的概念不限于编码为符号序列的信息。2维和3维样式也可以被视为信息。不过，大家包括计算机专家在内都喜欢1维，因此几乎所有人造的计算机都是基于对顺序符号序列的操作。