可判定语言

可判定性的核心不是某些实例容易，而是存在一台统一机器，对每个输入都在有限时间内给出正确的是非答案：它不仅要答对“是”的实例，还必须对所有“否”的实例明确给出否定答案并最终停止。停机要求排除了“找到证据才返回、找不到就一直等”的半算法，因此可判定语言同时拥有完备的正证据处理和负证据处理。把算法效率暂时拿掉后，这一概念刻画的是计算原则上的可能边界。

有限自动机接受问题可判定。某些语言可被识别：成员输入最终接受，但非成员输入可能永不停止；可识别不等于可判定。

有限图的连通性可判定：遍历从起点可达的顶点，有限步骤后便能回答。给定上下文无关文法和字符串的成员问题也可由 CYK 判定。与之相对，$HAL{T}_{TM}$ 虽然成员可通过模拟来确认，却不存在对所有不停止实例也能终止并拒绝的程序。

“输入规模有限”不自动带来可判定性，因为程序或机器描述虽然有限，却能指定无限计算。随机算法高概率给出答案也不改变这里的定义：除非它对每个随机分支都终止并满足所要求的零误差/确定语义，否则不能直接当作判定器。

可判定语言构成可识别语言公理库可识别语言Turing-recognizable language · Recursively enumerable language存在图灵机对语言内输入接受、对语言外输入可拒绝或不停机的语言。的严格子类：判定器同时给出正、负实例的有限停止保证。这个包含关系是研究不可计算性和归约的起点。可识别性公理库可识别语言Turing-recognizable language · Recursively enumerable language存在图灵机对语言内输入接受、对语言外输入可拒绝或不停机的语言。 是放松负实例停机要求后的概念，而 余可识别性公理库余可识别语言Co-recognizable language · Co-r.e. language补语言可被图灵机识别的语言。 放松正实例；两者同时成立恰好恢复可判定性。映射归约公理库映射归约Mapping reduction · Many-one reduction用可计算函数把一个语言成员关系变换为另一个语言成员关系。 用一个总可计算变换传递判定能力，因此是建立不可判定问题谱系的基本工具。