by shigemk2

当面は技術的なことしか書かない

停止性問題

停止性問題 - Wikipedia

チューリング機械(≒プログラム、アルゴリズム)Aに入力xを入れたら有限時間で停止するか、という問題。
かのチューリング対角線論法を用いて、停止性問題を解くチューリング機械が存在しないことを証明した。

「プログラムAとデータxが与えられたとき、A(x)が有限時間で停止するかどうか」という問題である。

つまり、全てのプログラムAと全てのデータxに対し、有限時間に停止するかどうかを判定し停止する
プログラムH(Halt)を仮定する。

  • A(x)が有限時間で停止する ⇒ H(A,x)は有限時間でYESを出力して停止する。
  • A(x)は有限時間では停止しない ⇒ H(A,x)は有限時間でNOを出力して停止する。

停止性問題を常に正しく解くプログラムHが存在したとする。

M(A)を、H(A,A)=YESなら停止せず、H(A,A)=NOなら0を出力して停止するプログラムとする。(H(A,A)と無限ループを組み合わせる事でM(A)を作る事ができる。)

M(M)は停止するだろうか?
M(M)が停止したとすると、Mの定義よりH(M,M)=NO。Hの定義より H(M,M)=NOとなるのはM(M)が停止しないときのみなので、矛盾。
M(M)が停止しないとすると、Mの定義よりH(M,M)=YES。Hの定義より、H(M,M)=YESとなるのはM(M)が停止するときのみなので、矛盾。

よって停止性問題を常に正しく解くプログラムHは存在しない。