不可判定的语言
对于不可判定的语言,不存在接受该语言并对每个输入字符串w做出决策的图灵机(尽管 TM 可以对某些输入字符串做出决策)。如果P的所有“是”实例的语言L不可判定,则判定问题P称为“不可判定”。不可判定语言不是递归语言,但有时,它们可能是递归可枚举语言。
例子
- 图灵机的停机问题
- 死亡率问题
- 凡人矩阵问题
- 邮政信件问题等
对于不可判定的语言,不存在接受该语言并对每个输入字符串w做出决策的图灵机(尽管 TM 可以对某些输入字符串做出决策)。如果P的所有“是”实例的语言L不可判定,则判定问题P称为“不可判定”。不可判定语言不是递归语言,但有时,它们可能是递归可枚举语言。