一個無法證明的邏輯問題

前三期我們用恩尼格碼的製造與破解闡述了一個用機器戰勝機器的故事。這也可以說是人們對計算機概念進行實踐的一個起點。那麼計算機的概念又是從何而來呢？本期我們回到20世紀初頁，從一個數學的邏輯問題開始講起。

△ 大衛·希爾伯特。

1900年，德國數學家及邏輯學家大衛·希爾伯特在國際數學大會上發表了題為「數學問題」的演講，並提出了23道當時待解決的數學問題。這份演講中提到的23個問題大力推動了整個20世紀的數學發展，並被後世稱為希爾伯特的23個問題。其中第十個問題提到，我們是否可以設計一個可行的過程，並通過有限次運算來判定任何多個未知數的整係數方程有無整數解。在提出這個問題之後，希爾伯特大力推崇一個概念，便是讓所有數學家都致力去構建數學公理，以至於所有的數學理論都能從這些構建的公理中，通過一個完備且一致的體系得到證明。

為了進一步說明希爾伯特的構想，這裡首先闡述一下其構想中提到的三個概念。一個是完備性，即所有數學理論都是可證明的。其次是一致性，即證明結果要麼是對，要麼是錯，不能存在自我矛盾（即對錯共同存在）。中學時候學過的反證法便是基於數學理論的一致性所得出的一種證明方法。最後是決定性，即是我們能通過一個可行的過程和有限次運算來證明數學理論。當然希爾伯特所推崇的這個概念是否可行完全取決於他1900年演講中提到的的第十個問題是否能夠被證明為正確。這個問題也使得大批當代數學家趨之若鶩，力圖證明希爾伯特提出的構想。而該構想也被命名為「希爾伯特判定性問題」。

△ 庫爾特·哥德爾。

這個問題在1931年得到了部分的解答。當時奧匈帝國數學家庫爾特·哥德爾在他的論文（On Formally Undecidable Propositions of Principia Mathematica and Related Systems）中提到了一個非常重要的概念——不完備性理論。哥德爾用數學及邏輯學的方法證明出了希爾伯特決定問題中所提出的完備性與一致性無法共存於一個數學系統里。為了理解方便，這裡我們舉一個簡單的例子 。「筆者聲明現在我寫的這個句子是一句謊話。」 如果你試圖去證明這句話的真偽，你會發現，如果這句話是真的，那麼我寫的這句話就是一句假話，如果這句話是假的，那麼我寫的這句話就是一句真話，無論從哪個角度來看他們都是相互矛盾的。也就是說如果這句話可被證明真偽（具有完備性），那麼得出來的結論必然相互矛盾（不具備一致性）。相反如果要保證證明一致性（沒有相互矛盾的結論），那麼這句話無論是真還是假，他都是不可以被證明的（不具備完備性）。

這套不完備理論自提出之後在數學及哲學界引起了不小的轟動。自此之後，越來越多的數學問題被證明是不可判定的。數學家們開始人心惶惶，因為誰也不能保證自己辛苦研究幾十年的問題不會於未來的某一天在數學系統中被證明為不可判定。哲學家們也開始自我懷疑，因為他們所信奉的絕對真理的體系開始瓦解，因為不完備理論使得他們知道了有些東西我們即使是在理論上也是不可能知道的。

△ 圖靈在1936年發表的論文。（圖片來源：A.M.Turing）

在哥德爾解決了「希爾伯特判定性問題」中的完備性和一致性的不共存關係之後，這個問題便只剩下了決定性沒有得到證明（因為即便是哥德爾證明了不是所有數學理論都是可證明的，也無法證明原來希爾伯特猜想中所提到的通過一個可行的過程及有限次運算來證明數學理論的可行性）。於是這個問題便留到了五年後，在一篇名為「論可計算書機器判定問題上的應用」（On Computable Numbers, with an Application to the Entscheidungsproblem）的論文中得到了最終的解答。沒錯，這就是圖靈享譽世界很重要的一篇論文之一。可能當時連他也不會想到這篇文章中所提到的概念會最終使他從數學和邏輯學系統中開闢出一個全新的分支——計算機。

在「希爾伯特判定性問題」中提到的可行的過程及有限次的運算這些概念屬於非常模糊的概念。因為它們在當時沒有數學上的一個完整的定義。於是圖靈在論文里提出了圖靈機這個的概念，用類似有限狀態機的原理（注意僅是類似，因為圖靈機的功能遠超過了有限狀態機）定義了「有限次運算」，並用圖靈機運算過程定義了「可行的過程」並將之重新命名為「演算法」（algorithm）。這便是如今計算機體系結構以及程序演算法設計最開始萌芽的地方。接下來我們就來介紹一下圖靈機的概念。（值得注意的是，圖靈機只是一個概念，並不是一個實體機器。）

如下圖所示，圖靈機由一個無限長的紙帶（TAPE），讀寫頭（HEAD），一套控制讀寫頭移動規則的規則表（TABLE）和一個狀態寄存器（REGISTER）組成。

△ 圖靈機的結構。（圖片來源：Wikipedia）

圖中紙帶被分為無限個格子，可記錄任何字母，二進位數字（0,1）以及空白。每個格子里代表了圖靈機的輸入和輸出信息而空白則表示沒有任何信息。下方三角為讀寫頭，表示當先讀寫（輸入輸出）的位置。讀寫頭可向左右移動，每次移動一個。其移動方向由當下讀寫頭所指的輸入和規則表決定（規則表其實就是當時控制計算機的程序）。讀寫頭首先記錄下當下位置的狀態（q₁）並存入狀態寄存器，然後根據當下輸入對比程序中的要求進行左右移動或停留在當下位置，最後根據程序輸出字母或數字，修改新的位置的數字或字母。每次工作圖靈機的讀寫頭都會從起始位置開始，由規則表和輸入控制其移動到不同位置，並最終在程序結束時停留在空白格里。在細心地讀者會發現，圖靈機的整個構想已經滿足了現代計算機所需要的所有基本元素，包括程序，輸入輸出和存儲器。這也是為什麼說圖靈機奠定了現代計算機發展的基礎。因為現在計算機能做的一切事情圖靈機都可以做到（圖靈機的具體工作例子我們會在今後的文章中慢慢提到）。

圖靈在論文中用讀寫頭在受程序和輸入控制下進行的移動來定義了希爾伯特判定性問題中的「可行過程」，並用讀寫頭通過有限次移動在程序結束時最終停留在空白格這一過程定義了決定問題中的「有限次運算」。通過這兩個定義的設定，希爾伯特的決定性問題就變成了：是否存在這樣一個圖靈機，使其能判定任意一個程序能否在有限時間內結束運行。這就演變成了另外一個重要的理論——停機理論。

可圈可點的是，圖靈用了一種非常簡單的辦法證明了這一理論的不可證的特性，所用的方法和我們之前提出證明謊言的例子類似。首先我們假設存在這樣一個圖靈機能夠對任意程序作出是否結束運行的判斷。先不管該機器內部如何運行，我們假設它能在接收到字元輸入（來自紙帶）和程序輸入（來自規則表）之後輸出「是」和「否」。（是代表判定運行可以結束，否代表判定運行不能結束）。我們將該圖靈機命名為H。然後我們將H稍作改動，在H輸出「是」的時候將輸出連接到一個無限的循環程序里，並在H輸出「否」的時候直接停止運行。我們把改進后的機器命名為H』。現在我們把H』同時作為H』這個機器本身的字元輸入和程序輸入，這時會發生什麼呢？ 如果H判斷「是」那麼H』則不會停止，而如果H判斷否，那麼H』則會停止（注意H』是通過H改變而來的，所以H』包含H）。而我們最開始假設的是機器H總能對程序是否結束運行做出正確的判斷。我們由此得到矛盾，從而得到這樣的機器H不存在。也就是說，不存在這樣一個圖靈機能準確的對程序是否結束運行作出判斷。而這個證明最關鍵的一點就是利用了自我干涉的原則和數學系統中的一致性。

至此希爾伯特最早提出來的讓所有數學理論都能從數學家構建的公理中得到證明的這一概念被圖靈證明了不可行。而圖靈在證明整套理論中所提出來的圖靈機的概念也為計算機體系結構及程序設計的發展奠定了基石。那麼圖靈機具體是如何做計算的呢？同時期的其他科學家是否有類似的研究呢？他們和圖靈的研究又是如何共同促進了現代計算機及程序的發展呢？且看下回分解。