algorithm - 停止プログラムの説明

Question

特定の入力で別のプログラム P が停止するかどうかをチェックできるプログラム H を作成できない理由を理解しようとしていますが (停止問題)、明確なアイデアを得ることができません。

このプログラム H が停止しないプログラム P を実行しようとすると、H 自体がループに入ることが直感的にわかります。しかし、これが証明の背後にある考え方だとは思いません。

誰でも簡単な素人の言葉で証明を説明できますか?

score 4 · Accepted Answer

証明の背後にあるアイデアは矛盾によるものです。

M停止問題を解決する停止問題マシンがあり0、一部の入力プログラムが終了しない場合、または終了する場合に譲歩すると仮定1します。M終了することが保証されています。

新しいマシンを作成しますH。 (それ自体)の入力で
H実行され、答えが 1 の場合 - 無限ループに入り、それ以外の場合 - 停止します。MHM

Mでは、 input で実行するとどうなるでしょうHか。
答えが - の場合は、が実行され、無限ループに陥る 1ので、間違っています。答えが- である場合は、停止するため、これも間違っています。HM
0H

したがって、それMは正しいという仮定に矛盾しています - したがって、そのようなものはありませんM。

直感的に言えば、それはオラクルなど存在しないと言っているようなものです。なぜなら、もし「あなた」がオラクルだと言ったら、私はどちらの腕を上げるつもりですか?
それから、私はあなたの答えを待ちます - そして反対のことをします - それは、オラクルが実際にオラクルであるという主張と矛盾します.

score 3 · Accepted Answer

チューリングは、これに対して矛盾による証明を使用しました（別名、不条理への還元）：

アイデアは、与えられたプログラムと入力が天気予報を教えてくれるような機械が実際にあると仮定することです。Hpip

そのようなが与えられHたら、それを変更して新しいマシンを作成できます。の出力の
後に別の部分を追加して、出力が yes の場合、マシンが無限ループし、出力が no の場合、新しいマシンが停止するようにします。新しいマシンをと呼びます。HH
H
H+

H+ここで、 ( programpと inputの両方として) 自分自身にフィードするときにパラドックスが発生しますi。

これH+ は、もし停止すると、(パーツから) はいの答えが得られますHが、その後永久にループするためです。
ただし、停止しない場合H+ はH、(部品から) 応答がありませんが、停止します。

これは、このコンピュータマニアのエピソードで非常にうまく説明されています。

2 に答える 2