- 什么是圖靈測試_圖靈機的工作原理詳解

圖靈機的工作原理詳解

關(guān)于圖靈機背景

圖靈機的歷史發(fā)展 圖靈機被公認(rèn)為現(xiàn)代計算機的原型，這臺機器可以讀入一系列的零和一，這些數(shù)字代表了解決某一問題所需要的步驟，按這個步驟走下去，就可以解決某一特定的問題。這種觀念在當(dāng)時是具有革命性意義的，因為即使在50年代的時候，大部分的計算機還只能解決某一特定問題，不是通用的，而圖靈機從理論上卻是通用機。

圖靈機的產(chǎn)生一方面奠定了現(xiàn)代數(shù)字計算機的基礎(chǔ)（要知道后來馮?諾依曼就是根據(jù)圖靈的設(shè)想才設(shè)計出第一臺計算機的）。另一方面，根據(jù)圖靈機這一基本簡潔的概念，我們還可以看到可計算的極限是什么。也就是說實際上計算機的本領(lǐng)從原則上講是有限制的。請注意，這里說到計算機的極限并不是說它不能吃飯、掃地等硬件方面的極限，而是僅僅就從信息處理這個角度，計算機也仍然存在著極限。這就是圖靈機的停機問題。

圖靈機原理及分析

? ? ? ?圖靈的基本思想是用機器來模擬人們用紙筆進行數(shù)學(xué)運算的過程，他把這樣的過程看作下列兩種簡單的動作： １）在紙上寫上或擦除某個符號； ２） 把注意力從紙的一個位置移動到另一個位置； 而在每個階段，人要決定下一步的動作，依賴于 （a） 此人當(dāng)前所關(guān)注的紙上某個位置的符號和（b） 此人當(dāng)前思維的狀態(tài)。為了模擬人的這種運算過程，圖靈構(gòu)造出一臺假想的機器，該機器由以下幾個部分組成：

一條無限長的紙帶。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號 表示空白。紙帶上的格子從左到右依此被編號為 0， 1， 2， 。.. ，紙帶的右端可以無限伸展。 一個讀寫頭。該讀寫頭可以在紙帶上左右移動，它能讀出當(dāng)前所指的格子上的符號，并能改變當(dāng)前格子上的符號。 一個狀態(tài)寄存器。它用來保存圖靈機當(dāng)前所處的狀態(tài)。圖靈機的所有可能狀態(tài)的數(shù)目是有限的，并且有一個特殊的狀態(tài)，稱為停機狀態(tài)。

一套控制規(guī)則。它根據(jù)當(dāng)前機器所處的狀態(tài)以及當(dāng)前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，并改變狀態(tài)寄存器的值，令機器進入一個新的狀態(tài)。 這個機器的每一部分都是有限的，但它有一個潛在的無限長的紙帶，因此這種機器只是一個理想的設(shè)備。圖靈認(rèn)為這樣的一臺機器就能模擬人類所能進行的任何計算過程 下面我們用另一種思想來理解圖靈機： 注：以下內(nèi)容來自百度文庫： 小蟲的比喻：我們不妨考慮這樣 一個問題。假設(shè)一個小蟲在地上爬，那么我們應(yīng)該怎樣從小蟲信息處理的角度來建立它的模型呢？

? ? ? ?首先， 我們需要對小蟲所在的環(huán)境進行建模。我們不妨假設(shè)小蟲所處的世界是一個無限長的紙帶，這個紙帶上被分成了若干小方格，而每個方格都只有黑白兩種顏色。黑色表示該方格有食物，白色就表示沒有。假設(shè)小蟲僅具有一個感覺器官：眼睛，而且它的視力差得可憐， 也就是說它僅僅能夠感受到它所處的方格的顏色。因而這個方格所在的位置的黑色或者白色的信息就是小蟲的輸入信息。其次， 小蟲有輸出動作，它可以在方格上前移，后移，還可以涂寫方格成黑色或者白色。最后，小蟲還會有兩種內(nèi)部狀態(tài)，即{饑餓，吃飽}。這樣小蟲的行動按照下面的程序進行：

程序：

輸入? 當(dāng)前內(nèi)部狀態(tài)? ? ?輸出? ? ?下時刻的內(nèi)部狀態(tài)

黑? ?饑餓? ? ?涂白? ? 吃飽

黑? ?吃飽? ? ?后移? ? 饑餓

白? ?饑餓? ? ? 涂黑? ? 饑餓

白? ? 吃飽? ? ?前移? ? 吃飽

即如果當(dāng)前處于饑餓狀態(tài)，則有食物就吃掉，沒有食物就“吐出食物”；如果當(dāng)前處于吃飽的狀態(tài)，則如果沒有食物就前移，如果有就后退，并且轉(zhuǎn)入饑餓狀態(tài)。那么當(dāng)小蟲子讀入黑白白黑白??這樣的紙帶的時候， 會怎樣行動呢？小蟲用圓圈表示，它從最左邊開始 移動，灰色表示饑餓狀態(tài)，白色表示吃飽狀態(tài)。 箭頭表示移動的方向。從上到下，小蟲一步一步 地根據(jù)紙帶的顏色和它自己的內(nèi)部狀態(tài)查

找規(guī)則表中的對應(yīng)項而采取行動。例如第 5 步讀入方格是黑色，內(nèi)部狀態(tài)為吃飽，根據(jù)這兩項輸入信息查找規(guī)則表找到對應(yīng)項是第二項，根據(jù)小蟲應(yīng)該后移，且內(nèi)部狀態(tài)變?yōu)轲囸I。不難看到，到 了第 8 步，情況跟第4步完全相同，輸入都是白色紙帶和饑餓狀態(tài)，根據(jù)程序，小蟲將重復(fù)4－8之間的動作，并一直持續(xù)下去??。盡管從長期來看，小蟲會落入機械的循環(huán)，然而當(dāng)你輸入給小蟲白色信息的時候，它的反應(yīng)可能完全不同 （如第 4 步和第 6 步的行為） 所以 ，只要小蟲子的內(nèi)部狀態(tài)和程序非常復(fù)雜，那么小蟲的行為也會越來越超出你的想象！ 相信你 已經(jīng)明白了這個小蟲模型，那么你就掌握了圖靈機的工作原理，因為從本質(zhì)上講，這個小蟲模型就是一臺圖靈機。 圖靈機是一個會對輸入信息進行變換給出輸出信息的系統(tǒng)。比如前面說的小蟲，紙帶上的一個方格一個方格的顏色信息就是對小蟲的輸入，而小蟲所采取的行動就是它的輸出。不過這么看，你會發(fā)現(xiàn)，似乎小蟲的輸出太簡單了。因為它僅僅就有那么幾種簡單的輸出動作。然而，不要忘了，復(fù)雜性來源于組合！雖然每一次小蟲的輸出動作很簡單，然而當(dāng)把所有這些輸出動作組合在一起，就有可能非常復(fù)雜！比如我們可以把初始時刻的紙帶看作是輸入信息，那么經(jīng)過任意長的時間比如說100年后，小蟲通過不斷的涂抹紙帶最后留下的信息

就是輸出信息了。那么小蟲完成的過程就是一次計算。事實上，在圖靈機的正規(guī)定義中，存在一個所謂的停機狀態(tài)，當(dāng)圖靈機一到停機狀態(tài)，我們就認(rèn)為它計算完畢了，因而不用費勁的等上100年。 我們自然可以通過組合若干圖靈機完成更大更多的計算，如果把一個圖靈機對紙帶信息變換的結(jié)果又輸入給另一臺圖靈機，然后再輸入給別的圖靈機??，這就是把計算進行了組合。也許你還在為前面說的無限多的內(nèi)部狀態(tài)，無限復(fù)雜的程序而苦惱，那么到現(xiàn)在，你不難明白，實際上我們并不需要寫出無限復(fù)雜的程序列表，而僅僅將這些圖靈機組合到一起就可以產(chǎn)生復(fù)雜的行為了。