圖靈機意義

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

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

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

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

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

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

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

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上有我就不贅述)。圖靈機的不可判定問題便需要借助對角線方法。而實數集“大于”自然數集這個事實，可以這么想：“無限&TImes;無限”比“無限&TImes;有限”大。每個自然數是有限的，集合是一階無限，自然數集就是一階無限；相較之下，一個實數是一階無限，集合又是一階無限，那么實數的集合就是二階無限。這個一階二階只是我個人的說法，關于不同集合之間的大小關系，康托提出連續統假設，即希爾伯特第一問題，認為不存在一個基數絕對大于可數集而絕對小于實數集的集合，不過這跟今天的話題沒有關系，不再展開。