|
不可判定性介绍在计算理论中，我们经常遇到这样的问题，答案不是“是”就是“不是”。可以回答为“是”的问题称为可解决或可决定的问题。否则，这类问题就被称为无法解决或无法确定。 通用语言的不可判定性:通用语言Lu是一种递归可枚举语言，我们必须证明它是不可判定的(非递归)。 定理:lu是正则，但不是递归的。 证明: 考虑语言Lu是递归枚举语言。我们假设Lu是递归的。然后是L的补uL 'u也是递归的。然而，如果我们有一个TM M来接受L 'u，那么我们就可以构造一个TM Ld．但我d对角化语言不是正则。因此我们假设Lu是递归的是错误的(不是RE意味着不是递归的)。因此我们可以说Lu是正则，但不是递归的。M对L的构造d如下图所示: 
下一个话题
关于TM的不可判定问题
|
观看视频请加入我们的Youtube频道:现在加入
反馈
- 将你的反馈发送至(电子邮件保护)
帮助他人，请分享
