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）顯示處理結果的輸出設備：輸出設備是用于轉換計算機輸出信息形式的設備。它將計算機運行得到的二進制數據轉化為其他設備或人能接受和識別的信息形式，常見的有打印機、音響、顯示器等。

馮·諾依曼將強大的計算理論模型——通用圖靈機，轉化成了可以指導實際計算機建造的馮·諾依曼結構。同時，計算機采用二進制數制，并按照程序順序執行以及“存儲程序”等設計概念，這也成為現代計算機程序設計的重要原則和基礎規則。

可以說圖靈機和馮·諾依曼結構為計算機科學奠定了堅實的理論基礎，并為計算機世界制定了最基礎的運行規則。后世的計算機學者、工程師、程序員，都是在這個理論基礎之上、在運行規則的指導下開展工作的。在計算機世界里，科學家和工程師在圖靈機的理論邊界之內，依照馮·諾依曼結構，將現實需求轉化并定義為問題，找到描述問題的方式或者模型，尋求解決問題模型的數學方法或工程方案，將解決方案實現為各種程序和軟硬件產品，從而完成現實世界需求的響應和問題的解決。隱私計算這項技術就是遵循著這樣的問題解決之道：將數據的保護和使用，轉化為如何在保護數據信息前提下的數據計算這樣一個問題，并給出了隱私計算這個解決方案，同時致力于在理論和工程上不斷地優化完善，以期能夠將隱私計算廣泛服務于數據時代的人類社會。想要在發揮數據價值的同時實現保護數據信息這個目標，離不開密碼學這項保護信息安全的核心科學。接下來，讓我們了解一下隱私計算技術的重要安全基石：密碼學。