832
《計算機科學導論》一1.1 圖靈模型
本節書摘來異步社區《計算機科學導論》一書中的第1章 ，第1.1節，［美］貝赫魯茲A. 佛羅讚（Behrouz A. Forouzan）著 劉藝劉哲雨等譯, 更多章節內容可以訪問雲棲社區“異步社區”公眾號查看。
1.1 圖靈模型
Alan Turing（阿蘭·圖靈）在1937年首次提出了一個通用計算設備的設想。他設想所有的計算都可能在一種特殊的機器上執行，這就是現在所說的圖靈機。盡管圖靈對這樣一種機器進行了數學上的描述，但他還是更有興趣關注計算的哲學定義，而不是建造一台真實的機器。他將該模型建立在人們進行計算過程的行為上，並將這些行為抽象到用於計算的機器的模型中，這才真正改變了世界。
1.1.1 數據處理器
在討論圖靈模型之前，讓我們把計算機定義成一個數據處理器。依照這種定義，計算機就可以被看作是一個接受輸入數據、處理數據並產生輸出數據的黑盒（如圖1-1所示）。盡管這個模型能夠體現現代計算機的功能，但是它的定義還是太寬泛。按照這種定義，也可以認為便攜式計算器是計算機（按照字麵意思，它也符合定義的模型）。
另一個問題是這個模型並沒有說明它處理的類型以及是否可以處理一種以上的類型。換句話說，它並沒有清楚地說明基於這個模型的機器能夠完成操作的類型和數量。它是專用機器還是通用機器呢？
這種模型可以表示為一種設計用來完成特定任務的專用計算機（或者處理器），比如用來控製建築物溫度或汽車油料使用。盡管如此，計算機作為一個當今使用的術語，是一種通用的機器，它可以完成各種不同的工作。這表明我們需要將該模型改變為圖靈模型來反映當今計算機的現實。
1.1.2 可編程數據處理器
圖靈模型是一個適用於通用計算機的更好模型。該模型添加了一個額外的元素—程序到不同的計算機器中。程序是用來告訴計算機對數據進行處理的指令集合。圖1-2顯示了圖靈模型。
在這個圖靈模型中，輸出數據是依賴兩方麵因素的結合作用：輸入數據和程序。對於相同的數據輸入，如果改變程序，則可以產生不同的輸出。類似地，對於同樣的程序，如果改變輸入數據，其輸出結果也將不同。最後，如果輸入數據和程序保持不變，輸出結果也將不變。讓我們看看下麵三個示例。
1.相同的程序，不同的輸入數據
圖1-3顯示了對於同樣的程序輸入不同的數據時，盡管程序相同，但因為處理的輸入數據不同，輸出也就不同。
2. 相同的輸入數據，不同的程序
圖1-4顯示了對於不同的程序輸入相同的數據時的情形。每個程序使計算機對相同的輸入數據執行不同的操作。第一個程序是使輸入數據按大小順序排列，第二個程序是使所有的數據相加，第三個程序是找出輸入數據中最小的數。
3.相同的輸入數據，相同的程序
我們希望無論何時對於同樣的輸入數據和程序，其輸出結果一致。換句話說，當程序在輸入相同的數據運行時，我們希望有相同的輸出。
1.1.3 通用圖靈機
通用圖靈機是對現代計算機的首次描述，該機器隻要提供了合適的程序就能做任何運算。可以證明，一台很強大的計算機和通用圖靈機一樣能進行同樣的運算。我們所需要的僅僅是為這兩者提供數據以及用於描述如何做運算的程序。實際上，通用圖靈機能做任何可計算的運算。
最後更新：2017-06-21 15:32:10