$ \ {w〜|〜\ forall x \ In t（m_v）：| w |> | x |〜\} $ decidable？

Question

我想询问 $ \ {w | \ forall x \ In t（m_v）：| w |> | x | \} $ 是可解除的v是一个随机但固定的图灵机的索引，其中 $ | t（m_v）| 。

我的想法： 从我发现 $ x \中的t（m_v）$ 中的 $ |x | \ geq | w | $ 我已经显示出这个套房w不在集中。我认为它是一个半解脱的，因为总是可以是 $ x \中的t（m_v）$ ，它比w长。因此，我也认为问题不可确定。

我监督什么吗？

Answer 1

是的，你缺少一些东西。

此语言是共同半解密的第一个参数是正确的。但是，第二个是错误的（并且没有正式写入。正式证明不能包含这种参数，它们通常是直觉）。

现在显示为什么它是完全可判定的： 我们知道 $ | t（m_v）|= c 。现在，由于这是一个小于无穷大的常数，因此必须存在 $ x_0 \中的t（m_v）$ ，其中 $ | x_0 | $ 是 $ t（m_v）的单词中最长的。$

现在，构建接受 $ w $ iff $ | w |> | x_0 | $ 。

由于 $ x_0 $ 是最长的，那么如果 $ | w |> | x_0 | $ 我们将拥有 $ \ forall x \ In t（m_v）：| w |>> | x_0 | \ ge | x | $ 以及 $ W $ 是您的语言。现在，如果 $ | w | \ le | x_0 | $ ，然后显然 $ w $ 不是你的语言。

因此 $ w $ 在您的语言中，iff $ w $ 是由图灵机接受的建造。