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

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

为了证明 L2 是可判定的，在所有长度不超过 10 的输入字符串上测试给定的 TM M，每个字符串执行 10 步。请注意，要测试的此类字符串数量有限，因此该算法将始终终止。如果 M 在 10 步内停止在任何输入字符串 w 上，则令 w' 是长度为 10 的 w 的前缀。M 也会在 10 步内停止输入 w'，因此上述决策算法会找到它。

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

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 定义和提示中做出正确的算法。

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

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

4

1 回答 1

0

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

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

所以算法看起来像这样：

  • 对于每个长度最多为 10 的字符串 w：
    • 在 w 上运行 M 最多十步。
    • 如果此时 M 在 w 上停止，则返回 true。
  • 返回假。
于 2016-03-13T08:09:24.960 回答