考虑语言
考虑语言 Aabb = {< M > | M 是 TM,M 接受 abb} a) Aabb 代表的计算问题是什么?b) 证明 Aabb 是不可判定的。
我试图证明这一点,但不知道该怎么做。
考虑语言
考虑语言 Aabb = {< M > | M 是 TM,M 接受 abb} a) Aabb 代表的计算问题是什么?b) 证明 Aabb 是不可判定的。
我试图证明这一点,但不知道该怎么做。
您可以直接使用赖斯定理并正确地证明该主张,方法是注意一些 TM 接受 aab,有些不接受,并且接受 abb 是语言的语义属性(它只与接受的字符串有关,与接受的方式无关他们)。赖斯保证这种语言是不可判定的。
如果您想要另一种证明,请考虑以下内容。字符串 abb 没有什么特别之处。如果这个问题是可判定的,我们希望这个问题对于任意字符串都是可判定的。如果对于任意字符串是可判定的,我们可以使用 dovetailing 来判定 TM 的语言是否为空。如果我们可以确定 TM 的语言是否为空,我们可以取任何 TM,将所有 halt-reject 实例更改为 halt-accept,然后确定 TM 是否在至少一个输入时停止。等等 等等 基本上,您可以根据需要构建一系列含义,但您很快就会发现可以减少到的已知不可判定的问题。