註意，枚舉器E可以以任意順序枚舉語言L(E)，L(E)中的壹個字符串可能會被E多次重復打印。
圖靈可識別語言的定義:設M是圖靈機。如果M在輸入串ω上運行後能進入接受狀態並停止，則稱為M接受串ω。M接受的所有字符串的集合稱為M識別的語言，簡稱L(M)。
集s？σ *是壹種語言。如果有壹個圖靈機M使得L(M)=S，就說圖靈機M識別S，S稱為圖靈可識別語言。
下面的定理揭示了遞歸可枚舉語言和圖靈可識別語言之間的關系。
定理:壹種語言是圖靈可識別的當且僅當它是遞歸可枚舉的。
證明:如果有枚舉器E枚舉語言S，構造壹個圖靈機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，在輸入W下，程序P最終能停止(而不是進入無限循環)嗎？
用數學語言描述，其本質問題是:給定壹個圖靈機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也是遞歸語言。