- @ThothChildren
- 2018.12.2
- PV 626
チューリングマシンの停止性問題
ー 概要 ー
停止性問題は、任意のプログラムが任意の入力が与えられて停止するかどうかを判定するプログラムは存在するかに関する問題.存在しないことが背理法によって示すことが可能.
この章を学ぶ前に必要な知識
ポイント
- 任意のプログラムとそのプログラムへの任意の入力に対して停止するかどうかを判定できるプログラムは存在しない
- 背理法によって証明することが可能
解 説
チューリングマシンの停止性問題は、任意のプログラムが任意の入力が与えられて停止するかどうかを常に判定できるプログラムは存在するかに関する問題.
存在しないことが背理法によって示すことが可能とわかっている.
| チューリングマシンの停止性問題 |
背理法を用いる.
「停止性を判定できる」プログラム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は存在しない | チューリングマシンの停止性問題の証明 |
この章を学んで新たに学べる
Comments