カントールの対角線論法との関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/11 15:10 UTC 版)
「停止性問題」の記事における「カントールの対角線論法との関係」の解説
対角線論法は、集合Sからその冪集合P(S)への全単射が存在しない(カントールの定理)事を示す為にゲオルグ・カントールが使った論法である。 実は上述の証明は対角線論法も利用している。以下簡単の為、プログラムの入力は全て自然数とする。前述したようにプログラムは0と1からなる数字で書き表せるので、プログラム全体の集合は自然数全体の集合 N {\displaystyle \mathbb {N} } と自然に同一視できる。本当は 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)により定義する。ただしここで「￢」は0と1を反転する写像。すなわち￢0=1、￢1=0。 すると対角線論法により、g=φMとなるMは存在しない。 さて、仮に停止性問題を常に正しく解くプログラムHが存在するとする。M(A)を、H(A,A)=YESなら停止せず、H(A,A)=NOなら0を出力して停止するプログラムとすると、MとHの定義よりg=φMが成立し、矛盾。したがって停止性問題を常に正しく解くプログラムは存在しない。
※この「カントールの対角線論法との関係」の解説は、「停止性問題」の解説の一部です。
「カントールの対角線論法との関係」を含む「停止性問題」の記事については、「停止性問題」の概要を参照ください。
- カントールの対角線論法との関係のページへのリンク
