2.2　所有計算機的同一祖宗——圖靈機

艾倫·圖靈是第一個提出制造一種簡單的計算機想法的人。圖靈機的操作僅局限于讀寫磁帶上的符號，將磁帶移向左邊或右邊來一次讀取一個符號。這個發明常被認為是計算機時代的開端。

實際上，“可計算的”一詞的定義是一個可以由圖靈機來解決的問題。圖靈機還在翻譯和破解用恩尼格碼密碼機寫碼的德國信息方面起著很大作用。

前面提到過，艾倫·圖靈寫了一篇名為《論可計算書機器判定問題上的應用》的論文，這就是艾倫·圖靈享譽世界很重要的論文之一。可能當時連他也不會想到，這篇文章中所提到的概念最終使他從數學和邏輯學系統中開辟出一個全新的分支——計算機。

1. 圖靈機的概念

接下來介紹一下圖靈機的概念（值得注意的是，圖靈機只是一個概念，并不是一個實體機器）。

圖靈機的基本思想如圖2-3所示，圖靈機由一條無限長的紙帶（tape）、讀寫頭（head）、一套控制讀寫頭移動規則的規則表（table）和一個狀態寄存器（register）組成。

艾倫·圖靈的基本思想是用機器模擬人們用紙和筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作。

（1）在紙上寫上或擦除某個符號。

（2）把注意力從紙的一個位置移到另一個位置。

而在每個階段，人要決定下一步的動作，依賴于：①此人當前所關注的紙上某個位置的符號；②此人當前思維的狀態。

2. 圖靈機的運算過程

為了模擬人的這種運算過程，艾倫·圖靈構造出一臺假想的機器，該機器由以下幾個部分組成。

（1）一條無限長的紙帶，如圖2-4所示。

紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號表示空白。紙帶上的格子從左到右依此被編號為0、1、2等，紙帶的右端可以無限伸展。

（2）一個讀寫頭。

讀寫頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，并能改變當前格子上的符號。

（3）一套控制規則表。

控制規則根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號確定讀寫頭下一步的動作，并改變狀態寄存器中的值，令機器進入一個新的狀態。

（4）一個狀態寄存器。

狀態寄存器用來保存圖靈機當前所處的狀態。圖靈機的所有可能狀態的數目是有限的，并且有一個特殊的狀態，稱為停機狀態。

注意：這個機器的每一部分都是有限的，但它有一個潛在的無限長的紙帶，因此，這種機器只是一個理想的設備。艾倫·圖靈認為這樣的一臺機器就能模擬人類所能進行的任何計算過程。

圖2-5中所示紙帶被分為無限個格子，可記錄任何字母、二進制數字（0，1）及空白。每個格子里代表了圖靈機的輸入和輸出信息，空白則表示沒有任何信息。下方三角為讀寫頭，表示當前讀寫（輸入輸出）的位置。讀寫頭可向左右移動，每次移動一個格。

在某些模型中，讀寫頭沿著固定的紙帶移動。要進行的指令（q₁）展示在讀寫頭內。在這種模型中“空白”的紙帶全部為0。有陰影的方格，包括讀寫頭掃描到的空白，標記了“1，1，B”的那些方格，以及讀寫頭符號，構成了系統狀態。

其移動方向由當下讀寫頭所指的輸入和規則表決定（規則表其實就是當時控制計算機的程序）。讀寫頭首先記錄下當下位置的狀態（q₁）并存入狀態寄存器，然后根據當下輸入對比程序中的要求進行左右移動或停留在當下位置，最后根據程序輸出字母或數字，修改新位置的數字或字母。每次工作圖靈機的讀寫頭都會從起始位置開始，由規則表和輸入控制其移動到不同位置，并最終在程序結束時停留在空白格里。

3. 圖靈機的意義

細心的讀者會發現，圖靈機的整個構想已經滿足現代計算機所需要的所有基本元素，包括程序、輸入輸出和存儲器、如圖2-6所示。

這也是為什么說圖靈機奠定了現代計算機發展的基礎。因為現在計算機能做的一切事情圖靈機都可以做到（圖靈機的具體工作示例會在后面慢慢提到）。