量子計算学習ノート - チューリング数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)}$$は停止する結果になる。これは明らかに矛盾である。

このことからチューリング機械にも少なくとも停止問題の内、解けない問題があることが明らかとなった。