チューリングマシンの停止性問題

チューリングマシンの停止性問題は、任意のプログラムが任意の入力が与えられて停止するかどうかを常に判定できるプログラムは存在するかに関する問題. 存在しないことが背理法によって示すことが可能とわかっている.

背理法を用いる. 「停止性を判定できる」プログラムAがあるとする(仮定).即ち、プログラムAに何かのプログラムXとそのプログラムへの入力Yを与えると停止するかどうかを1か0で返す.いかなるプログラムもデータであるため他のプログラムへの入力としても扱えることに注意. $$ A(X,Y) = \begin{eqnarray} \left\{ \begin{array}{l} 1\ (X(Y)が停止する) \\ 0 \ (X(Y)が停止しない) \end{array} \right. \end{eqnarray} $$ どのようなプログラムを入れても成立しなくてはならないので、意地悪なプログラムBを与えたときを考える. ここでA(Z,Z)が1ならBは停止し、A(Z,Z)が0ならBは停止しないプログラムBがあるとすると, (Zはプログラムであるがデータとしても扱える) $$ B(Z) = \begin{eqnarray} \left\{ \begin{array}{l} 停止しない\ (A(Z,Z)が1) \\ 停止する \ (A(Z, Z)が0) \end{array} \right. \end{eqnarray} $$ このような問題を考えた時にZがBだとすると上記が以下のように書き換えられる $$ B(B) = \begin{eqnarray} \left\{ \begin{array}{l} 停止しない\ (A(B,B)が1) \\ 停止する \ (A(B, B)が0) \end{array} \right. \end{eqnarray} $$ 条件の部分をより正確に書き下すと以下のようになる. $$ B(B) = \begin{eqnarray} \left\{ \begin{array}{l} 停止しない\ (B(B)が停止する) \\ 停止する \ (B(B)が停止しない) \end{array} \right. \end{eqnarray} $$ これは明らかにB(B)が停止する時にB(B)が停止しないとなっており、矛盾しているとわかる. そのため仮定は誤っており、 「停止性を判定できる」プログラムAは存在しない