pptx - 横山てつお

停止性問題
横山てつお
すべてのプログラム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