このPDF で以下の問題に遭遇しました：
TM Mが与えられた場合、Mが空のテープで開始されたときに空白以外の記号を書き込むかどうか。
解決策は次のとおりです。
マシンに空白のみを書き込むようにしますシンボル。その場合、wのcom計算における構成の数はq×2です。ここで、qはMの状態の数です。因数2は、選択に関するものです。頭の動きの方向;それは常に空白であるため、書かれた記号の要素はありません。したがって、問題は決定可能であり、次のマシンによって決定されます。入力（M、w）、q×2ステップでw上でMを実行します。 Mが空白以外の記号を書き込んだ場合は、「はい」と答えて停止します。 Mが空白以外の記号を書き込まない場合は、応答なしで停止します
疑問：
Q1。すべてのqx2構成が確実に行われるようにする方法wでqx2ステップを実行している間？一部の構成は、qx2ステップで繰り返される場合があります。
Q2。質問には「空のテープ」ですが、答えは空でない文字列wでTMをシミュレートしようとしました。どのように意味がありますか？
回答
Q1：状態が繰り返される可能性があります。重要なのは、状態が繰り返され、空でないシンボルが書き込まれていなくても、チューリングマシンは、これまでに遭遇したいくつかの状態を循環して停止する必要があるため、停止しないことを知っているということです。サイクルのどの状態もTMに空白以外のシンボルを書き込ませなかったため、TMは空白以外のシンボルを書き込むことはありません。
$ 2qの後$ の手順では、空白以外の記号が書き込まれ、「はい」と答えることができます。または、書き込まれた記号がすべて空白で、（少なくとも）1つの状態が2回以上発生している必要があります。つまり、 「いいえ」と答えることができます。
Q2：私の推測では
コメント
- Q1。 "空白以外の記号が書かれていて、はいと答えることができます…そしていいえ "？質問は" Mが空白以外の記号を書き込むかどうかを尋ねるからです"。第2四半期に。空白の記号で上書きされたwの位置のサブセットの数に対応する状態の数で"を取得しませんでした"
- その通りです。私は自分の答えを修正しました。後半も明確にしました。