?圖靈機意義

圖靈提出圖靈機的模型并不是為了同時給出計算機的設計，它的意義我認為有如下幾點：

1、它證明了通用計算理論，肯定了計算機實現的可能性，同時它給出了計算機應有的主要架構；

2、圖靈機模型引入了讀寫與算法與程序語言的概念，極大的突破了過去的計算機器的設計理念；

3、圖靈機模型理論是計算學科最核心的理論，因為計算機的極限計算能力就是通用圖靈機的計算能力，很多問題可以轉化到圖靈機這個簡單的模型來考慮。

對圖靈機給出如此高的評價并不是高估，因為從它的設計與運行中，我們可以看到其中蘊涵的很深邃的思想。通用圖靈機等于向我們展示這樣一個過程：程序和其輸入可以先保存到存儲帶上，圖靈機就按程序一步一步運行直到給出結果，結果也保存在存儲帶上。另外，我們可以隱約看到現代計算機主要構成（其實就是馮諾依曼理論的主要構成），存儲器（相當于存儲帶），中央處理器（控制器及其狀態，并且其字母表可以僅有0和1兩個符號），IO系統（相當于存儲帶的預先輸入）；

4、“圖靈機”只是假象的“計算機”，完全沒有考慮硬件狀態，考慮的焦點是邏輯結構。圖靈在他著作里，進一步設計出被人們稱為“通用圖靈機”的模型，圖靈機可以模擬其他任何一臺解決某個特定數學問題的“圖靈機”的工作狀態。圖靈甚至還想象在帶子上存儲數據和程序?！巴ㄓ脠D靈機”實際上就是現代通用計算機的最原始的模型。

學習圖靈機模型中遇到的三個問題

1） 為什么圖靈機有不可判的問題？

2） 為什么強大的圖靈機會不停機？

3） 為什么圖靈當初要設計圖靈機？

圖靈機雖然構造簡單，但卻及其強大，它能模擬現代計算機的所有計算行為，堪稱計算的終極機器。然而即便是這個終極機器，也有令它無能為力的問題，這便是第一個要回答的問題：為什么圖靈機有不可判的問題？

首先明確什么是圖靈可識別（Turing recognizable）和圖靈可判定（Turing decidable）。圖靈機的識別對象是語言，圖靈可識別當然不是說圖靈本人能識別的語言（照這樣說漢語可能是圖靈不可識別的~），事實上這只是簡稱，全稱應該是圖靈機可識別語言（Turing machine recognizable language）和圖靈機可判定語言（Turing machine decidable language）。 一臺圖靈機在讀取一個串后可能進入三種狀態：接受、拒絕、循環，如果圖靈機進入循環狀態，那它將永不停機。現在假設有語言A，如果能設計出一臺圖靈機M，對于任意字符串ω，如果ω∈A，那么M讀取ω后會進入接受狀態，那么A是一個圖靈可識別語言。注意這個定義對于ω不屬于A的情況沒有做出限制，所以M讀取到不屬于A的ω，那么它有可能拒絕，也有可能循環。 圖靈可判定語言的要求更嚴格，它要求對于語言A能設計出一臺圖靈機M：如果ω∈A，M進入接受狀態；否則進入拒絕狀態。如果一個語言是圖靈可判定的，總能設計出一臺圖靈機，能在有限步數內判定一個字符串是不是屬于這個語言。如果一臺圖靈機對所有輸入總是停機，那么稱它為判定器（decider）。然而第一個問題指明一定有所有判定器都不能判定的問題，要證明這一點，得從康托（Georg Cantor）說起。

康托最大的貢獻可能是創建了現代集合論，他認為某些不同的無窮集合有不同的大小。1891年，康托發表了一篇只有5頁的論文，證明實數集的基數大于自然數集，并在這篇論文中提出了傳說中的對角線方法（方法雖然巧妙但很簡單，wiki上有我就不贅述）。圖靈機的不可判定問題便需要借助對角線方法。而實數集“大于”自然數集這個事實，可以這么想：“無限×無限”比“無限×有限”大。每個自然數是有限的，集合是一階無限，自然數集就是一階無限；相較之下，一個實數是一階無限，集合又是一階無限，那么實數的集合就是二階無限。這個一階二階只是我個人的說法，關于不同集合之間的大小關系，康托提出連續統假設，即希爾伯特第一問題，認為不存在一個基數絕對大于可數集而絕對小于實數集的集合，不過這跟今天的話題沒有關系，不再展開。

#e#

回到正題：圖靈機。圖靈機能夠識別語言，而圖靈機本身當然也可以由語言描述。什么是語言？給定一個字母表∑，一個{［由∑中的字母組成的序列］的集合}就是∑上的一個語言（為了消除歧義，算式可以加括號，語言當然也可以）。必須清楚這些概念中哪些是有限的，哪些是無限的：一個語言包含的字符串數可以是有限的也可以是無限的，但一個字母表上的所有語言的數目是無限的，而語言中任意一個字符串的長度是有限的。

首先要證明的是：一個字母表上所有語言構成的集合不僅是無限的，而且是不可數的。 這里需要借助無限二進制序列的集合來幫助證明。一個無限二進制序列（即{0，1}組成的無限序列）是一階無限，那么這些序列組成的集合就是“無限×無限”，可以通過對角線方法證明無限二進制序列是不可數的，也可以將實數集的元素唯一地映射到無限二進制序列集合。

用后者的方法，可以這樣建立二者之間的映射：二進制序列每4個為一組，用8421BCD碼編碼，4位對應實數中的一位，再用1111表示小數點，這樣每個實數總能映射到一個唯一的二進制序列，既然實數集不可數，那么無限二進制序列也不可數。 接下來證明，{無限二進制序列的集合B}與（任意字母表）{∑上的所有語言組成的集合L}是同樣規模的，仍然通過建立映射的方法。設∑上所有字符串的集合按字典序排序成∑*={s1， s2， s3， 。..}，L中的每個語言A都對應一個二進制序列b：如果si∈A，bi=1；否則bi=0，這樣的序列稱作A的特征序列。舉個例子，如果∑={a，b}，A是所有包含b的串構成的語言，則A的特征序列b如下：

∑*={a， b， aa， ab， ba， bb， aaa， aab，。..} A ={ b， ab， ba， bb， aab，。..} b = 0 1 0 1 1 1 0 1 ，。..

反之，每個二進制序列b也能對應一個唯一的語言，所以L與B等勢，又因為B是不可數集，所以{∑上的所有語言組成的集合L}也是不可數的。

好，明確了所有語言構成的集合是不可數的之后，我要回答下面這個問題：為什么圖靈機集合是可數的？（reserve：哥德爾配數法）

從圖靈機的定義入手，圖靈機是1個7元組（Q，∑，Γ，δ，q0，qaccept，qreject）。每一臺圖靈機總是由有限個字符編碼而成： 1） 有限的狀態集Q。 2） 有限的輸入字母表∑。 3） 有限的帶字母表Γ。 4） 有限的轉換函數δ。 5） 1個起始狀態q0。 6） 有限個接受狀態qaccept。 7） 有限個拒絕狀態qreject。 若上述每個元素都用二進制編碼表示，任意一臺圖靈機都只需要有限個二進制位。再將這些二進制串按照字典序排列，就可以得到一個{圖靈機集合}-》自然數集的一一對應。

好，給定一個字母表∑： ［∑上的所有語言］的集合《=》［二進制無限序列］的集合《=》實數集《=》不可數集 ［所有圖靈機］的集合《=》自然數集《=》可數集

有不可數個語言，卻只有可數個圖靈機，語言的集合“大于”圖靈機的集合，所以從本質上證明了必然存在圖靈機不能識別的語言。 推論：必然存在圖靈機不能判定的語言。理由是圖靈可判定語言的集合不會大于圖靈可識別語言。 圖靈可判定語言要求更嚴格，所以應該存在這樣的語言：它是圖靈可識別的，但同時不是圖靈可判定的。事實確實如此，圖靈自己就給出了一個： A={《M， ω》 | M描述一臺圖靈機，且M描述的機器接受ω} 首先證明A是圖靈可識別的（形式化證明太過繁瑣，這里只給出很高層次的證明）。設通用圖靈機U這樣運行：U接受參數《M， ω》，它可根據圖靈機M的描述模擬M的行為，并在虛擬的M上計算ω。如果M接受ω，那么U進入接受狀態；否則拒絕。

依據定義以及通用圖靈機的存在性，U能識別A，所以A是圖靈可識別的，證畢。

順著這個證明走下去，如果M本身遇到輸入ω時會陷入循環，那么模擬M的U也會陷入循環，所以U不是判定器。如果U知道M在ω上不停機，那么它可以進入拒絕狀態，問題是它不知道。那么能判定A的圖靈機存在嗎？我們就假設存在H，使得： 1）若M接受ω，則H（《M，ω》） =接受 2）若M不接受ω，則H（《M，ω》） =拒絕 根據H的定義，無論M接不接受ω，H總能停機。進一步再假設有圖靈機D，以H為子程序，接受一個描述圖靈機的串《M》，在H上運行H（《M，《M》》），并返回相反的結果： 1）若H（《M，《M》》）=接受，則D（《M》）=拒絕 2）若H（《M，《M》》） =拒絕，則D（《M》）=接受 也就是說，如果一臺圖靈機M接受描述它自身的串《M》，那么D（《M》）進入拒絕狀態。構造這樣一臺奇怪的D是為了讓它做下面這件事情，現在對D輸入描述它自己的串《D》，看看會發生什么： 1）若D接受《D》，即H（《D，《D》》）=接受，則D（《D》）=拒絕 2）若D拒絕《D》，即H（《D，《D》》） =拒絕，則D（《D》）=接受 到底是接受還是拒絕呢？兜了一個圈子，D繞回原地，產生了矛盾。所以D是不存在的，所以H也是不存在的，語言A不可判定，證畢。

上述證明比較繞，我用一階邏輯再改寫一遍

命題： 1）P：存在語言A的判定器H 2）Q：存在以H為子程序的圖靈機D（描述見上） 已知條件： 1）P→Q：如果有H，總能設計出D 2）┐Q：D是不存在的（證明見上） 證明： 1 P 假設 2 P→Q 已知條件 3 Q 1，2 4 ┐Q 已知條件 5 ┴ 推出矛盾 6 ┐P 假設不成立 上面的證明中，圖靈機D的構造簡直是神來之筆，圖靈怎么想到的？雖然之前的證明沒有直接給出不可判定的語言，但已經從數量上證明有圖靈機不能判定的語言，由于判定器的要求更嚴格，所以可以推斷所有判定器構成的集合小于所有語言構成的集合。這是個與“實數集的勢大于自然數集”類似的命題，所以應該能用類似的方法——對角線方法證明。好，嘗試一下。 康托構造映射表格時，表格的每一行由一個自然數表示這是第幾行，每一列也由一個自然數標識列數，對角線法構造出來的實數實際上是一行，然而這一行卻和每一行都不一樣。剛才的證明我們看到，圖靈機集合是可數集，可將其對應自然數，標識表格的每一行，那么每一列用什么標識呢？怎樣讓列數與行數相等呢？行和列的交叉處是什么呢？自然數/實數的例子中，每一行由一個自然數對應一個實數，在這個問題中，行由圖靈機標識了，那么不難想到，每一行應該是一個語言。語言又該如何表示？下面依次回答這些問題。 列應該用什么來標識？在對角線方法中，表格的行列數一致，行和列都用自然數集標識。那么首先可以想到既然行用圖靈機標識，那么列也可以用圖靈機標識。但是這樣的話行列交匯處就沒什么意義了，試問隨意挑選的兩臺圖靈機之間能擦出什么火花？ 腦子再轉一下，圖靈機與圖靈機之間沒有什么一般化的關系，圖靈機識別的是語言，是字符串，那么將標識列的圖靈機換成描述圖靈機的串，既保持了行列數一致性，又讓行列交匯處有了非平凡的意義！即，用M1， M2， M3.。.標識第1行、第2行、第3行??再用描述圖靈機的字符串《M1》， 《M2》， 《M3》。..標識第1列、第2列、第3列??行列交匯處就填入accept或reject，表示一臺圖靈機是否接受描述某一臺圖靈機的串！這樣，每一行剛好也就是一個語言，每一個部分的意義都正好是我們想要的。

《M1》

《M2》

《M3》

《M4》

??

M1

accept

reject

reject

reject

M2

reject

reject

accept

M3

accept

accept

reject

accept

M4

reject

Accept

reject

accept

??

為構造對角線準備的表格 走到這一步，離結果就很近了。 若將所有圖靈機和描述它們的串排成表，行列交叉處就是H（Mi，《Mj》）的運行結果。構造圖靈機D，實際上就是用對角線方法選出一行，這一行的第1列與M1相反，第2列與M2相反，第3列與M3相反??所以構造出來的這一行肯定不在這個表中。如果在，這么D所在的行與對角線相交處會出現矛盾！

《M1》

《M2》

《M3》

《M4》

??

D

??

M1

accept

reject

reject

reject

accept

M2

reject

Reject

accept

reject

reject

M3

accept

Accept

Reject

accept

accept

M4

reject

accept

reject

accept

reject

??

D

reject

accept

accept

reject

??

D的每一列都與對角線相反，到它自己與對角線的交匯處產生矛盾 想必圖靈深知語言集比圖靈機集要“大”，一臺圖靈機只能對應一個語言，所以用對角線方法必定能構造出一個所有圖靈機都不能識別的語言。這個語言就是D“識別”的語言，則D的語言肯定不會出現在那個圖靈機和對應語言的表格中。如果強行將這臺“不存在的圖靈機”安插進表格中，必然產生矛盾，矛盾就發生在D所在行與對角線的相交處。就像康托用對角線方法構造出來的那個實數無法插入到［自然數-》實數］的映射表格中，否則構造出來的那個實數就與它自己矛盾了，神奇的“圖靈機D”就是這么來的。 圖靈是用圖靈機的術語改寫了對角線方法，在圖靈機上重現康托的思想。

至此，回答了第一個問題：為什么圖靈機也有不可判定的語言，并且還構造了一個這樣的語言，即A={《M， ω》 | M描述一臺圖靈機，且M描述的機器接受ω}，A又被稱為接受問題。

語言A是超越圖靈機極限的必然產物，因為圖靈機和語言的內在關系決定了A這樣不能被任何圖靈機判定的語言是存在的。這是本質上的原因，但關于A本身還有一個表象上的原因（之前提到過）：之所以不能用圖靈機斷定其它圖靈機是否接受一個串，是因為圖靈機不能斷定其它圖靈機在某個輸入串上計算時是否會停機，這個問題同樣是不可判定的，這就是著名的停機問題（Halting problem）。莊子曰，“吾生也有涯，而知也無涯，以有涯隨無涯，殆已”。以有限的步驟去判定可能無限的計算，殆已。 但由此我產生了一個很大的疑問：為什么圖靈機會不停機？這也是我試圖回答的第二個問題。

#e#

圖靈機雖然強大，但是不停機的缺陷是人們萬萬不想要的。然而這缺陷是天生的，原因是??圖靈賦予圖靈機兩個無限： 1）圖靈機能在輸入字符串上左右移動，步驟無限，時間無限。 2）圖靈機有一條無限長的帶子，供讀寫頭在上面活動，空間無限。 有窮狀態機和下推自動機這兩種更簡單能力更弱的機器只能看到極其有限的歷史，它們的讀寫頭只能在輸入字符串上單向移動，所以肯定會停機。而圖靈機的讀寫頭卻可以在輸入串上左右移動??一旦擁有這個能力，圖靈機可以看到更多的歷史，同時就必須承擔這種能力帶來的風險——無限循環。另一方面，圖靈機擁有無限長的帶子，給讀寫頭的移動提供了無限的空間，更增加了循環的可能。 實際計算機沒有無限長的帶子，只有有限的內存，所以讀寫頭左右移動這種能力帶來的影響更致命：即使只有有限的空間，也可能陷入無限的循環。 然而很遺憾我的嘗試只能到此為止了，現在的我還不能從本質上回答“為什么不停機”。根據我的理解，圖靈機會不停機與哥德爾不完備定理有關。應該是圖靈機這兩種能力（左右移動，無限帶子）讓它足以蘊含皮亞諾算術公理，同時引入了既不能證明也不能證否的命題：碰到這種情況，圖靈機就陷入循環了。希望自己將來能夠摸清背后的本質，完整地回答為什么強大的圖靈機會不停機？ 既然圖靈機有這么大的缺陷，為什么圖靈當初還要設計圖靈機？這要從上個世紀初數學界的boss希爾伯特（David Hilbert）說起。1928年，希爾伯特在國際數學家大會上很樂觀地預期，數學將在不久的將來建立在牢固的基礎上，并提出關于一階邏輯公式可滿足性的判定問題（Entscheidungs Problem）。引用我以前寫過的一段話： 希爾伯特計劃把數學建立在一個完備的、一致的公理化系統之上。如果他成功了，這意味著： 一，所有的數學命題都能用符號無二義地表達出來； 二，所有的數學命題都能被證明或證偽（完備性）； 三，對任意數學命題P，如果P被證明，那么?P必定能被證偽（一致性）。 四，如果最后再找到一個算法，能機械地判定一個數學命題的真偽（可判定性），那么整個數學大廈就是鋼筋鐵骨屹立不倒了。 結果事與愿違。 1931年，哥德爾（Kurt G?del）發表了震驚數學界的哥德爾不完備定理，數學系統一致性和完備性的統一被打破。 1935-1936年間，圖靈在劍橋大學國王學院研究希爾伯特判定問題。1936年5月，圖靈完成論文《論可計算數及其在判定問題上的應用》（“On Computable Numbers， with an Application to the Entscheidungsproblem”），提出圖靈機作為通用計算模型，并基于圖靈機重新定義了可計算函數，同時給出了一個圖靈機無法判定的問題，即停機問題。 1937-1938年間，圖靈來到普林斯頓大學，在邏輯大神阿隆佐·邱奇的指導下繼續研究可計算性問題，這一階段他證明他的圖靈機與邱奇的λ演算具有等價的計算能力，并將這個結果作為附錄加到他的論文當中。而此前，哥德爾也提出了遞歸函數作為計算模型，不過同樣不久后被證明與λ演算等價。

在這一期間，邱奇-圖靈論題（Church-Turing Thesis）在邱奇、圖靈與哥德爾三人的工作下成型，該論題認為所有可有效計算的函數或算法都可以由一臺圖靈機來執行。這是一個論題，而不是命題，因為“可有效計算”本身是一個不存在精確定義的概念。目前普遍認為邱奇-圖靈論題是正確的，即所有人能想到的算法都能用圖靈機執行。

圖靈設計了一個能模擬所有計算的機器，然后證明這臺機器也有缺陷，有它不可判定的問題，給希爾伯特的幻想以最后的致命一擊，這便是圖靈機的起源。毫無疑問，雖然沒有直接參與圖靈機的設計，但希爾伯特功不可沒，因他提出的問題指引了其他數學家的工作。

圖靈機給計算機的具體實現提供了參考價值，但它速度太慢，也很難編程。相比之下它更是數學家們的神兵利器：算法問題從此有了堅實的基礎。但圖靈機也給出了現在這個時代人的上限，而這個“人”還不是一般人，而是人類中思考的精英——數學家。

根據邱奇-圖靈論題，圖靈機能模擬所有機械的、有限步的計算，但仍然有圖靈機不能識別的語言，它的誕生就是為了去證明它自己的缺陷??這就是為什么說計算機是數學家一次思考失敗的產物。