可计算性和复杂性/可计算性/可判定性
本节讨论在图灵机 (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，因此不是图灵可识别的。