停止性問題の決定不能性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 07:08 UTC 版)
「カントールの対角線論法」の記事における「停止性問題の決定不能性」の解説
停止性問題の決定不能性も対角線論法で証明できる。（停止性問題の決定不能性が何かは停止性問題の項を参照）。 以下簡単の為、プログラムの入力は全て自然数とする。プログラムは0と1からなる数字で書き表せるので、プログラム全体の集合と自然数全体の集合 N {\displaystyle \mathbb {N} } と自然に同一視できる。 ϕ : N × N ↦ { 0 , 1 } {\displaystyle \phi :\mathbb {N} \times \mathbb {N} \mapsto \{0,1\}} を次のように定義する：A(x)が停止すればφ(A,x)=1、そうでなければφ(A,x)=0。 以下φ(A,x)の事をφA(x)と定義する。 g : N ↦ { 0 , 1 } {\displaystyle g:\mathbb {N} \mapsto \{0,1\}} を、g(A)=￢φA(A)により定義する。すると対角線論法により、g=φMとなるMは存在しない。 さて、仮に停止性問題を常に正しく解くプログラムHが存在するとする。M(A)を、H(A,A)=YESなら停止せず、H(A,A)=NOなら0を出力して停止するプログラムとすると、MとHの定義よりg(A)=φMが成立し、矛盾。したがって停止性問題を常に正しく解くプログラムは存在しない。 ゲーデルの第一不完全性定理の証明は停止性問題の決定不能性の証明に酷似している。したがってゲーデルの第一不完全性定理の証明も暗に対角線論法を利用している。 停止性問題の決定不能性を「有限時間」と「無限時間」という２つの時間階層の間の時間階層定理だと解釈すると、時間階層定理の証明を停止性問題の決定不能性の証明の焼き直しとみなすことができる。したがって時間階層定理の証明も対角線論法を使っている事が分かる。
※この「停止性問題の決定不能性」の解説は、「カントールの対角線論法」の解説の一部です。
「停止性問題の決定不能性」を含む「カントールの対角線論法」の記事については、「カントールの対角線論法」の概要を参照ください。
- 停止性問題の決定不能性のページへのリンク
