証明
論理学
アルゴリズムとデータ構造

アルゴリズムの停止性問題を噛み砕いてみた

任意のプログラムが停止するかを判断するプログラムが存在しない、という証明を整理してみました。(Halting Problem)

必要なもの:高校時代、命題についての数学で、ヒイヒイいってた思い出。

Proof

任意のアルゴリズムAがあるとする。また、Aに対して停止性を判断するアルゴリズムMが存在するとする。これをM(A)とおく。

このとき、

1. Aが無限ループを持たない(Aは停止する)→M(A)は「停止する」という結果を出力する。

2. Aが無限ループを持つ(Aは停止しない)→M(A)は「停止しない」という結果を出力する。

★ここで重要なのは、アルゴリズムMは結果を出力して停止している、という点である。

さて、アルゴリズムMは入力されたアルゴリズムの停止性を判断できるのだから、自分自身を入力しても判断できるはずである。つまり、M(M)とする。

この状態で上記の命題1と2の対偶をとってみる。

*1. M(M)は「停止しない」という結果を出力する。→Mは無限ループを持つ(Mは停止しない)

*2. M(M)は「停止する」という結果を出力する。→Mは無限ループを持たない(Mは停止する)

*1で矛盾が起きましたね。Mはどんなアルゴリズムでも結果を出力して停止する、と仮定していたのに、停止しない、となってしまいました。

※わかりやすさを優先していますので書き方の厳密さについてはお許しください、、、。

※これをそのままテストで書いて単位を落としても私は一切責任を負いません。


引用

https://ja.wikipedia.org/wiki/%E5%81%9C%E6%AD%A2%E6%80%A7%E5%95%8F%E9%A1%8C