无法为可判定语言创建算法

Question

L2 = {<M> : M is a TM and there exists an input string w such that M halts within 10 steps on input w}

嗨。我正在创建一个算法来显示 L2 以上是可判定的。提示如下：

To show L2 is decidable, test given TM M on all input strings of length at most 10, each for 10 steps. Note that there are finitely many such strings to test, so this algorithm will always terminate. If M halts on any input string w within 10 steps then let w' be the prefix of w of length 10. M will also halt on input w' within 10 steps, so the decision algorithm described above will find it.

我只是无法理解这个提示。

M(w)
 let w be w1,w2,... such that w=w1,w2,...,wn
 for i=1,2,...,10
  run m on wi for 10 steps
  if it accepts
   let w' be prefix of w of length 10 and w' be w1,w2,... such that w'=w'1,w'2,...,w'n
   for t=1,2,...,10
    run m on w't for 10 steps
   end for
  end if
 end for
end M(W)

如您所见，我制作的上述算法，我不知道如何根据上面的 L2 定义和提示制作正确的算法。

我需要正确编写它的帮助（请使用您编写算法的风格。我认为只要主要思想正确，风格并不重要。我不明白的是它的思想。）

如果你能帮助我，非常感谢。

Answer 1

这里有一个对解决这个问题非常有用的观察。假设你拿一个 TM M 和运行它在一个非常非常长的字符串 w 上，想知道它是否在十步内停止。如果您考虑一下，w 中唯一重要的部分是前十个字符，因为在十个步骤中，TM 无法读取更多内容。换句话说，如果你想判断一个TM是否在运行上的字符串w上在十步内停止，你只需要检查w的前十个字符。

现在假设您要确定 TM 是否会在十步内停止在某个字符串上。由于我们刚才的观察，您无需查看所有字符串即可确定此问题的答案。也就是说，在所有长度为 10 或更短的字符串上，只需运行十步的 TM。如果 TM 在任何这些字符串上在十步内停止，那么你就完成了 - 你已经看到 TM 在某些输入字符串上在十步内停止了。另一方面，假设 TM 在任何这些字符串上都不会在十步内停止。需要证明的是，TM 因此不会在十步内停止在 any 字符串上，因为如果它停止了，那么当只给出该字符串的前十个字符时它就必须停止（鉴于上述推理），但我们知道它没有。

所以算法看起来像这样：

对于长度最多为 10 的每个字符串 w：
- 运行 M on w 最多十步。
- 如果当时 M 在 w 上停止，return 为真。
Return 错误。

无法为可判定语言创建算法

Cannot create algorithm for decidable language

algorithm

computer-science

turing-machines

reduction

decidable