为什么以下语言是不可判定的？

Question

我目前正在学习本学期的考试，并试图从过去几年解决一些旧考试。

问题是展示，L是不可判定的。 $ l={w | t（m_w）\ neq \ imptyset \ land \ forall x \ In t（m_w）：xx \在t（m_w）\ land xxx \ notin t （m_w）\} $

我展示了语言 $ l'={w | T（m_w）\ neq \ imptyset \} $ 由于米定理而无法判定。我创建到图灵机 $ m_1 $ with $ t（m_1）=imptyset $ 和 $ m_2 $ 使用 $ t（m_2）=sigma ^ * $ 显示语言l'不是微不足道的。 （由于 $ 1 \ in l $ 和 $ 2 \ in loce a $ 。出现了一般性的丧失我假设机器具有Gödelindexes1和2）

我的问题现在是，我知道没有办法展示，即这个结果转移到语言L.我知道语言l必须只包含这样的吉尔索引，即以下TM的那些索引必须接受无限单词（因为在 $ x \中的情况下（m_w）$ ，必须有 $ xx \ In t（m_w）$ < / span> ......因此必须是 $ xxxx \以t（m_w）$ 等。）

我很想听到建议/答案！ 提前谢谢

Answer 1

这是大米定理的直接后果。一个单词 $ w $ 在 $ l $ 如果 $ t（m_w）$ 满足以下语义属性：

$ t（m_w）$ 是非空的，并且对于任何 $ x \ In t（m_w）$ ，我们有 $ x ^ 2 \在t（m_w）$ 和 $ x ^ 3 \ in notin t （m_w）$ 。

为了表明，根据米饭的定理，我们需要展示两个图灵机 $ w_1 $ 和 $ w_2 $ ：一个不满足财产的$，另一个不满足它。我们可以使用 $ w_1 $ 是一些机器，使得 $ t（m_ {w_1}）=imptyset $ ， $ w_2 $ 是一些机器，使得 $ t（m_ {w_2}）={a ^ {2 ^ n}：n \ geq 0 \} $ 。