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

bbrfkr

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

ここではチューリングが提唱した計算モデルであるチューリング機械について説明し、どのように動くか実際に見ていこう。

まずチューリング機械とは次の四つの要素からなる。

  • 有限な状態制御

  • テープ

  • テープヘッド

  • プログラム

有限な状態制御

有限な状態制御とは、チューリング機械の内部状態を指し示す要素$${q_0, q_1, \cdots q_n}$$および出発状態$${q_s}$$、停止状態$${q_h}$$を合わせた有限集合$${\{q_0, q_1, \cdots q_n, q_s, q_h\}}$$を指す。チューリング機械は状態$${q_s}$$の状態でプログラム実行を開始し、$${q_h}$$の状態でその動作を停止する。

テープ

テープとはアルファベットがある一方向に無限に並んだ点列だ。ここでアルファベットとは、そのチューリング機械においてテープに記録されうる記号のことである。テープは現在のコンピュータにおける主記憶装置（メモリ）と同じ役割を担い、チューリング機械が処理の過程で一時的に保持しておきたい情報を蓄えるのに使われる。

例えば、アルファベット全体を$${\Gamma \equiv \{0,1,b, \triangleright \}}$$と表す。ここで$${b}$$はその位置には何もデータが記録されていない（blank）ということを示し、$${\triangleright}$$はテープの一番左端、すなわちチューリング機械の実行時のテープヘッドの初期位置を表すこととする。このとき、次のようなテープを定義できる。

$$
Tape \equiv (\triangleright, 0,1,1,0,1,0,0,1,1,0,b,b,b,\cdots)
$$

通常特に断らない限りは、アルファベットには必ず空$${b}$$とテープ左端$${\triangleright}$$を含むとし、テープ左端には$${\triangleright}$$が記録されていることを仮定する。

テープヘッド

テープヘッドはテープに対してデータの読み取り・書き込みを実施できるデバイスのことだ。テープヘッドを介してチューリングマシンはテープのデータを読み書きすることができる。数学的にはテープ上のどの位置を現在チューリングマシンが読み書きできるかを示すポインタの役割をする。
しかし、テープヘッドの実際の位置をチューリング機械自体が記憶している必要はない。テープヘッドのアトミックな操作は次の三つに限られている。

  • テープヘッドを左に動かす ($${= -1}$$)

    • ただし、ヘッドがテープの左端であるときのみ、例外的に動かない

  • テープヘッドを右に動かす ($${= +1}$$)

  • テープヘッドを動かさない ($${= 0}$$)

プログラム

チューリング機械におけるプログラムは以下のような組の集合である。

$$
(Q_p, L_p, Q_n, L_n, h)
$$

それぞれの記号は次の意味を持っている。

  • $${Q_p}$$: 現在の状態

  • $${L_p}$$: テープヘッドが示す部分のテープのアルファベット

  • $${Q_n}$$: 次の状態

  • $${L_n}$$: テープヘッドが示す部分のテープに書き込むアルファベット

  • $${h}$$: テープヘッドの動き

チューリング機械$${TM}$$を数学的に組$${TM \equiv (S,T,H,P)}$$と定義したとしよう。ここで$${S}$$は内部状態全体、$${T}$$をテープ、$${H}$$をテープヘッド、$${P}$$をプログラムとする。チューリング機械は次のように動作する。

  1. チューリング機械は内部状態$${q = q_s}$$、テープヘッドの位置$${h = 0}$$であるとする。

  2. 内部状態が$${q_h}$$ならば、停止する。そうでなければ次の処理に進む

  3. テープヘッドから現在の位置のテープ内容$${l}$$を読み出す

  4. プログラム$${P}$$から、$${Q_p = q, L_p=l}$$である要素$${p}$$を取り出す

  5. 取り出したプログラムの要素$${p}$$より、現在の状態を$${Q_n}$$で上書きし、テープヘッドが示す位置のテープ内容を$${L_n}$$で上書きする

  6. テープヘッドをプログラムの要素$${p}$$より、$${h}$$の内容に従って動かす

  7. 2.に戻る

さて、チューリング機械とはここまででどのように定義されるか、どのように動作するかまでは説明できたので、次回以降は実際に動かしてみて、具体的にチューリング機械を使ってどのような問題が解けるのかを見ていくことにする。

この記事が気に入ったらサポートをしてみませんか？