量子計算学習ノート - チューリング数2

---

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。

---

前の記事では算術の基本定理を証明した。この記事ではこれを用いて任意のチューリング機械が互いに異なる自然数に対応付けられることを示そう。

実際にチューリング機械を自然数に対応付ける前に、一般性を失わない形で対象とするチューリング機械の範囲を狭める。具体的には以下の制約を加える。

1. 片方に無限に長いテープを1つ持つとする

2. 記号には $${0, 1}$$の2つしか用いない

前者はすでにテープの変形によってチューリング機械が計算できる関数のクラスが変化しないことは述べた。問題は2の記号を2つしか採用しない点で、これは議論していない。

しかし、任意の文字は$${0, 1}$$の2つの文字列で2進数コーディングによって対応付けることができる。よって、このような仮定を置いたとしても多数の記号を持つチューリング機械の動作をエミュレーションすることができるため、一般性は失われない。

では実際にチューリング機械を自然数に対応させる処理を紹介しよう。まずチューリング機械の記号、状態、ヘッドの動きを自然数に対応させることを考える。

記号集合は仮定より$${\Gamma \equiv \{0, 1\}}$$だから、このままでよい。状態集合が$${S = \{q_i, q_1, q_2, \cdots, q_{k-1}, q_h\}}$$だとすると、$${q_i \to 0,\ q_j \to j\ (j \in [1, k-1]),\ q_h \to k}$$と対応付ければいい。ヘッドの動きは$${-1, 0, 1}$$をそれぞれ$${0,1,2}$$と対応付けるようにする。

次に、プログラムを先に対応させた自然数の列に変換する。例えばプログラム行として$${(q_3, 0, q_5, 1, 1)}$$という行があったとすると、これは$${(3,0,5,1,2)}$$という自然数列に対応させられる。
あとはプログラム行の対応するすべての自然数列を連結すればよい。以下のようなプログラム行の対応する自然数列が以下のように与えられたとしよう。

$$
(n_{11}, n_{12}, n_{13}, n_{14}, n_{15})\\
(n_{21}, n_{22}, n_{23}, n_{24}, n_{25})\\
\cdots \\
(n_{m1}, n_{m2}, n_{m3}, n_{m4}, n_{m5})
$$

すると、プログラムに対応する自然数の列は次のようになる。

$$
(n_{11}, n_{12}, n_{13}, n_{14}, n_{15}, n_{21}, n_{22}, n_{23}, n_{24}, n_{25}, \cdots, n_{m1}, n_{m2}, n_{m3}, n_{m4}, n_{m5})
$$

最後にこの自然数列から素因数分解表現を次のように作る。

$$
T = p_{1}^{1+n_{11}}p_{2}^{1+n_{12}}\cdots p_{5(i-1)+j}^{1+n_{ij}} \cdots p_{5m}^{1+{n_{m5}}}
$$

ここで$${p_i}$$は$${i}$$番目の素数だ。この自然数$${T}$$をチューリング機械に対応付ける自然数とする。

前の記事で示した通り、素因数分解が違えば対応する自然数も違うため、プログラムが異なるチューリング機械に対応する自然数は互いに異なるようになる。

このようにして決められたチューリング機械に対応する自然数$${T}$$を、そのチューリング機械のチューリング数という。なお、チューリング数の与え方は状態、ヘッドの動きの自然数への対応付けの仕方分存在するため、一意ではない。

次回はこのチューリング数を用いて万能チューリング機械という、チューリング機械を定義しよう。