显示语言是不确定的

Question

考虑语言

考虑语言Aabb = { | M是TM，M接受abb}a）Aabb代表的计算问题是什么？b）证明Aabb不能确定。

我试图证明这一点，但不知道该怎么办。

Answer 1

您可以直接使用赖斯定理，并指出某些TM接受aab，有些不接受ab，而接受abb是语言的语义属性（它只与接受的字符串有关，而与方式无关，因此可以直接并正确地证明该主张。接受他们）。赖斯保证这种语言是不确定的。

[如果您需要另一种证明，请考虑以下内容。字符串abb没什么特别的。如果这个问题是可确定的，那么我们希望这个问题对于任意字符串都是可确定的。如果可以确定任意字符串，则可以使用燕尾确定TM语言是否为空。如果我们可以确定TM的语言是否为空，则可以采用任何TM，将所有halt-reject实例更改为halt-accept，然后确定TM是否在至少一个输入上停止。等等基本上，只要您愿意，您就可以构建一个含义链，但是您很快就会发现可以减少到的已知不确定性问题。