圖靈機(jī)簡(jiǎn)介和原理分析

圖靈機(jī)簡(jiǎn)介和原理分析摘要：1936年，阿蘭·圖靈提出了一種抽象的計(jì)算模型——圖靈機(jī)(TuringMachine)。圖靈機(jī)是指一個(gè)抽象的機(jī)器，可被視作任意解決有限數(shù)學(xué)邏輯過(guò)程的機(jī)器，它提供了一種簡(jiǎn)單有效的解決邏輯過(guò)程的方法，加快了后來(lái)諾依曼設(shè)計(jì)的計(jì)算機(jī)的出現(xiàn)。本文將對(duì)圖靈機(jī)的原理和歷史等進(jìn)行簡(jiǎn)介和分析。關(guān)鍵字：圖靈機(jī)，計(jì)算模型。圖靈機(jī)的歷史發(fā)展圖靈機(jī)被公認(rèn)為現(xiàn)代計(jì)算機(jī)的原型，這臺(tái)機(jī)器可以讀入一系列的零和一，這些數(shù)字代表了解決某一問(wèn)題所需要的步驟，按這個(gè)步驟走下去，就可以解決某一特定的問(wèn)題。這種觀念在當(dāng)時(shí)是具有革命性意義的，因?yàn)榧词乖?0年代的時(shí)候，大部分的計(jì)算機(jī)還只能解決某一特定問(wèn)題，不是通用的，而圖靈機(jī)從理論上卻是通用機(jī)。1936年,圖靈向倫敦權(quán)威的數(shù)學(xué)雜志投了一篇論文,題為"論數(shù)字計(jì)算在決斷難題中的應(yīng)用"。在這篇開(kāi)創(chuàng)性的論文中,圖靈給"可計(jì)算性"下了一個(gè)嚴(yán)格的數(shù)學(xué)定義,并提出著名的圖靈機(jī)"(TuringMachine)的設(shè)想。"圖靈機(jī)"不是一種具體的機(jī)器,而是一種思想模型,可制造一種十分簡(jiǎn)單但運(yùn)算能力極強(qiáng)的計(jì)算裝置,用來(lái)計(jì)算所有能想像得到的可計(jì)算函數(shù)。"圖靈機(jī)"與"馮?諾伊曼機(jī)"齊名,被永遠(yuǎn)載入計(jì)算機(jī)的發(fā)展史中。1950年10月,圖靈又發(fā)表了另一篇題為"機(jī)器能思考嗎"的論文,成為劃時(shí)代之作。也正是這篇文章,為圖靈贏得了"人工智能之父"的桂冠。在圖靈看來(lái)，這臺(tái)機(jī)器只用保留一些最簡(jiǎn)單的指令，一個(gè)復(fù)雜的工作只用把它分解為這幾個(gè)最簡(jiǎn)單的操作就可以實(shí)現(xiàn)了，在當(dāng)時(shí)他能夠具有這樣的思想確實(shí)是很了不起的。圖靈機(jī)的產(chǎn)生一方面奠定了現(xiàn)代數(shù)字計(jì)算機(jī)的基礎(chǔ)（要知道后來(lái)馮?諾依曼就是根據(jù)圖靈的設(shè)想才設(shè)計(jì)出第一臺(tái)計(jì)算機(jī)的）。另一方面，根據(jù)圖靈機(jī)這一基本簡(jiǎn)潔的概念，我們還可以看到可計(jì)算的極限是什么。也就是說(shuō)實(shí)際上計(jì)算機(jī)的本領(lǐng)從原則上講是有限制的。請(qǐng)注意，這里說(shuō)到計(jì)算機(jī)的極限并不是說(shuō)它不能吃飯、掃地等硬件方面的極限，而是僅僅就從信息處理這個(gè)角度，計(jì)算機(jī)也仍然存在著極限。這就是圖靈機(jī)的停機(jī)問(wèn)題。圖靈機(jī)原理及分析圖靈的基本思想是用機(jī)器來(lái)模擬人們用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過(guò)程，他把這樣的過(guò)程看作下列兩種簡(jiǎn)單的動(dòng)作：１）在紙上寫上或擦除某個(gè)符號(hào)；把注意力從紙的一個(gè)位置移動(dòng)到另一個(gè)位置；而在每個(gè)階段，人要決定下一步的動(dòng)作，依賴于(a)此人當(dāng)前所關(guān)注的紙上某個(gè)位置的符號(hào)和(b)此人當(dāng)前思維的狀態(tài)。為了模擬人的這種運(yùn)算過(guò)程，圖靈構(gòu)造出一臺(tái)假想的機(jī)器，該機(jī)器由以下幾個(gè)部分組成：一條無(wú)限長(zhǎng)的紙帶。紙帶被劃分為一個(gè)接一個(gè)的小格子，每找規(guī)則表中的對(duì)應(yīng)項(xiàng)而采取行動(dòng)。例如第5步讀入方格是黑色，內(nèi)部狀態(tài)為吃飽，根據(jù)這兩項(xiàng)輸入信息查找規(guī)則表找到對(duì)應(yīng)項(xiàng)是第二項(xiàng)，根據(jù)小蟲應(yīng)該后移，且內(nèi)部狀態(tài)變?yōu)轲囸I。不難看到，到了第8步，情況跟第4步完全相同，輸入都是白色紙帶和饑餓狀態(tài)，根據(jù)程序，小蟲將重復(fù)4－8之間的動(dòng)作，并一直持續(xù)下去……。盡管從長(zhǎng)期來(lái)看，小蟲會(huì)落入機(jī)械的循環(huán)，然而當(dāng)你輸入給小蟲白色信息的時(shí)候，它的反應(yīng)可能完全不同(如第4步和第6步的行為)所以，只要小蟲子的內(nèi)部狀態(tài)和程序非常復(fù)雜，那么小蟲的行為也會(huì)越來(lái)越超出你的想象!相信你已經(jīng)明白了這個(gè)小蟲模型，那么你就掌握了圖靈機(jī)的工作原理，因?yàn)閺谋举|(zhì)上講，這個(gè)小蟲模型就是一臺(tái)圖靈機(jī)。圖靈機(jī)是一個(gè)會(huì)對(duì)輸入信息進(jìn)行變換給出輸出信息的系統(tǒng)。比如前面說(shuō)的小蟲，紙帶上的一個(gè)方格一個(gè)方格的顏色信息就是對(duì)小蟲的輸入，而小蟲所采取的行動(dòng)就是它的輸出。不過(guò)這么看，你會(huì)發(fā)現(xiàn)，似乎小蟲的輸出太簡(jiǎn)單了。因?yàn)樗鼉H僅就有那么幾種簡(jiǎn)單的輸出動(dòng)作。然而，不要忘了，復(fù)雜性來(lái)源于組合！雖然每一次小蟲的輸出動(dòng)作很簡(jiǎn)單，然而當(dāng)把所有這些輸出動(dòng)作組合在一起，就有可能非常復(fù)雜！比如我們可以把初始時(shí)刻的紙帶看作是輸入信息，那么經(jīng)過(guò)任意長(zhǎng)的時(shí)間比如說(shuō)100年后，小蟲通過(guò)不斷的涂抹紙帶最后留下的信息就是輸出信息了。那么小蟲完成的過(guò)程就是一次計(jì)算。事實(shí)上，在圖靈機(jī)的正規(guī)定義中，存在一個(gè)所謂的停機(jī)狀態(tài)，當(dāng)圖靈機(jī)一到停機(jī)狀態(tài)，我們就認(rèn)為它計(jì)算完畢了，因而不用費(fèi)勁的等上100年。我們自然可以通過(guò)組合若干圖靈機(jī)完成更大更多的計(jì)算，如果把一個(gè)圖靈機(jī)對(duì)紙帶信息變換的結(jié)果又輸入給另一臺(tái)圖靈機(jī)，然后再輸入給別的圖靈機(jī)……，這就是把計(jì)算進(jìn)行