量子計算学習ノート - チューリング数3
この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。
前回チューリング数を定義したので、このチューリング数を用いて「万能チューリング機械」と「停止問題」について述べる。まずは万能チューリング機械について説明しよう。
万能チューリング機械は、任意のチューリング機械のシミュレーションができるチューリング機械のことだ。万能チューリング機械$${UTM}$$はチューリング機械$${M}$$をシミュレートするために、次のようなテープの内容を期待する
$${M}$$のチューリング数$${T_M}$$の後に区切り文字としての空白$${b}$$が続き、その後に$${M}$$への入力$${x}$$が続く
このようなテープが与えられると、$${UTM}$$は$${M}$$の計算結果と同じ$${M(x)}$$を出力する。チューリング数$${T_M}$$を読み取って、対応するチューリング機械$${M}$$の動きをシミュレーションして動作するのだ。
このようなチューリング機械の存在から、もしかしたら数学的な問題はすべてチューリング機械で計算、解くことができると思うかもしれない。しかし実際はそうではなく、チューリング機械でも解くことができない数学的問題が存在する。そのような問題の具体例として「停止問題」がある。
停止問題とは「チューリング数$${x}$$に対応するチューリング機械は入力$${y}$$を与えられると停止するか?」 という問題だ。このような問題は一般的にはチューリング機械で解けない、そのようなアルゴリズムは存在しないことがわかっている。
このことを調べるために部分的な問題として「チューリング数$${x}$$に対応するチューリング機械は入力$${x}$$を与えられると停止するか?」という問題を考えることができる。さて今、この問題を解くことができるチューリング機械が存在すると仮定しよう。このようなチューリング機械は次のような関数$${h(x)}$$を計算できることになる。
$$
h(x) = \left\{
\begin{array}{l}
0 \ (チューリング数xのチューリング機械が、入力xで停止しないとき)\\
1 \ (チューリング数xのチューリング機械が、入力xで停止するとき)
\end{array}
\right.
$$
$${h(x)}$$を計算するアルゴリズムを$${HALT(x)}$$と表示することにする。このとき、次のようなアルゴリズム$${TURING(x)}$$を考える。
TURING(X) {
y = HALT(x)
if y = 0 {
halt
}
else {
loop forever
}
}
$${HALT}$$が問題なく定義されている、つまり停止問題を解くアルゴリズムが存在するなら、この$${TURING}$$に対応するチューリング数$${t}$$に対しても$${HALT}$$は停止し、値を出力することになる。
アルゴリズムをよく見ると、$${HALT(t)}$$は$${TURING(t)}$$が停止するとき$${1}$$になる。しかし、そのようなとき$${TURING(t)}$$は停止せず、無限ループに陥る。一方で$${HALT(t)}$$が$${0}$$になるならば、$${h(t)}$$の定義から$${TURING(t)}$$は停止しないはずだが、$${TURING}$$のアルゴリズムによると$${TURING(t)}$$は停止する結果になる。これは明らかに矛盾である。
このことからチューリング機械にも少なくとも停止問題の内、解けない問題があることが明らかとなった。
この記事が気に入ったらサポートをしてみませんか?