カントールの対角線論法
停止性問題の決定不能性も対角線論法で証明できる。 (停止性問題の決定不能性が何かは停止性問題の項を参照)。
以下簡単の為、プログラムの入力は全て自然数とする。 プログラムは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)により定義する。