算法系列教程02 - 從羅素悖論到圖靈機
艾倫·圖靈
為什麼會出現圖靈機？這得從羅素悖論講起。
羅素悖論
有位理髮師放出豪言：他給且只給不為自己刮鬍子的人刮鬍子。問：這位理髮師該為自己刮鬍子嗎？
如果理髮師為自己刮鬍子，那麼按照他的豪言“只給不為自己刮鬍子的人刮鬍子”他不應該為自己刮鬍子；但如果他不為自己刮鬍子，同樣按照他的豪言“他給不為自己刮鬍子的人刮鬍子”他又應該為自己刮鬍子。
這個問題就是著名的 理髮師悖論 ，是哲學家兼數學家的羅素用來比喻 羅素悖論 的一個通俗說法，也被叫作集合論悖論，用集合論來描述就是：
集合 S 由一切不屬於自身的元素組成，那麼 S 是否屬於 S 呢？
在這一悖論提出之前集合論是數學理論的重要基礎，結合集合論，歷史上的一切數學問題都可以完美地等到求證，當時人們已經相信整個數學大廈已經建立起來了，數學已經迎來了絕對的嚴格性。
但羅素悖論出現後，人們心中的大廈坍塌了，直接導致了歷史上的第三次數學危機。當時提出集合論的數學家康托爾也被這個悖論逼瘋了，可憐的康托爾。由此可見羅素這個人在數學界的影響。
哥德爾不完備性定理
當時人們好不容易在集合論的基礎上構建起了數學大廈，結果集合論也是不完美的，連這個基礎都崩潰了。那還能不能找到一個系統，在它的基礎上真正構建整個數學大廈呢？
後來有一個數學家哥德爾成功證明了一個定理，大意是這樣的：
世界上存在我們既沒辦法證真也沒辦法證偽的命題。
比如前文說的的集合論，還有典型的 1+1=2 的問題，我們既不能證明它們是真命題，也不能證明它是偽命題。這個定理被稱為 哥德爾不完備性定理 。我們可能會想，這種定理也能被證明？他是怎麼證明的？這個我們就不去研究了，反正哥德爾他就是證明了這樣的一個定理，過程是很複雜的。
哥德爾不完備性定理的證明結束了關於數學基礎的爭論，宣告了數學不是絕對嚴格性的，把數學徹底形式化這種願望是不可能實現的，不存在這樣一個完美的數學系統。
哥德爾不完備性定理告訴我們，不要試圖去尋找一個完美的系統，這不存在的，這輩子都不可能存在的。
那麼，有了這個結論，我們是不是就可以不往下探索了呢？如果還可以往下探索，我們該探索什麼問題？
計算模型和圖靈機
通過哥德爾不完備性定理，我們知道，有些問題是既不能證真也不能證偽的，有些問題是可以證真或證偽的。對於這兩類問題，它們的邊界在哪裡？怎麼去判定一個未解的問題是否真的有解？
為了解答這個問題，我們需要引入一個度量： 可計算問題 。在數學中對應可計算函式，它的定義是這樣的：
設函式 f 的定義域為 D，值域為 R，如果存在一種演算法，對於 D 中任意給定的 x，都能計算出 f(x) 的值，則稱函式 f 是可計算的。
這是當時諸多數學家、邏輯學家等對判斷一個問題是否可計算提出的一個思路。通俗的講就是，先給定一個模型，如果拿有限的值去套這個模型，能夠得到期望的結果，那就說明這個問題是可計算的，否則是不可計算的。這裡用來判斷問題是否可計算的模型就被稱為： 計算模型 。
那麼如何設計或找到這樣一個計算模型呢？這是當時人們所面臨的一個重要問題，一直沒有得到解決。後來終於有一位數學家提出了一個這樣的模型，他就是圖靈。他提出的這個計算模型被稱為 圖靈模型 ，而這個圖靈模型就是 圖靈機 。
好了，到這裡我們已經知道了歷史背景下為什麼會誕生圖靈機。那麼圖靈模型它是一個怎樣的模型？圖靈機它又是如何工作的呢？這就是下一篇要講的內容。
最後順帶講一下圖靈這個人，相信很多人都聽過他的故事，他真的是很牛逼。他 24 歲就提出了圖靈機，二戰期間參與了密碼破譯工作，任密碼破譯總顧問，後來還提出了著名的“圖靈測試”，逝世前兩年還寫出了第一個國際象棋程式。圖靈的貢獻對計算機領域的發展有著非常深遠的影響，可惜他享年只有 42 歲（1912 年 - 1954 年），如果不是英年早逝的話，計算機的整個發展史可能就要重寫了。
參考：
1. http://t.cn/EvMrKcS
2. http://t.cn/EvMru3r
3. http://t.cn/RGJrnmS