为什么这种语言是可识别的，而不是不可识别的

Question

我读到以下语言是r.e.但不是不可识别的识别

$ l $ ：在输入 $ m $ （其中 $ M $ 是一个图灵机）， $ m $ 接受至少20个输入

我不确定为什么它不是不可识别的。，因为我可能会使以下从 $ \ overline {a_ {tm}} $ 给 $ l $ 给定此过程 $ r $ 即：

$ r $ ：在输入 $ $ ：

1. 构造tm $ m_1 $ ，其中在输入 $ x $ ，if $ x= 1 $ ，接受
2. 如果输入 $ x $ 不等于 $ 1 $ ，运行 $ M $ 在输入 $ w $ for $ | x | $ 脚步。如果之后 $ | x | $ 步骤， $ m $ 不接受 $ W $ ，然后接受 $ x $

从这种减少，如果 $ m $ 不接受 $ w $ ，即 $ \ in \ ovline {a_ {tm}} $ ，然后 $ m_1 $ 接受任何输入单词，即 $ m_1 \ in l $ 。

我在这里遗漏了什么？

Answer 1

您缺少的是，如果 $ \ langle m，w \ rangle \ portin \ locline {a _ {\ mathrm {tm}}} $ ，即如果 $ m $ 停止输入 $ w $ ，您不知道是 $ M_1 \投入L $ 。如果 $ m $ 在 $ w $ 上，但这需要长于 $ 20 $ 步骤，它还可以按住 $ m_1 \ in l $ 。因此，您在此处没有减少。

语言 $ l $ 不能是Cy-Re是大米定理的立即后果。