Automata Theory 简明教程

对于不可判定的语言，不存在接受该语言和对每个输入串 w 做出判定的图灵机（尽管 TM 可以对某些输入串做出判定）。如果对 P 的所有肯定实例的语言 L 是不可判定的，则判定问题 P 称为“不可判定”。不可判定语言不是递归语言，但有时可能是递归可枚举语言。