1.3　计算机世界的问题解决之道

在计算机时代，计算机科学家和工程师不断地探索和实践，攻克了一个又一个理论和工程上的难题，从而满足了现实世界中一个又一个的需求。当然，计算机可以解决的问题是有其边界和范围的，并不是所有的问题都可以通过信息化的方式解决。但可以说，正是由于计算机科学理论和工程技术的不断进步、两者之间的相互融合和不断发展，以及这两方面取得的丰硕成果，才开创了人类的信息化时代。这个过程仍在持续，并且我们每个人都身处其中。以隐私计算为例，如前面介绍，这项技术起源于“百万富翁”问题及其理论层面的分析探讨，兴起于数据时代对数据安全的重视，目前正处于工程和技术层面的蓬勃发展阶段。隐私计算的兴起和发展就是十分典型的通过计算机解决现实问题的案例。本节就带领大家尝试像计算机科学家和工程师一样思考，看看计算机世界里解决问题的理论和工程基础。

1.3.1　从第三次数学危机说起

图灵机和计算理论是计算机科学的理论基础。这个划时代理论的缘起，可以追溯到第三次数学危机。

1874年，德国数学家Georg Cantor（康托尔）发表论文，建立了集合论。我们现在称之为康托尔集合论或朴素集合论。朴素集合论是数学领域的一个重大突破。当时，数学家们发现，从自然数与康托尔集合论出发，可以在严谨的逻辑基础上建立起整个数学大厦。被誉为欧洲数学界教皇的德国著名数学家David Hilbert（大卫·希尔伯特）甚至称赞：“没有人可以将我们从康托尔所创造的天堂中驱逐出来。”希尔伯特是一位伟大的数学家，他希望能够构造出一套基本的公理，通过这些公理和逻辑推导，可以构造出整个数学大厦。这一想法被称为希尔伯特计划。1900年，希尔伯特应邀参加在巴黎举办的第二届国际数学家大会，在大会上，希尔伯特做了题为《数学问题》的重要演讲。在这次具有历史意义的演讲中，他提出了著名的23个数学问题，指明了20世纪数学发展的方向。这23个问题中的第2个问题，算术系统的相容性，正是希尔伯特计划的重要一环，这个问题的解决，将让整个数学大厦建立在坚实的基础之上。

但是，这个基础，受到了极大的挑战。

首先是针对朴素集合论，数学家Bertrand Arthur William Russell（罗素）提出了“理发师悖论”：一个小城里的理发师宣称，他只为城里所有不为自己理发的人理发。然而，问题是理发师该为自己理发吗？如果理发师为自己理发，那么按照他的说法“只为城里所有不为自己理发的人理发”，那么他就不应该为自己理发；但如果他不为自己理发，同样按照他的说法“只为城里所有不为自己理发的人理发”，他又应该为自己理发。这个简单的悖论有一个更为严谨的等价表述，即罗素悖论，该悖论指出了朴素集合论的逻辑瑕疵。于是，数学的基础被动摇了，引发了第三次数学危机。

前面提到的希尔伯特23个问题中的第2个问题，即算术系统的相容性问题，如果得到正面的解答，就将终结这场危机。但是更为致命的打击即将来临。

希尔伯特计划的主要目标是为数学提供一个安全的理论基础，包含以下三个问题。

问题1：数学的完备性，即一个数学体系中所有的真命题，均可被证明。

问题 2：数学的一致性，即一个数学体系不会推导出矛盾的结论（例如，出现一个命题，这个命题既为真又为假）。

问题3：数学的可判定性，即存在一种算法，可以机械化地判定数学陈述的对错。

希尔伯特确信，这三个问题的答案都是肯定的。很快，前两个问题得到了解答，虽然答案并不是希尔伯特所期待的。1930年，奥地利数学家Kurt Gödel（哥德尔）证明并发表了两条定理，即哥德尔不完全性定理（或称为哥德尔不完备定理）。

定理1-1：任意一个包含一阶谓词逻辑与初等数论的形式系统，都存在一个命题，该命题在这个系统中既不能被证明为真，也不能被证明为假。

定理1-2：如果系统S含有初等数论，当S无矛盾时，它的无矛盾性不可能在S内被证明。

哥德尔不完全性定理指出任何包含了皮亚诺公理的数学系统，都不可能同时拥有完备性和一致性；任何包含了算术的数学系统，如果是自洽的，那么这个数学系统必定包含一个基于该数学系统构建的命题，但这个命题在这个数学系统内既不能被证明为真，也不能被证明为假。

简单来说，哥德尔不完全性定理否定了希尔伯特计划完成的可能性。

这场数学危机给数学界带来了许多新认识、新内容，建立了公理化集合论，也带来了革命性的变化。对于所有学习计算机科学的人来说，最重要的奠基人就要登场了，他的目标是判定问题。

1.3.2　图灵机：计算机科学的理论基石

Alan Mathison Turing（艾伦·麦席森·图灵），英国数学家、逻辑学家，被称为计算机科学之父、人工智能之父，是计算机科学领域最重要的科学家之一，计算机学界最重要的奖项就是用他的名字命名的图灵奖。

如图1-3所示，图灵在1936年发表了论文《论可计算数及其在判定问题上的应用》（On Computable Numbers，with an Application to the Entscheidungsproblem）［1］，这篇论文讨论、研究了希尔伯特的判定问题。在该论文里，图灵描述了一种可以辅助数学研究的机器，从理论上构想了一种可以执行计算的机器，这就是图灵机。

图灵机是一种抽象的机器模型，是一种十分简单但运算能力极强的计算模型，用来计算所有能想象得到的可计算函数。图灵在该论文中不仅对希尔伯特的判定问题给出了解答，更为重要的是，通用图灵机的诞生，完全改变了世界。从机械装置的角度描述，图灵机由以下几个部分组成。

（1）一条具有无限长度的纸带：纸带被分成多个相邻的单元格。每个单元格都可以写入某个有限字母表的一个符号。这个有限字母表中包含一个特殊的空白符号，以及一个或者多个其他符号。

（2）一个读/写头：读/写头可以在纸带上读/写符号，并一次将纸带向左或向右移动一个单元格。

（3）一个状态寄存器：状态寄存器用来存储图灵机的状态，这个状态是某个有限状态集中的一个。其中有一个特殊的启动状态，状态寄存器就是用它来初始化的。

（4）一个有限的指令表：指令表限定了图灵机的状态转换及动作规则。图灵机根据指令表和机器当前所处的状态，让机器依次做以下事情：擦除或写入一个符号、移动读/写头（向左或向右，或者停留在原地）、保持状态相同或进入新的状态。

通过上面的定义，图灵将计算归结为一些内容简单、含义明确的基本操作，这些基本操作非常直观地描述了计算过程：对于输入带上的一个输入字符串，图灵机从初始状态和带上最左边的字符开始，通过连续不断地扫描和执行确定的机械动作（例如，“读/写纸带单元格中的符号”“向左或向右移动一个单元格”“改变状态并写入纸带”等）来完成计算。如果在某个时刻按照规则进入终止状态，图灵机就接受输入串。在此可以看出，图灵机虽然是一个构造十分简单的机器模型，却有着十分重要的意义。

首先，图灵机给出了一个可实现的通用计算模型。上面提到的纸带、读/写头、状态寄存器、指令表等，都是十分简易的构件，在物理实现上具备极高的可行性。

其次，图灵把计算用确定性的机械操作来表示，并在论文中证明了通过上述过程，可以模拟人类所能进行的任何计算过程。依据图灵的设计和证明，上述简单构件组合而成的图灵机能完成极为复杂的计算。

上述贡献奠定了计算机科学的理论基础。

再次，图灵机的设计引入了通过“读/写符号”和“改变状态”这种简单操作进行运算的思想，并引入了存储区、寄存器、程序、控制器等概念。这些概念极大地突破了此前计算机器的设计理念，成为计算机程序设计的基础概念，至今仍深刻地影响着程序员的程序和算法设计。

可以说从图灵开始，计算机领域有了真正坚实的理论基础。

图灵证明了通用计算理论，以及计算机实现的可能性，同时图灵机的设计也给出了计算机应有的主要架构。图灵给出了计算的极限，明确了图灵机可以解决的问题、不能解决的问题。这些都划定了现代计算机可以解决问题的理论边界，这个边界本身是极有价值的。此外，图灵还进一步思考了机器智能的概念，提出了著名的“图灵测试”。这些工作使图灵赢得了“人工智能之父”的称号。图灵设计的图灵机虽然构造简单，却是人类目前可实现的计算模型中最强大的。著名的邱奇-图灵论题（Church-Turing thesis）提出，所有计算或算法都可以由一台图灵机来执行。这意味着所有的计算模型都可以被转化为图灵机这个计算模型。图灵从理论上证明了只要是计算模型能计算的问题，就能通过图灵机进行计算，因此它能模拟现代计算机的所有计算行为。

至此，理论意义上的计算机已经出现。接下来图灵机这个理论模型要形成真正物理意义上的通用计算机，就需要另一位伟大的科学家出场了。此人提出了电子计算机使用二进制数制系统和存储程序的概念，他就是冯·诺依曼。

1.3.3　冯·诺依曼结构：计算机工程发展的坚实基础

冯·诺依曼是“现代计算机之父”“博弈论之父”，也是20世纪最杰出的数学家之一。他一生的辉煌成就无数，在统计学、核武器设计、流体力学、博弈论和计算机结构学等领域均有许多重要的贡献和成果，是一位全才式的天才科学家。

1945年，冯·诺依曼在First Draft of a Report on the EDVAC［2］一文中，提出了“存储程序”的计算机设计思想，并提出了冯·诺依曼结构，这也成为现代计算机发展所遵循的基本结构形式。

冯·诺依曼提出计算机的数制应该采用二进制形式，并且计算机应该按照程序顺序执行。同时，我们应该将程序看作一种数据，将程序编码与数据一同存放在存储器中的不同地方，这样计算机就可以调用存储器中的程序来处理数据。这就是“存储程序”的概念，是冯·诺依曼结构的核心设计思想。依据这个核心思想，冯·诺依曼结构消除了此前只能依靠硬件控制程序的计算机结构，通过将程序编码视同数据存储在存储器中，使得计算机架构有了很好的可编程性，从而实现了硬件设计和程序设计的分离。这种开创性的设计大大促进了计算机的发展。因为无论实现什么功能的程序，按照冯·诺依曼结构，都可以被转换为数据的形式并存储在存储器中，执行程序时只需从存储器中的对应位置取出指令，然后顺序依次执行指令即可。这样冯·诺依曼确立了现今所用的将一组数学过程转变为计算机指令语言的基本方法，使得计算机具备了灵活性和普适性。

冯·诺依曼结构主要由运算器、控制器、存储器、输入设备和输出设备5部分组成。运算器是执行各种算术和逻辑运算操作的部件；控制器是进行指令分析和执行的核心部件；存储器是存储程序和各种数据的部件；输入设备和输出设备是人与机器相互沟通的媒介。

（1）完成数据加工处理的运算器：运算器的主要部件被称为算术逻辑单元（Arithmetic Logic Unit，简写为ALU）。ALU的主要功能是在控制信号的作用下，完成加、减、乘、除等算术运算以及与、或、非、异或等逻辑运算。

（2）控制程序执行的控制器：控制器又被称为控制单元（Control Unit），负责从存储器中取出并翻译指令，然后将控制指令发送至相关部件，控制相应的部件执行指令所指定的操作。运算器和控制器共同组成了中央处理器（Central Processing Unit），也就是我们常说的CPU。其主要功能是解释计算机指令以及处理数据，告诉计算机的每一个部件按照指令完成指定的动作。CPU是计算机的运算和控制核心。

（3）存储程序和数据的存储器：存储器的主要功能是存储程序和各种数据。存储器中的数据格式均为二进制格式。所以，计算机中的程序和数据都是以0和1这样的二进制码进行存储的。

（4）装载数据和程序的输入设备：输入设备是用于向计算机输入数据的设备。它将各种形式的信息转化为计算机可以识别的二进制的形式，常见的有键盘、鼠标、摄像头等。

（5）显示处理结果的输出设备：输出设备是用于转换计算机输出信息形式的设备。它将计算机运行得到的二进制数据转化为其他设备或人能接受和识别的信息形式，常见的有打印机、音响、显示器等。

冯·诺依曼将强大的计算理论模型——通用图灵机，转化成了可以指导实际计算机建造的冯·诺依曼结构。同时，计算机采用二进制数制，并按照程序顺序执行以及“存储程序”等设计概念，这也成为现代计算机程序设计的重要原则和基础规则。

可以说图灵机和冯·诺依曼结构为计算机科学奠定了坚实的理论基础，并为计算机世界制定了最基础的运行规则。后世的计算机学者、工程师、程序员，都是在这个理论基础之上、在运行规则的指导下开展工作的。在计算机世界里，科学家和工程师在图灵机的理论边界之内，依照冯·诺依曼结构，将现实需求转化并定义为问题，找到描述问题的方式或者模型，寻求解决问题模型的数学方法或工程方案，将解决方案实现为各种程序和软硬件产品，从而完成现实世界需求的响应和问题的解决。隐私计算这项技术就是遵循着这样的问题解决之道：将数据的保护和使用，转化为如何在保护数据信息前提下的数据计算这样一个问题，并给出了隐私计算这个解决方案，同时致力于在理论和工程上不断地优化完善，以期能够将隐私计算广泛服务于数据时代的人类社会。想要在发挥数据价值的同时实现保护数据信息这个目标，离不开密码学这项保护信息安全的核心科学。接下来，让我们了解一下隐私计算技术的重要安全基石：密码学。