註意，枚舉器E可以以任何順序枚舉語言L（E），L（E）中的壹個字符串可能會被E重復打印多次。
圖靈可識別語言的定義:設M為圖靈機。如果M在輸入字符串ω上運行後可以進入接受狀態並停止，則稱為M接受字符串ω。M接受的所有字符串的集合稱為M識別的語言，簡稱L（M）。
設定s？σ *是壹種語言。如果有壹個圖靈機M使得L（M）= S，則稱圖靈機M識別S，S稱為圖靈可識別語言。
以下定理揭示了遞歸可枚舉語言和圖靈可識別語言之間的關系。
定理:壹種語言是圖靈可識別的當且僅當它是遞歸可枚舉的。
證明:如果有枚舉語言S的枚舉器E，構造壹個圖靈機M如下:
M =對於輸入ω
運行E生成字符串S1，S2，...；
如果遇到某個Si =ω，它將進入接受狀態並停止。
註意是ω？S，M可能永遠不會停止，但是M接受的單詞集恰好是S，所以M識別S..
假設我們有圖靈機M識別語言S，並如下構造壹個枚舉器E:
E =忽略輸入。
對於i = 1，2，3，重復以下步驟...；
設σ * = {S1，S2，...}，分別取s1、s2、...，si作為M的輸入，並模擬M以執行步驟I；
如果某個sj，1 ≤ j ≤ i，能被步驟I中的M接受，則輸出它。
顯然，以這種方式構造的枚舉器E的最終輸出語言恰好是S .註意，S中的字符串在E中不是按字典順序輸出的，同壹字符串可能會被E多次輸出，但根據枚舉器的定義，這些都是允許的。
註意圖靈可識別語言和圖靈可確定語言的區別:如果S是圖靈可識別語言，則只有壹個圖靈機M，當M輸入ω ∈ S時，M肯定會停止並進入接受狀態；當m的輸入ω？s、M可能會停止並進入拒絕狀態，或者永遠不會停止。
但是，如果S是圖靈可判定語言，即遞歸語言，則壹定存在圖靈機M，這樣對於任何輸入字符串ω？σ *，m可以壹直停著，根據ω是否屬於S進入接受或拒絕狀態。
並不是所有的語言都是圖靈可識別的，這可以證明圖靈不可識別語言的存在。
停機問題是判斷任何程序是否會在有限的時間內結束運行。
這個問題等價於下面的判斷題:給定壹個程序P和壹個輸入W，程序P能否在輸入W下最終停止（而不是進入無限循環）？
用數學語言描述，它的本質問題是:給定壹個圖靈機T和壹個任意語言集S，T最終會停在每個ω ∈ S嗎？其含義與可確定語言的含義相同。顯然，任何有限的S都是可確定的，而可數的S也是可停止的。
艾倫·圖靈在1936中證明了不存在解決關機問題的通用算法。
丘奇-圖靈論點認為“任何算法上可計算的問題也可以用圖靈機計算”
另壹種說法是邏輯和數學中有效的或機械的方法可以用圖靈機來表示。通常我們假設這些方法必須滿足以下要求:
1.方法由有限數量的簡單而精確的指令組成，這些指令可以用有限數量的符號來描述。
2.這種方法總是在有限的步驟中產生結果。
3.基本上，人們只能用紙和鉛筆來完成它。
4.這種方法的實現不需要人類的智慧來理解和執行這些指令。
這種方法的壹個例子是通過歐幾裏德除法確定兩個自然數的最大公約數。
假設有壹種遞歸語言L，其可接受的字符串集為σ。驗證:l: σ * \ l的補集也是遞歸語言。
證明過程:
因為L是遞歸語言，所以有壹個圖靈機M1，它可以完成:
1.當且僅當ω∈σ*andl時，輸入字符串ω被接受並始終進入關機狀態，這是最終狀態。
2.當且僅當ω ∈ σ *和ω？l，輸入字符串ω被拒絕並始終進入關閉狀態，這是非最終狀態。
現在，通過交換M1的最終狀態和非最終狀態（原始非最終狀態成為最終狀態，最終狀態成為非最終狀態）來構造另壹個圖靈機M2。M2可以完成:
1.當且僅當ω∈σ*andσ* \ l時，輸入字符串ω被接受並始終進入關機狀態，這是最終狀態。
2.當且僅當ω ∈ σ *和ω？σ* \ L，輸入字符串ω被拒絕，它可以始終進入關閉狀態，這是非最終狀態。
因此，被M1拒絕的輸入將被M2接受，而被M1接受的輸入將被M2拒絕。
M2只接受σ * \ l，也就是說σ * \ l也是壹種遞歸語言。