停性問題 - 横山てつお

停⽌性問題
横⼭てつお
すべてのプログラムAとすべてのデータxに対し、
以下のような H(A,x) があると仮定する（背理法）
A
x
A(x)の実⾏は停⽌する
Yes
"YES"を印刷
して停⽌
No
"NO"を印刷
して停⽌
以下のような M(A) が存在する。
A
H(A,A) = YES か？
Yes
停⽌しない
No
"0"を印刷
して停⽌
すると、 M(M) は存在しない。(Yes/Noどちらでも⽭盾)
H(M,M):
M
M(M):
M
M(M)の実⾏は停⽌する
Yes
"YES"を印刷
して停⽌
No
"NO"を印刷
して停⽌
M
H(M,M) = YES か？
Yes
停⽌しない
No
"0"を印刷
して停⽌

Download Report