可計算性和複雜性/可計算性/可判定性
本節討論在圖靈機 (TM) 上執行的問題的可判定性。有關圖靈機的定義，請參見無限制語言.
對於那些存在圖靈機能夠在有限時間內始終停止並接受語言中任何字串的語言，稱為圖靈可識別語言。請注意，並非必須能夠製作一臺機器來停止並拒絕所有不在語言中的字串 - 機器可能會迴圈。繼續前面的示例，由所有 {給出如何生成和列印有限小數位數的數字的指令（使用某些特定編碼）的字串} 組成的語言是圖靈可識別的。如果機器收到正確的輸入，它可以遵循指令，列印數字，完成並接受。如果它收到沒有意義的指令，它可以拒絕。但如果它收到看起來正確的指令，並按照這些指令進行，它將永遠執行。
對於某些語言，可以編寫圖靈機，該圖靈機可以在所有輸入上停止，要麼接受要麼拒絕。這些語言稱為可判定語言，總是停止在任何輸入上的 TM 稱為判定器。可判定語言的一個例子是其單詞由一個字串化的 LBA 和一個輸入字串組成的語言，其中 LBA 在該輸入上停止。可以編寫一個 TM 來模擬 LBA，記錄它執行的步驟數，如果它接受則接受，如果它拒絕則拒絕，如果它超過了某個步驟數則拒絕（該步驟數是多少以及它是如何保證 LBA 將永遠迴圈的，在關於 上下文敏感語言 的章節中解釋）。根據定義，所有可判定語言也是圖靈可識別的。
對於 TM，也許最重要的不可判定問題被稱為停機問題。通用圖靈機 (UTM) 無法始終準確地預測給定的 TM 在給定輸入上是否會停止或永遠執行。UTM 的巧妙程式設計有時可以預測答案，但所有問題的唯一解決方案是模擬機器在輸入上的行為。不幸的是，如果模擬的機器永遠執行，UTM 也會永遠執行，永遠不會停止並拒絕。已經證明，無法編寫任何 TM 來判定停機問題，因此由字串化的 TM 與輸入字串組成的語言，其中機器在該輸入字串上停止，是一種圖靈可識別語言，但不可判定。
並非所有語言都能夠識別。例如，停機問題的逆，其單詞由一個字串化的 TM 與一個輸入字串組成的語言，其中 TM 在該輸入上沒有停止。如果該語言被某些 TM 'S' 圖靈可識別，那麼可以設計一個 UTM 'T' 來模擬 S，並模擬提供給 S 的 TM。最終，兩者之一會停止，因此 T 將成為停機問題的判定器，我們知道這種判定器不存在，因此該語言不是圖靈可識別的。此外，由於每臺圖靈機都可以在某種編碼下被編碼為一個唯一的字串，並且字串的數量是可數無限的，但語言的數量是不可數無限的，因此一定有不可數無限的語言沒有相應的 TM，因此不是圖靈可識別的。