computation-theory - 表明语言是不可判定的

Question

考虑语言

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

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

标签： computation-theorydecidable

Answer 1

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

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