量子計算学習ノート - チューリング機械4

---

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

---

ここでは、チューリング機械の物理学的に合理的な変形について見ていこう。例えば両方向に無限長のテープを持ったチューリング機械や、1次元ではなく2次元以上の高次元テープを持つようなものが考えられる。

ここでは具体的に2つのテープを持つチューリング機械についてその定義を考えてみよう。2つのテープを持つチューリング機械は、これまで通りアルファベット$${\Gamma \equiv \{\triangleright, 0, 1, b\}}$$がテープに記録されるとし、次のようなプログラム行を持つとする。

$$
(q, x_1, x_2, q', x_1', x_2', s_1, s_2)
$$

ここで、それぞれの記号は次を意味する。

• $${q}$$: チューリング機械の現在状態

• $${x_i}$$: $${i}$$番目のテープに対し、ヘッドが読む現在のアルファベット

• $${q'}$$: チューリング機械が次に遷移する状態

• $${x'_i}$$: $${i}$$番目のテープに対し、ヘッドが現在の位置に書き込むアルファベット

• $${s_i}$$: $${i}$$番目のテープに対し、ヘッドが動く方向($${+1, -1, 0}$$)

このように定義したチューリング機械は、実は1つのテープを持つチューリング機械と等価であることがわかっている。

チューリング機械同士が等価であるとはどういうことか？

私達はチューリング機械が計算可能な関数のクラスに興味がある。したがって、チューリング機械（厳密にはその計算モデル）の等価性は片方のチューリング機械が他方のチューリング機械の計算を必ず行えること、つまり相互に計算をシミュレート可能なときであると定義する。

2つのテープを持つチューリング機械は1つのテープを持つチューリング機械をシミュレート可能であることは自明だ。2つ目のテープを使用しなければいいのだから。このため、1つのテープを持つチューリング機械が2つのテープを持つチューリング機械の計算をシミュレートできるかが議論の争点になる。厳密に議論しないが、実際にこれはできる。要は2つのテープの内容を1つのテープに再現できればいい。なにがしかのオーバーヘッドは生じるものの、無限に長いテープを利用しているのでこれは可能であることがわかっている。

同様にチューリング機械に対して、物理学的に合理的な変形を加えたいかなる計算モデルも、大元のチューリング機械と等価であることを示すことができる。つまり、どんな変形を考えてもチューリング機械のいかなる側面も変更できないし、計算可能な関数のクラスを拡張することもできない。

興味あるチューリング機械の変形として、そのふるまいにランダム性を持たせるというものがある。具体的に言えば、次のようなプログラム行を持つチューリング機械が考えられる。

$$
(q, x, q_{H}, x_H, s_H, q_{T}, x_T, s_T)
$$

• $${q}$$: チューリング機械の現在状態

• $${x}$$: テープに対し、ヘッドが読む現在のアルファベット

• $${q_{H}}$$: コイン投げの結果が$${H=Head}$$、つまり表だった時に、遷移する状態

• $${x_{H}}$$: コインが表だった時に、ヘッドが書き込むアルファベット

• $${s_{H}}$$: コインが表だった時に、ヘッドが動く方向

• $${q_{T}}$$: コイン投げの結果が$${T=Tail}$$、つまり裏だった時に、遷移する状態

• $${x_{T}}$$: コインが裏だった時に、ヘッドが書き込むアルファベット

• $${s_{T}}$$: コインが裏だった時に、ヘッドが動く方向

このように、チューリング機械が次のプログラム行を実行するときにコイン投げを行い、その結果に応じてふるまいを変えるようなチューリング機械を考えることができる。しかし、このようなチューリング機械を考えてもチューリング機械の計算可能なクラスを拡張することはできない。

実際このようなチューリング機械の、コイン投げの結果の組み合わせによって取りうる状態遷移の仕方一つ一つに対する計算結果は、確率的ではない計算結果を決定的に出力する従来のチューリング機械の計算結果に対応する。したがって、ランダム性を持たせた先のチューリング機械は、複数の決定的チューリング機械から確率的に1つ選択して、計算結果を出力する機械に他ならないからだ。