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 が決定可能であることを示すには、与えられた TM M を最大 10 の長さのすべての入力文字列で、それぞれ 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 で実行し、10 ステップ以内で停止するかどうかを知りたいとします。考えてみれば、w の重要な部分は最初の 10 文字だけです。10 ステップでは TM はそれ以上読み取ることができないからです。つまり、文字列 w に対して実行したときに TM が 10 ステップ以内で停止するかどうかを判断したい場合は、w の最初の 10 文字を調べるだけで済みます。

ここで、TM がある文字列で 10 ステップ以内に停止するかどうかを判断したいとします。先ほど行った観察により、すべての文字列を調べなくても、この質問に対する答えを判断できます。つまり、長さが 10 以下のすべての文字列で TM を 10 ステップだけ実行します。これらの文字列のいずれかで TM が 10 ステップ以内に停止した場合、完了です。入力文字列で 10 ステップ以内に TM が停止したことを確認しました。一方、これらの弦のいずれにおいても、TM が 10 ステップ以内に停止しなかったとします。証明すべき主張は、TM が10 ステップ以内のどの文字列でも停止しないということです。停止した場合、その文字列の最初の 10 文字が与えられたときに停止する必要があるためです (上記の理由を考えると)。しなかったこと。

したがって、アルゴリズムは次のようになります。

  • 長さが最大 ​​10 の各文字列 w について:
    • M を w 上で最大 10 ステップ実行します。
    • その時間内に M が w で停止した場合、true を返します。
  • false を返します。
于 2016-03-13T08:09:24.960 に答える