不可判定的语言

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