はてぃーぽったーの備忘録

某授業まとめ+競プロの感想記事

チューリング機械の形式的定義および計算状況

こんばんは。前回は講義の概略をお話ししましたが、今回はチューリング機械の導入をしていこうと思います。今回の話は形式的定義および計算状況に限ったものなので、計算可能性にかかわる本質的(と思われる)な話は次回以降の記事になります。

 

注意

現状、 二年前の名残から図などを自前で用意しない記事構成になっていますが後ほど追加する予定です。当時はスライドの補完的な立ち位置として書いていたものなので、授業スライドを併せて見るといいかと思います。

 

まず、チューリング機械とはどんなものでしょうか。両側無限単一テープチューリング機械の特徴としては、

  • 読み書き用の無限長のテープを持つ
  • テープには無限個のマス目が存在し、入力記号列はテープ状に存在している
  • 計算の初期状態として、入力記号列の書かれたマス以外は  \sqcup で埋められている
  • 現在地のマス目を示すヘッドが存在する
  • ヘッドは左右に1マスずつ動ける
  • この動きを制御するための、有限状態を持つ制御部が存在する

 

あくまで制御部はヘッドの動きを制御するものであり、ヘッドの具体的な位置を保持しているわけではないことに注意しましょう。

非決定性チューリング機械  M は以下のように形式的に記述されます。

 M=(Q, \Gamma, \Sigma, \delta, p_0, \sqcup, F) 

 Q: 状態の有限集合  ・ p_0: 初期状態

 \Gamma: テープ記号の有限集合

 \Sigma (\subset \Gamma): 入出力記号の集合

 \delta: 次動作関数:  Q\times\Gamma → 2^{Q\times\Gamma\times\{L,R\}} (非決定性ゆえに冪集合の形となる。
   決定性チューリング機械なら  Q\times\Gamma → Q\times\Gamma\times\{L,R\})

 \sqcup (\in\Gamma \  \Sigma): 空白記号

 F: 受理状態の集合

この中で最も馴染みのない表記は次動作関数  \delta だと思うので、具体例を示します。

 (q_i, g)\in Q\times\Gamma: q_i\in Q, g\in\Gamma に対する次動作関数  \delta の値が「 q_j に遷移し、 g h に書き換えた後、ヘッドを左に動かす」か、「 q_{j'} に遷移し、  g h' に書き換えた後、ヘッドを右に動かす」といった動作のとき、以下のように表現できます。

 \delta(q_i,g) = \{(q_j, h, L), (q_{j'}, h', R)\}

 

チューリングマシンの計算状況

ここからは計算状況について書きます。

記述の仕方は様々なものがありますが、ここではある瞬間での計算状況  C を以下のように表すこととします。

 C = (p, a_1 ... a_i ... a_n, i) \in Q\times\Gamma^*\times\mathbb{Z}

 a_1 ... a_n \sqcup 以外でテープ上の一番左の文字から一番右の文字までを繋げた文字列を指し、 i a_1 1番目と見た時のヘッド位置を示します。例えば  i=3 であれば  a_3 の文字が書かれているマス目をヘッドが指していることになります。

また、 a_1 はテープを左から見た時、 \sqcup 以外の文字が出てくる最初の位置の文字となります。 a_1 ... a_n の間に  \sqcup が入っていても、間を詰めるようなことはしません。

 a_1 \sqcup \sqcup \dots\sqcup a_i ... a_n において、 a_1 \sqcup に書き換えると何が起こるのでしょうか。この場合は、添え字の 1 番目の位置が変わります。具体的には、 a_{i} a_1 になります。それに伴い  a_1 があった位置の添え字は  1-(i-1)=2-i となります。つまり新たな計算状況  C' は、チューリング機械の状態が  p\mapsto q となるとすると  C' = (q, a_i\dots a_n,2-i) になります。

 

ところで  \Sigma に関してですが、確かにスライドでは入出力記号と書かれていますが(現在はどうなんでしょう)、 \Sigma\subset\Gamma ということなので個人的にはぼんやりしてる印象を受けます。

さて、上記のような添え字の急激なジャンプを防ぎたいとします。問題となっているのは  \sqcup を新たに書き込める点なので、

 \delta : Q\times\Gamma→2^{Q\times\Sigma\times\{L,R\}}

 \Sigma=\Gamma \setminus \{\sqcup\}

とすると防げることが分かります(この辺りをどう定義するかは自由だと思います、本質的には後の話に関わってこないので)。

 

最後に停止や受理など細々したお話をします。チューリング機械 Mは、

  • ある計算状況 (p, w, i)について次の動作が定義されない時、 M (p, w, i)で停止する
  •  w \in \Sigma^* が(p_0, w, 1) ⊢^*_M (q_f, v, i) ,q_f \in F を満たし(q_f, v, i) で停⽌するとき、 M wを受理するという
  • チューリング機械 Mが認識(受理)する⾔語 L(M) とは、 Mに受理される記号列全体のなす⾔語
  • チューリング機械は永遠に停止しないこともある

最後はかなり重要で、これがいわゆる決定可能というところに深く関わってきます。

 

今回はここまでにします。次回はチューリング機械の様々なモデルを扱います。

 

編集履歴

2018/12/03, 22:36 それに伴い a_iがあった位置の添え字は 1-iとなります。

→それに伴い a_1があった位置の添え字は 1-iとなります。

次動作関数の定義に言及した文脈の「~とすれば防げます。」の後に\Sigmaに関する補足説明を追加

2018/1/19, 18:46 それに伴い a_1があった位置の添え字は 1-iとなります。→それに伴い a_1があった位置の添え字は 1-(i-1)=2-iとなります。

2020/10/07, 19:36 全体的に文章や表現を見直しました