停止性問題
ハルティング問題とは、コンピュータサイエンスの問題です。この問題は、コンピュータプログラムを見て、そのプログラムが永遠に実行されるかどうかを見つけることです。私たちは、あるプログラムが他のプログラムを見て、そのプログラムが永遠に実行されるかどうかを知ることができれば、そのプログラムは「停止問題を解決している」と言います。
例えば、こんなプログラム。
while True:続ける。は永遠にループしますが、プログラム
while False:続ける。は非常に早く止まります。
停止問題を解決するプログラムはあるのか？存在しないことがわかりました．もし、停止問題を解くプログラムが存在するならば、不可能なことが起こることを示して、この事実を証明します。そこで，今のところは，停止問題を解決するプログラムが本当に存在するかのように振る舞うことにしましょう．ここで、Pは関数F（引数Iで呼ばれる）を評価し、それが永遠に実行されれば真を返し、そうでなければ偽を返す関数です。
def P(F, I): F(I)が永遠に実行される 場合: Trueを 返し、 そうでない場合: Falseを返す。Pはどんなプログラムでも見て、そのプログラムが永遠に動作するかどうかを調べることができます。Pを使って、Qと呼ぶ新しいプログラムを作ります。Qがすることは、別のプログラムを見て、次の質問に答えることです。"このプログラムを実行して、それ自身のコピーを見るようにした場合、それは永遠に実行されますか？PがあるのでQを作ることができます。あとは、Qに古いプログラムが自分自身を見ている新しいプログラムを作るように指示し、Pを使って新しいプログラムが永遠に動くかどうかを調べればいいのです。
def Q(F): P(F, F)を返す。Rは別のプログラムを見て、そのプログラムについてQに答えを求めます。もしQが「yes, もしこのプログラムを実行して、それ自身のコピーを見るようにしたら......永遠に実行されるだろう」と答えたら、Rは停止します。Q が「no, if we run this program and make it look at a copy of itself, it will not run forever」と答えると、R は無限ループに入り、永遠に実行される。
def R(F): if Q(F): return; // 終了 else: while True: continue; //永遠にループする。さて、Rにそれ自身のコピーを見させるとどうなるかを見てみましょう。2つのことが起こります：それは停止するか、永遠に実行されるかです。
Rを実行して自分自身のコピーを見させても永遠に動かないのであれば、Qは「はい、このプログラムを実行して自分自身のコピーを見させれば永遠に動くでしょう」と答えた。しかし、QはR自体を見るときにこのようなことを言っています。つまり、Qが実際に言ったのは「yes, if we run R and make it look at a copy of itself it will run forever」ということになります。ということです。Rを実行して、それ自身のコピーを見させれば、永遠に実行される」というのは、Rが永遠に実行されないのであればこれは不可能です。
Rを実行して自分自身のコピーを見させれば永遠に動くのであれば、Qは「いや、このプログラムを実行して自分自身のコピーを見させれば永遠には動かない」と答えた。しかし、QはR自体を見るときにこのようなことを言っています。つまり、Qが実際に言ったのは「no, if we run R and make it look at a copy of itself it will not run forever」ということになります。ということです。Rを実行して、自分自身のコピーを見させると、永遠に実行されない。これも不可能です。
何があっても、ありえない状況に陥ってしまう。何か間違ったことをしたから、それが何だったのかを突き止めないといけない。私たちがやったことのほとんどは間違っていません。プログラムに自分のコピーを見させることが間違っている」とか、「別のプログラムが言ったことを見て、あることを言っていたらループに入って、別のことを言っていたら止めてしまう」ということが間違っているとは言えないのです。そういうことをしてはいけないというのは意味がありません。間違っているように見えることをしたのは、そもそもPのようなプログラムが存在することを装ったことだけです。そして、これだけは間違っている可能性があり、何かが間違っているに違いないので、これはこれである。これが、Pのようなプログラムが存在しないことの証明です。思考停止問題を解決するプログラムは存在しない。
この証明は、1936年にアラン・チューリングによって発見されました。
質問と回答
Q:ハルティング問題とは何ですか?
A: Halting問題とは、コンピュータ・サイエンスにおける問題で、コンピュータ・プログラムを見て、そのプログラムが永遠に実行されるかどうかを決定するものです。
Q:プログラムがハルティング問題を解決しているかどうかは、どのようにしてわかるのですか?
A:あるプログラムが、他の任意のプログラムを見て、その他のプログラムが永遠に実行されるかどうかを判断できる場合、そのプログラムは「停止問題を解決している」と言います。
Q:そのようなプログラムが存在しないことを証明する方法はあるのでしょうか?
A:はい、もしそのようなプログラムがあれば、不可能なことが起こることを示すことで証明できます。この証明は、1936年にアラン・チューリングによって発見されました。
Q:Pは何をするのですか?
A: P は他の関数 F（引数 I で呼び出される）を評価し、それが永遠に実行されれば真を、そうでなければ偽を返す関数である。
Q: Q は何をするのですか?
A: Q は別のプログラムを見て、この同じプログラムを自分自身に実行すると無限ループになるかどうかという質問に答えます。これは、P を使って与えられた関数 F を評価することによって行われます。
Q:Rは何をするのですか?
A:Rは、別のプログラムを見て、その特定のプログラムについての答えをQに求めます。Qが「はい、このプログラムを走らせて自分自身のコピーを見させると永遠に走ります」と答えたらRは停止します。しかし、Qが「いいえ、このプログラムを走らせて自分自身のコピーを見させると永遠に走りません」と答えたらRは無限ループに入って永遠に走り続けるのです。
Q:Rに自分自身を見させるとどうなるのですか?
A:Rが止まるか、永遠に走り続けるかの2つが考えられますが、Pのようなプログラムが存在しないことが証明されている以上、どちらの結果もあり得ないので、Rに自分自身を見させるまでの過程のどこかで何かが間違っていたのでしょう。
