この問題のために私のメモを検討していますが、この問題の仕組みを理解できていないようです。私たちはMを持っているとし、Mはすべての非停止状態を訪れる入力を受け入れます。この言語が決定可能かどうかを証明する
私はこの問題が決定可能だと確信しましたが、私は問題を証明しています。私の答えの大まかな概要は次のようなものです：TM Tが1つの停止状態しかないと仮定し、すべての状態を通過する必要がある場合は、この停止状態を通過する必要があり、どのようにそれらが循環するかを示す必要がありますすべての州はそのようなものです。
ご協力いただきありがとうございます。
私は答えが実際には決めることができないと思います。どうして？これは、停止問題を解決できるようになります。
説明した問題に対しては、TM Mと入力xとOracle Qが与えられます。 oracle Qを使用して、入力xを持つMの停止問題を解決できますか？
MはNM IFF X上で停止し、テープへの書き込みのXのすべての入力に停止 - - テープの内容 が削除されます：まず
は、我々はM.の前に新しいTM Nを接続するここでNが何をするかです。これは、入力がxであった場合にMが見たようにNがテープを正確に残すので、見やすいものでなければならない。 Nのすべての状態が訪問されるようにNを設計することができる。
ここで、2番目のテープを追加してMにMを変更します。 2番目のテープは、私たちが訪れた最高の番号のM 'の状態を追跡するために使用されます。セカンダリテープからn番目の状態を読み出し、M 'を（n + 1）番目の状態に遷移させる遷移をM'に加える。最も高い番号の状態M 'からの遷移は、M'の初期状態に戻り、セカンダリテープに「finished」のようなものを書き込む必要があります。 M 'がセカンダリテープ上で「終了」したと見なすと、Mはそうしたように動作し、プライマリテープのみを考慮します。
だから、Mは最初の訪問Mのすべての状態と、その後は、それだけでMはX上の停止のx IFF上のM.
M」停止と同じように動作した後にリセットされることを除いて、ありません「Mはまさにん」。 Mがx上で停止する場合、NM 'も停止する。
最後に、私たちは証明の準備が整いました。オラクルQは、Mがx上で停止するとNM 'を受け入れます。 Qは、NM 'がすべての状態を訪問するようになる入力yをNM'が受け入れる場合、NM 'を受け入れる。しかし： - すべての入力yはNM 'をすべての状態に訪問させる（Nのすべての状態は構築によって訪問され、Mのすべての状態はMの修正によって訪問される）。だから、Qは本当に "NMは文字列を受け入れるの？"という質問にちょうど答えているのですか？ - NMは入力テープからyを消去し、xを書き込んでM 'に渡します。したがって、入力yは重要ではありません。 NM 'が入力を受け入れるならば、それはすべてを受け入れます。そして、M 'がxを受け入れるなら、それはすべてを受け入れます。 - M 'はMと同じ言語を受け入れます。
NMに適用されたQは、Mがxで停止するかどうかを実際に教えてくれます。その後、Qは停止問題を解決する。