0

次の証明についていくつか質問したい。証明はもともと教科書から来ており、次に下のスタックオーバーフローに関する質問から来ています。

停止問題が決定不能であるというこの証明はどのように機能するのでしょうか?

質問1：

以下の証明は、本質的に H をその入力マシンのシミュレーターにしますか?

言い換えれば、H = M と言うのと、以下の証明からの記述との間に重要な違いはありますか?

H([M,w]) = {accept if M accepts w}
         = {reject if M does not accept w.}

質問2：

私の次のコメントはどのように正しいか間違っていますか?

停止の問題は、特定のマシンがその出力 (受け入れ/拒否) に関係なく停止するかどうかを決定する問題だと思いました。停止する問題の解決策が存在する場合、それは実際に実行するのではなく、コンパイラ/逆コンパイラ/逆アセンブラのようにソース コードを分析するものでなければなりません。それを実行する必要がある場合、明らかに「いいえ」の答えを決定することはありません。

証明の明らかな問題に注目すると、証明全体が停止問題の決定不能性を示していないように見えます。

代わりに、証明はこれを示しているようです: 次のアルゴリズムは停止しません:

    boolean D()
    {
        return not D();
    }

以下は、Sipser による Intro to the Theory of Computation から再タイプされた問題の証明です。

停止の問題は決定不可能です

これで定理 4.11、言語の決定不能性を証明する準備が整いました。

ATM = {[M,w] | M は TM であり、M は w} を受け入れます。

証明: ATM が決定可能であると仮定し、矛盾を取得します。H が ATM のディサイダーであるとします。M が TM で w が文字列である input で、H は停止し、M が w を受け入れる場合に受け入れます。さらに、M が w を受け入れない場合、H は停止して拒否します。つまり、H は TM であると仮定します。

H([M,w]) = {accept if M accepts w}
         = {reject if M does not accept w.}

ここで、サブルーチンとして H を使用して新しいチューリング マシン D を構築します。この新しい TM は、H を呼び出して、M への入力が独自の記述である場合に M が何をするかを決定します。D がこの情報を決定すると、反対のことを行います。つまり、M が受け入れる場合は拒否し、M が受け入れない場合は受け入れます。Dの説明は以上です。

D = "On input [M], where M is a TM:
1. Run H on input [M, [M]].
2. Output the opposite of what H outputs; that is, if H accepts, reject and if H rejects, accept."

独自の記述でマシンを実行するという考えに混乱しないでください。これは、それ自体を入力としてプログラムを実行することに似ており、実際には時々発生します。たとえば、コンパイラは他のプログラムを変換するプログラムです。Pascal 言語のコンパイラ自体が Pascal で記述されている可能性があるため、そのプログラムをそれ自体で実行することは理にかなっています。要約すれば、

D([M]) = { accept if M does not accept [M]
       = { reject if M accepts [M]

独自の説明を入力として D を実行するとどうなるか > その場合、次のようになります。

D([D]) = {accept if D does not accept [D]
       = {reject if D accepts [D]

D が何をしようとも、反対のことをするのは力であり、明らかに矛盾しています。したがって、TM D も TM H も存在できません。

4

1 に答える 1

0

言い換えれば、H = M と言うのと、以下の証明からの記述との間に重要な違いはありますか?

H マシンは、ユニバーサル チューリング マシン (UTM) と呼ばれ、それ自体を含め、他のチューリング マシンをシミュレートできます。

M が H のような万能チューリング マシンである場合、H = M と言って問題ありません。

停止の問題は、特定のマシンがその出力 (受け入れ/拒否) に関係なく停止するかどうかを決定する問題だと思いました。停止する問題の解決策が存在する場合、それは実際に実行するのではなく、コンパイラ/逆コンパイラ/逆アセンブラのようにソース コードを分析するものでなければなりません。それを実行する必要がある場合、明らかに「いいえ」の答えを決定することはありません。

そのため、証明は矛盾に基づいて機能し、ちょっとわかりにくいです。基本的に、与えられた入力に対して「はい」または「いいえ」で答えるようなマシンが最初に存在すると仮定します。[仮説]

このマシンを Q と呼びましょう。Q が有効で UTM であると仮定すると、次の手順に従って動作する別のマシン S をシミュレートできます。

  1. S は入力 (プログラムとその入力) を読み取ります
  2. S は、読み取ったばかりの入力を複製します
  3. S はコピーされた入力を渡して Q を呼び出します
  4. S は Q が応答するのを待ちます (そして、私たちの仮説に基づいて、常に応答します)

入力 Q(S, S) を想像してみましょう。Q はプログラム S を受け取り、S の引数は S そのものです。この入力により、S は Q を無期限に呼び出し、停止することはありません。

Q と S は正当なプログラムでしたが、Q を決して停止させない一種の入力があるため、Q は構築不可能なマシンであり、したがってプログラム S が停止するかどうかを判断することは不可能です。したがって、停止問題が決定不能であることが証明されました。

シプサーはそれをうまく説明しています。今もう一度読んで、アイデアをキャッチするかどうかを確認してください:)

さて、あなたの質問に戻ります。チューリング マシンは、問題を表現するための最も強力なマシンです。認識マシンとして、入力を調べてアルゴリズムを実行し、有効かどうかを判断する必要があります。アルゴリズムを実行せずにその出力を知ることは不可能です。

コンパイラは、構文と小さなセマンティクスの単なる翻訳者です。プログラムがどのように使用され、出力がどうなるかを予測することはできません。

于 2012-12-10T02:57:13.877 に答える