發明者
1936年，艾倫·圖靈(1912-1954)提出了一種抽象的計算模型——圖靈機(TuringMachine）。
概述
圖靈機英國數學家A.M.圖靈提出的一種抽象計算模型，用來精確定義可計算函式。圖靈機由一個控制器、一條可無限延伸的帶子和一個在帶子上左右移動的讀寫頭組成。這個在概念上如此簡單的機器，理論上卻可以計算任何直觀可計算的函式。圖靈機作為計算機的理論模型，在有關計算理論和計算複雜性的研究方面得到廣泛的套用。
研究簡況
由於圖靈機以簡明直觀的數學概念刻劃了計算過程的本質，自1936年提出以來，有關學者對它進行了廣泛的研究。C.E.仙農證明每一個圖靈機等價於僅有兩個內部狀態的圖靈機，王浩證明每個圖靈機可由具有一條唯讀帶和一條只有兩個符號的存儲帶的圖靈機模擬。人們還證明，圖靈機與另一抽象計算模型──波斯特機器在計算能力上是等價的（見波斯特對應問題）。
人們還研究了圖靈機的各種變形，如非確定的圖靈機、多道圖靈機、多帶圖靈機、多維圖靈機、多頭圖靈機和帶外部信息源的圖靈機等。除極個別情形外，這些變形並未擴展圖靈機的計算能力，它們計算的函式類與基本圖靈機是相同的，但對研究不同類型的問題提供了方便的理論模型。例如，多帶圖靈機是研究計算複雜性理論的重要計算模型。人們還在圖靈機的基礎上提出了不同程度地近似於現代計算機的抽象機器，如具有隨機訪問存儲器的程式機器等。
基本結構和功能
圖靈機的控制器具有有限個狀態。其中有兩類特殊狀態：開始狀態和結束狀態（或結束狀態集合）。圖靈機的帶子分成格子，右端可無限延伸，每個格子上可以寫一個符號，圖靈機有有限個不同的符號。圖靈機的讀寫頭可以沿著帶子左右移動，既可掃描符號，也可寫下符號。
圖靈機在計算過程的每一時刻，圖靈機處於某個狀態，通過讀寫頭注視帶子某一格子上的符號。根據當前時刻的狀態和注視的符號，機器執行下列動作：轉入新的狀態；把被注視的符號換成新的符號；讀寫頭向左或向右移動一格。這種由狀態和符號對偶決定的動作組合稱為指令。例如指令q1ai│ajq2L表示當機器處在狀態q1下注視符號ai時,將ai換成符號aj,轉入新的狀態q2,讀寫頭左移一格。決定機器動作的所有指令表稱為程式。結束狀態或指令表中沒有的狀態、符號對偶，將導致停機。
在每一時刻，機器所處狀態、帶子上已被寫上符號的所有格子以及機器當前注視的格子位置，統稱為機器的格局。圖靈機從初始格局出發，按程式一步步把初始格局改造為格局的序列。此過程可能無限制繼續下去，也可能遇到指令表中沒有列出的狀態、符號組合或進入結束狀態而停機。在結束狀態下停機所達到的格局是最終格局，此最終格局(如果存在)就包含機器的計算結果。
圖靈機接受語言
圖靈機（簡記為 T）可作為接受語言的裝置,它所接受的語言L恰是所有這樣的符號串ω的集合：如果把符號串ω記錄在T的帶子上,開始工作時T處於初始狀態q0，讀寫頭處於帶子最左端,則經過有限步之後，T進入某個結束狀態q。被圖靈機接受的語言類也就是遞歸可枚舉集，或 O型語言（見形式語言理論）。
圖靈機產生語言
圖靈機作為語言的產生裝置，它在帶子上枚舉出該語言中所有的字。如果這個語言是無限的，這個枚舉過程就是無窮的。圖靈機產生的語言恰是遞歸可枚舉集。圖靈機按字長增長的順序產生的語言，恰是遞歸集。
圖靈機計算函式
設機器帶子上的輸入符號串為自然數n的編碼。如果機器從這樣的帶子出發,到達結束狀態時，帶子上符號串已改造為m的編碼,則稱機器計算了函式f(n)=m。如果一個函式以自然數為值域和定義域，並且有一個圖靈機計算它，則稱此函式為“可計算函式“。
由於圖靈機的帶子是可以向右無限延伸的，所以圖靈機的存儲空間和計算時間都是可無限制增加的。因此，圖靈機是一般算法概念的精確化，即任何算法均可由適當的圖靈機模擬。人們尚未發現一個直觀可以計算的函式不能由圖靈機來計算。而且，已有的關於直觀可計算函式的另一些精確化定義，如遞歸函式、λ可定義函式等，都等價於圖靈機定義的可計算函式。
形式化
一台圖靈機是一個七元組，{Q，Σ，Γ，δ，q0,qaccept,qreject}，其中Q，Σ，Γ都是有限集合，且滿足
1.Q是狀態集合；
2.Σ是輸入字母表，其中不包含特殊的空白符□；
3.Γ是帶字母表，其中□∈Γ且Σ∈Γ；
4.δ：Q×「→Q×Γ×{L,R}是轉移函式，其中L,R表示讀寫頭是向左移還是向右移；
5.q0∈Q是起始狀態；
6.qaccept是接受狀態。
7.qreject是拒絕狀態，且。qreject≠qaccept
圖靈機M=(Q，Σ，Γ，δ，q0,qaccept,qreject)將以如下方式運作：
開始的時候將輸入符號串從左到右依此填在紙帶的第號格子上，其他格子保持空白（即填以空白符）。M的讀寫頭指向第0號格子，M處於狀態q0。機器開始運行後，按照轉移函式δ所描述的規則進行計算。例如，若當前機器的狀態為q，讀寫頭所指的格子中的符號為x，設δ（q,x)=(q',x',L），則機器進入新狀態q'，將讀寫頭所指的格子中的符號改為x'，然後將讀寫頭向左移動一個格子。若在某一時刻，讀寫頭所指的是第0號格子，但根據轉移函式它下一步將繼續向左移，這時它停在原地不動。換句話說，讀寫頭始終不移出紙帶的左邊界。若在某個時刻M根據轉移函式進入了狀態qaccept，則它立刻停機並接受輸入的字元串；若在某個時刻M根據轉移函式進入了狀態qreject，則它立刻停機並拒絕輸入的字元串。
注意，轉移函式δ是一個部分函式，換句話說對於某些q,x，δ（q,x)可能沒有定義，如果在運行中遇到下一個操作沒有定義的情況，機器將立刻停機。
通用圖靈機
已經證明，存在一個圖靈機U,它可以模擬任何其他的圖靈機T,這樣的U稱為通用圖靈機。U的帶子上記錄著被模擬機器T的指令描述，也記錄著T的問題數據。在工作過程中，U根據輸入帶上記錄的T的指令，模擬T的動作，處理問題的數據。這樣，U可以模擬任何計算過程。
停機問題
圖靈機根據機器的程式處理初始格局。有的初始格局可能導致停機，有的則導致無限的格局序列。停機問題是：是否存在一個算法，對於任意給定的圖靈機都能判定任意的初始格局是否會導致停機。已經證明，這樣的算法是不存在的，即停機問題是不可判定的。
停機問題是研究許多不可判定問題的基礎，人們往往把一個問題的判定歸結為停機問題：“如果問題 A可判定，則停機問題可判定。”從而證明問題 A的不可判定性。停機問題有多種不同的敘述方式和證明方法，它們分別適用於具有不同特徵的問題。
可計算性
圖靈可識別語言圖靈可判定語言遞歸可枚舉語言可計算函式遞歸函式停機問題可判定性不可判定性等價機器
除了圖靈機以外，人們還發明了很多其它的計算模型。包括：暫存器機遞歸函式λ演算生命遊戲馬爾可夫算法然而這些模型無一例外地都和圖靈機的計算能力等價，因此邱奇，圖靈和哥德爾提出了著名的邱奇-圖靈論題：一切直覺上能行可計算的函式都可用圖靈機計算，反之亦然。
