圖靈機(jī)有什么意義_學(xué)習(xí)圖靈機(jī)模型中遇到的問題

?圖靈機(jī)意義

圖靈提出圖靈機(jī)的模型并不是為了同時(shí)給出計(jì)算機(jī)的設(shè)計(jì)，它的意義我認(rèn)為有如下幾點(diǎn)：

1、它證明了通用計(jì)算理論，肯定了計(jì)算機(jī)實(shí)現(xiàn)的可能性，同時(shí)它給出了計(jì)算機(jī)應(yīng)有的主要架構(gòu)；

2、圖靈機(jī)模型引入了讀寫與算法與程序語(yǔ)言的概念，極大的突破了過去的計(jì)算機(jī)器的設(shè)計(jì)理念；

3、圖靈機(jī)模型理論是計(jì)算學(xué)科最核心的理論，因?yàn)橛?jì)算機(jī)的極限計(jì)算能力就是通用圖靈機(jī)的計(jì)算能力，很多問題可以轉(zhuǎn)化到圖靈機(jī)這個(gè)簡(jiǎn)單的模型來考慮。

對(duì)圖靈機(jī)給出如此高的評(píng)價(jià)并不是高估，因?yàn)閺乃脑O(shè)計(jì)與運(yùn)行中，我們可以看到其中蘊(yùn)涵的很深邃的思想。通用圖靈機(jī)等于向我們展示這樣一個(gè)過程：程序和其輸入可以先保存到存儲(chǔ)帶上，圖靈機(jī)就按程序一步一步運(yùn)行直到給出結(jié)果，結(jié)果也保存在存儲(chǔ)帶上。另外，我們可以隱約看到現(xiàn)代計(jì)算機(jī)主要構(gòu)成（其實(shí)就是馮諾依曼理論的主要構(gòu)成），存儲(chǔ)器（相當(dāng)于存儲(chǔ)帶），中央處理器（控制器及其狀態(tài)，并且其字母表可以僅有0和1兩個(gè)符號(hào)），IO系統(tǒng)（相當(dāng)于存儲(chǔ)帶的預(yù)先輸入）；

4、“圖靈機(jī)”只是假象的“計(jì)算機(jī)”，完全沒有考慮硬件狀態(tài)，考慮的焦點(diǎn)是邏輯結(jié)構(gòu)。圖靈在他著作里，進(jìn)一步設(shè)計(jì)出被人們稱為“通用圖靈機(jī)”的模型，圖靈機(jī)可以模擬其他任何一臺(tái)解決某個(gè)特定數(shù)學(xué)問題的“圖靈機(jī)”的工作狀態(tài)。圖靈甚至還想象在帶子上存儲(chǔ)數(shù)據(jù)和程序?！巴ㄓ脠D靈機(jī)”實(shí)際上就是現(xiàn)代通用計(jì)算機(jī)的最原始的模型。

學(xué)習(xí)圖靈機(jī)模型中遇到的三個(gè)問題

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

2） 為什么強(qiáng)大的圖靈機(jī)會(huì)不停機(jī)？

3） 為什么圖靈當(dāng)初要設(shè)計(jì)圖靈機(jī)？

圖靈機(jī)雖然構(gòu)造簡(jiǎn)單，但卻及其強(qiáng)大，它能模擬現(xiàn)代計(jì)算機(jī)的所有計(jì)算行為，堪稱計(jì)算的終極機(jī)器。然而即便是這個(gè)終極機(jī)器，也有令它無(wú)能為力的問題，這便是第一個(gè)要回答的問題：為什么圖靈機(jī)有不可判的問題？

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

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