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

---

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

---

この記事では具体的なチューリング機械の動きを確かめてみることにしよう。次のようなチューリング機械を考える。

• 状態集合$${S \equiv \{q_1, q_2, q_3, q_s, q_h\}}$$

• $${Tape \equiv (\triangleright, x_0, x_1, x_2, x_3, b, b, b, \cdots)}$$

  • ここで$${x_i}$$は任意の2進数($${0,1}$$)であるとする

• プログラム (番号は説明のためでプログラムの一部ではない) 

  • 1: $${(q_s, \triangleright, q_1, \triangleright, +1)}$$

  • 2: $${(q_1, 0, q_1, b, +1)}$$

  • 3: $${(q_1, 1, q_1, b, +1)}$$

  • 4: $${(q_1, b, q_2, b, -1)}$$

  • 5: $${(q_2, b, q_2, b, -1)}$$

  • 6: $${(q_2, \triangleright, q_3, \triangleright, +1)}$$

  • 7: $${(q_3, b, q_h, 1, 0)}$$

さて、このようなチューリング機械はどんな計算を実行できるか。プログラムをよく眺めてみるとわかってくるが、これはテープに記録された2進数$${x \equiv x_3x_2x_1x_0}$$を入力とし、一定値$${f(x) = 1}$$を返却する関数、アルゴリズムとみることができる。

まず1:によってテープは何もせずにヘッドを右へ移動する。その後状態は$${q_1}$$になる。

次に状態が$${q_1}$$になったので適用されるプログラムは2:、3:、4:となるが、テープには2進数$${x_0,x_1,x_2,x_3}$$が連なって記載されているので、実際に適用されるのは2:、3:になる。また遷移する状態は$${q_1}$$であり続ける。したがって$${b}$$が来るまでひたすらテープに$${b}$$を記録し続けヘッドを右へ移動する、ということを繰り返す。

さて、テープの内容はこの時点で$${Tape \equiv (\triangleright, b, b, \cdots)}$$となっていることに注意しよう。ヘッドが指すテープの内容は$${b}$$でしかないので、まず4: が適用されて状態は$${q_1}$$から$${q_2}$$に遷移し、ヘッドは一つ左に戻る。その後もテープの内容は$${b}$$だから、5: によってテープの内容を書き換えずにひたすらヘッドを左に移動させ状態は$${q_2}$$のまま、ということを繰り返す。

テープの左端$${\triangleright}$$に到達すると、6: により状態は$${q_3}$$に遷移して、テープには何もせずにヘッドを右へ動かす。

最後に7: が適用されて、テープに$${1}$$を出力して、状態は$${q_h}$$に到達し、チューリング機械は動作を停止する。

さて、一定値関数$${f(x) = 1}$$を計算するのにとんでもなく面倒なことをしてきたように感じるが、このチューリング機械を計算モデルとして利用すると、非常に多くの種類の関数を計算できることがわかっている。チューリング機械が計算できる範囲については次の記事でもう少し詳細に踏み込んでいくことにしよう。