turing-machines - 判断以下语言是否可判定

Question

{⟨M,N⟩ | L(M)∩L(N) 中的所有字符串都以 110 开头。}

我认为这种语言是可判定的。我们可以制作一个图灵机 TM，它以 为输入。对于 L(M)∩L(N) 中的每个字符串，如果字符串以 110 开头，在前 3 位之后，我们停止并接受。如果前三位不是 110，我们就停止并拒绝。如果字符串不在 L(M)∩L(N) 中，我不确定我们该怎么做。

总的来说，我不确定我的图灵机是否真的在工作。我能得到一些反馈吗？

Answer 1

如果 M 和 N 是图灵机，那么这种语言是不可判定的。如果是的话，我们可以让 N 成为一个接受所有字符串的 TM，然后我们就有一个 {M | M 中的所有字符串都以 110} 开头。我们可以认识到这是不可判定的，因为某些 TM 的条件为真，而另一些 TM 的条件为假，而且它的语义在于它处理语言中的字符串；所以赖斯定理适用。