形式陈述

语言 $L\subseteq\Sigma^*$$L\subseteq {\mathrm{\Sigma }}^{\ast }$ 可判定，当且仅当存在图灵机 $M$$M$，对每个输入 $w$$w$ 都在有限步内停机，并且 $w\in L$$w\in L$ 时接受、$w\notin L$$w\notin L$ 时拒绝。这样的 $M$$M$ 称为判定器。

直觉

关键不仅是答对“是”的实例，还必须对所有“否”的实例给出否定答案且最终停止。

例子与边界

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

推论与应用

可判定性划分算法能完全解决与只能半判定的问题，是研究不可计算性和归约的起点。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., §4.1.
• Hartley Rogers Jr., Theory of Recursive Functions and Effective Computability, Chapter 5.