圖靈機:通用計算機模型-中文百科頻道

概述

英國數學家A.M.圖靈提出的一種抽象計算模型，用來精确定義可計算函數。圖靈機由一個控制器、一條可無限延伸的帶子和一個在帶子上左右

移動的讀寫頭組成。這個在概念上如此簡單的機器，理論上卻可以計算任何直觀可計算的函數。圖靈機作為計算機的理論模型，在有關計算理論和計算複雜性的研究方面得到廣泛的應用。

研究簡況

由于圖靈機以簡明直觀的數學概念刻劃了計算過程的本質，自1936年提出以來，有關學者對它進行了廣泛的研究。C.E.仙農證明每一個圖靈機等價于僅有兩個内部狀态的圖靈機，王浩證明每個圖靈機可由具有一條隻讀帶和一條隻有兩個符号的存儲帶的圖靈機模拟。人們還證明，圖靈機與另一抽象計算模型──波斯特機器在計算能力上是等價的（見波斯特對應問題）。

人們還研究了圖靈機的各種變形，如非确定的圖靈機、多道圖靈機、多帶圖靈機、多維圖靈機、多頭圖靈機和帶外部信息源的圖靈機等。除極個别情形外，這些變形并未擴展圖靈機的計算能力，它們計算的函數類與基本圖靈機是相同的，但對研究不同類型的問題提供了方便的理論模型。例如，多帶圖靈機是研究計算複雜性理論的重要計算模型。人們還在圖靈機的基礎上提出了不同程度地近似于現代計算機的抽象機器，如具有随機訪問存儲器的程序機器等。

基本結構和功能

圖靈機的控制器具有有限個狀态。其中有兩類特殊狀态：開始狀态和結束狀态（或結束狀态集合）。圖靈機的帶子分成格子，右端可無限延伸，每個格子上可以寫一個符号，圖靈機有有限個不同的符号。圖靈機的讀寫頭可以沿着帶子左右移動，既可掃描符号，也可寫下符号。

在計算過程的每一時刻，圖靈機處于某個狀态，通過讀寫頭注視帶子某一格子上的符号。根據當前時刻的狀态和注視的符号，機器執行下列動作：轉入新的狀态；把被注視的符号換成新的符号；讀寫頭向左或向右移動一格。這種由狀态和符号對偶決定的動作組合稱為指令。例如指令q1ailajq2L表示當機器處在狀态q1下注視符号ai時,将ai換成符号aj,轉入新的狀态q2,讀寫頭左移一格。決定機器動作的所有指令表稱為程序。結束狀态或指令表中沒有的狀态、符号對偶，将導緻停機。

在每一時刻，機器所處狀态、帶子上已被寫上符号的所有格子以及機器當前注視的格子位置，統稱為機器的格局。圖靈機從初始格局出發，按程序一步步把初始格局改造為格局的序列。此過程可能無限制繼續下去，也可能遇到指令表中沒有列出的狀态、符号組合或進入結束狀态而停機。在結束狀态下停機所達到的格局是最終格局，此最終格局(如果存在)就包含機器的計算結果。

接受語言

圖靈機（簡記為T）可作為接受語言的裝置,它所接受的語言L恰是所有這樣的符号串ω的集合：如果把符号串ω記錄在T的帶子上,開始工作時T處于初始狀态q0，讀寫頭處于帶子最左端,則經過有限步之後，T進入某個結束狀态q。被圖靈機接受的語言類也就是遞歸可枚舉集，或O型語言（見形式語言理論）。

産生語言

圖靈機作為語言的産生裝置，它在帶子上枚舉出該語言中所有的字。如果這個語言是無限的，這個枚舉過程就是無窮的。圖靈機産生的語言恰是遞歸可枚舉集。圖靈機按字長增長的順序産生的語言，恰是遞歸集。

計算函數

設機器帶子上的輸入符号串為自然數n的編碼。如果機器從這樣的帶子出發,到達結束狀态時，帶子上符号串已改造為m的編碼,則稱機器計算了函數f(n)=m。如果一個函數以自然數為值域和定義域，并且有一個圖靈機計算它，則稱此函數為“可計算函數“。

由于圖靈機的帶子是可以向右無限延伸的，所以圖靈機的存儲空間和計算時間都是可無限制增加的。因此，圖靈機是一般算法概念的精确化，即任何算法均可由适當的圖靈機模拟。人們尚未發現一個直觀可以計算的函數不能由圖靈機來計算。而且，已有的關于直觀可計算函數的另一些精确化定義，如遞歸函數、λ可定義函數等，都等價于圖靈機定義的可計算函數。

通用圖靈機

已經證明，存在一個圖靈機U,它可以模拟任何其他的圖靈機T,這樣的U稱為通用圖靈機。U的帶子上記錄着被模拟機器T的指令描述，也記錄着T的問題數據。在工作過程中，U根據輸入帶上記錄的T的指令，模拟T的動作，處理問題的數據。這樣，U可以模拟任何計算過程。