そのため、この問題に関するメモを確認していますが、この問題がどのように機能するのか理解できません。M があり、M はすべての非停止状態を訪問する入力を受け入れます。
この問題は決定可能であると確信しましたが、そう証明するのに苦労しています。私の答えの大まかな概要は次のとおりです。停止状態が1つしかないTM Tがあり、すべての状態を通過したい場合は、この停止状態を通過する必要があり、それらがどのように循環するかを何らかの形で示す必要があると仮定しますそのようなすべての州。
どんな助けでも有益です、ありがとう！
答えは、実際には決定不可能であることがわかると思います。なんで？これにより、停止の問題を解決できます。
あなたが説明した問題に対して、TM M と入力 x とオラクル Q が与えられます。オラクルQを使用して、入力xでMの停止問題を解決できますか?
最初に、新しい TM N を M の前に接続します。N が行うことは次のとおりです。 - テープの内容を削除します - テープに x を書き込みます
NM がすべての入力で停止する場合、M は x で停止します。これは、入力が x の場合に M が見たのとまったく同じように、N がテープを離れるため、簡単に確認できるはずです。N のすべての状態が訪れるように N を設計できます。
ここで、2 番目のテープを追加して、M を M' に変更します。2 番目のテープは、私たちが訪れた M' の最大番号の状態を追跡するために使用されます。二次テープから n 番目の状態を読み取り、M' を (n+1) 番目の状態に遷移させる遷移を M' に追加します。M' の最大番号の状態からの遷移は、M' の初期状態に戻り、セカンダリ テープに「終了」などの情報を書き込む必要があります。M' がセカンダリ テープで「終了」したことを確認すると、M が行ったのと同じように動作し、プライマリ テープのみを考慮します。
したがって、M' は M' とまったく同じことを行いますが、最初に M のすべての状態にアクセスし、その後リセットしてから M と同じように動作する点が異なります。
M' が x で停止する場合、M は x で停止します。また、M が x で停止した場合、NM' は停止します。
いよいよ証明の準備です。オラクル Q は、M が x で停止した場合に NM' を受け入れます。Q は、NM' がすべての状態を訪問する入力 y を受け入れる場合、NM' を受け入れます。ただし: - すべての入力 y により、NM' はすべての状態を訪問します (N のすべての状態は構成によって訪問され、M' のすべての状態は M の変更によって訪問されるため)。つまり、Q は「NM' は文字列を受け入れますか?」という質問に答えているだけです。- NM' は入力テープから y を消去し、x を書き込み、それを M' に渡します。したがって、入力 y は重要ではありません。NM' が任意の入力を受け入れる場合、それらすべてを受け入れます。そして、M' が x を受け入れる場合、それらすべてを受け入れます。- M' は M と同じ言語を受け入れます。
したがって、Q を NM' に適用すると、M が x で停止するかどうかがわかります。次に、Q は停止問題を解きます。