註意，枚舉器E可以以任意的順序枚舉語言L（E），而且L（E） 中的某個串可能會被E多次重復地打印。
圖靈可識別語言定義：設 M是壹臺圖靈機，若在輸入串ω上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是圖靈可判定語言，既 遞歸(Recursive)語言 ，則必須存在圖靈機M，使得對於任意輸入串ω ? Σ*，M 總能停機 ，並根據ω屬於或不屬於S分別進入接受或拒絕狀態。
並不是所有的語言都是圖靈可識別的，可以證明存在圖靈不可識別語言。
停機問題就是判斷任意壹個程序是否會在有限的時間之內結束運行的問題。
該問題等價於如下的判定問題：給定壹個程序P和輸入w，程序P在輸入w下是否能夠最終停止（而不是進入無限循環）。
用數學語言描述，則其本質問題為: 給定壹個圖靈機T，和壹個任意語言集合S，是否T會最終停機於每壹個ω ∈ S。其意義相同於可確定語言。顯然任意有限 S 是可判定性的，可數的（countable）S 也是可停機的。
艾倫·圖靈在1936年用對角論證法證明了，不存在解決停機問題的通用算法。
邱奇-圖靈論題認為“任何在 算法 上可計算的問題同樣可由圖靈機計算”
另外壹種說法就是邏輯和數學中的有效或機械方法可由圖靈機來表示。通常我們假定這些方法必須滿足以下的要求：
1.壹個方法由有限多簡單和精確的指令組成，這些指令可由有限多的符號來描述。
2.該方法總會在 有限的 步驟內產生出壹個結果。
3.基本上人可以僅用紙張和鉛筆來執行。
4.該方法的執行 不需人類的智慧 來理解和執行這些指令。
此類方法的壹個範例便是用歐幾裏得輾轉相除法確定兩個自然數的最大公約數。
設當前有遞歸語言 L，其可接納的字符串集為 Σ。求證：L的補集：Σ*\L 也為遞歸語言。
證明過程：
因為L是遞歸語言，則存在壹臺圖靈機M1，能夠完成：
1.當且僅當ω ∈ Σ*且 ω ∈ L 時， 接受 輸入串ω並總能進入停機狀態，該停機狀態為 最終態 。
2.當且僅當ω ∈ Σ* 且 ω ? L 時， 拒絕 輸入串ω並總能進入停機狀態，該停機狀態為 非最終態。
現在通過將M1的最終態與非最終態互換（原本的非最終態變為最終態，最終態變為非最終態），構造另壹臺圖靈機M2。則M2能夠完成：
1.當且僅當ω ∈ Σ*且 ω ∈ Σ*\L 時， 接受 輸入串ω並總能進入停機狀態，該停機狀態為 最終態 。
2.當且僅當ω ∈ Σ* 且 ω ? Σ*\L 時， 拒絕 輸入串ω並總能進入停機狀態，該停機狀態為 非最終態。
故M1拒絕的輸入將被M2接受，M1接受的輸入將被M2拒絕。
則M2恰好接受 Σ*\L ， 即 Σ*\L 也為遞歸語言。