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

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

句構造文法と万能TMについて

情報数学 数学

今回は句構造文法（生成規則 P に対する制限がない文法）と万能TMについてお話していきます。 

目次

句構造文法とTM

f:id:mkwamezaki1007:20190119193245p:plain

証明のお気持ちは上図にほとんど集約されています。

TM M を、句構造文法 G の開始記号 S および w\in L(G) を入力とし、 S に対する書き換えを行っていった結果 w と一致するものが得られた時は入力 (S, w) を受理するとします。

まず、 L(G)\subset L(M) を示します。

w\in L(G), つまり G が生成する記号列 w を取ります。

入力記号列 w の後に区切り記号と開始記号 S を置き、生成規則に対応するような次動作関数を定義することにより S を書き換えていきます。 S から w を導出するような生成規則の適用経路は w\in L(G) より必ず存在するため、 M は入力 (S, w) を受理します。よって、 L(G)\subset L(M) です。

 

次に L(G)\supset L(M) を示します。

M が受理する記号列 w\in L(M) に対して、受理するまでの動作は G が w を生成する過程になっています。（つまり、 M の動作ではヘッドの指し示す位置の記号を書き換えていきますが、この書き換えを生成規則に変換してあげればいいです。）これによって L(G)\supset L(M) が示され、 L(G)=L(M) となります。細かな M の動作については割愛していますが、この辺りは適宜手元の資料を参照してください。

 

万能TM

次に万能TMについてです。まず、万能というのは認識能力が他のモデルと異なるということではありません（ TMのモデルの等価性の記事を参照）。これは、ある万能TM: U は任意のTM: M をエミュレートすることができるということです。今までは特定のTM: M に対する入力記号列 w を考えてきましたが、万能TM: U の入力はそういったTM: M および記号列 w であり、入力は \langle M,w \rangleと書きます。

M が w を受理するならば U は \langle M,w\rangle を受理

M が w を拒否するならば U は \langle M,w\rangle を拒否

つまり、記号列 w に対して入力されたTM: M を動作させているわけです。他のTMも同様に入力として受け取れるので、結果として任意のTMをエミュレートできるわけですね。これが万能TMの考え方です。

ただ、一つ気を付けたいのはあくまで U はただのTMなので、 M をそのまま動かせるわけではありません。TMはあくまで記号列を入力とするので、 M 自体も記号列に変換する、いわゆる「コード化」という作業が必要です。ただ、万能TMを使用した証明の際にはコード化の中身にまで言及する必要は無いので、 M の動作の記述には高レベルな記述を用いることが多いと思います。

 

次回は決定性のお話です。

 

 

編集履歴:

2020/10/26 全体的な表現の見直し

チューリング機械の様々なモデルについて

情報数学 数学

※結構長くなります

 

目次

概要

 

今回はチューリング機械(以降TMと表記します)の様々なモデルについて扱っていきます。今回扱うモデルは３つ。

1. 片側無限テープTM

2. 多テープTM

3. 決定性TM

前回の記事で導入したTMは非決定性の両側無限単一テープのモデル（以下標準TMと言います）でした。実はこの1と2と3および前回のTM、認識する言語は全く変わりません。計算の可能性という点では等価です。ではなぜこれらのモデルを扱うかというと、計算可能性の観点と複雑さの観点から１つずつ理由が挙げられます。

 

  • 計算可能性の観点

都合のいいモデルを用いて問題を考えられることが利点です。ある言語を認識する有限オートマトンを作るために、状態遷移図を考えることにします。この時、決定性有限オートマトン（DFA）よりも非決定性有限オートマトン（NFA）の方が頭の中で考えやすいです（遷移先を１つに限らず設定していいため）。そのうえDFAとNFAは計算能力の面で等価なので、計算能力が等しい限りは自分の都合のいいモデルで考える方が嬉しいです。

 

  • 計算の複雑さの観点

異なるモデルを用いることで、例えば時間計算量が変わる可能性があります。これは実際に標準TMで他のモデルのTMを模倣(エミュレート)した時に実感できると思います。

ここで、エミュレートという単語についてwikipediaさんが軽く説明してくれます。

語源は英語の"emulate"（エミュレート：模倣する・真似をする）からきており、そのとおり異なるハードウェアやソフトウェア環境を模倣・物真似をさせる技術である。模倣対象のシステムを近似や推論でモデル化する場合をシミュレート（simulate）と言う。エミュレーションやエミュレータは、模倣対象のシステムにおいて、予測できる現象より予測できない現象が支配的である場合に使われる。また、非常に高い安全性が要求される場合にも良く使われる。予測できる現象が支配的な場合や、完全に模倣することが難しい場合はシミュレーション技術を使う。

 

エミュレータ - Wikipedia

エミュレータは完全に内部仕様まで模倣するのに対し、シミュレータはある程度近似的な模倣が許されているわけですね。したがって、モデルのある性質における等価性を示すにはシミュレートではなくエミュレートまでやることが必要になります。以降では、様々なTMのモデルにおける計算可能性の等価性をエミュレートによって示していきます。

 

計算能力の等価性の証明

 TMの計算性能が等価であることを示すには、モデル１がモデル２をエミュレート可能であり、かつモデル２がモデル１をエミュレート可能であることを示せばよいです。互いの状態や出力などに相当するものを自分自身の定義で記述できればいいわけですね。

1. 片側無限テープTM

標準TMで片側無限テープTMをエミュレート可能なことは明らかです。よって、片側無限テープTMで標準TMをエミュレートすることを考えます。標準TMのテープのマス目で、適当な箇所を a_0 と定めます。そのマスの中心でテープを折り返し、重なった２つのマス目を１つぶんのマス目として見ます。 a_0 は a_0 自身と重なりますが、同じマスが二回現れるわけにはいかないので下図に示すような特殊なマス \$ を使用します（下図では ¢ になっています）。

f:id:mkwamezaki1007:20181204071833p:plain

前回の記事では計算状況について書きましたが、その時はテープ上の文字列の⊔を除いた左端の文字が添字の1番だったじゃないか！と思うかもしれません。しかし、計算状況はTMの形式的記述の外側での定義であり、ここでの添字の振り方とは関係ないため問題ありません。

さて、折り返した結果見た目は片側無限長のようになりました。しかし、文字の読み込み、書込み等は上か下のどちらかで行うことになるので、現在のヘッド位置が上を指しているのか下を指しているのか判断したいです。また、上下のテープの行き来がどうなるかも気になります。

この問題は、テープの折り返し地点で下側のテープに特殊なシンボルを用いると解決できます。

以上の考察から、（天下り的ではありますが）与えられた標準 TM M_1 に対し片側無限テープ TM M_2 の定義を以下のように書くことを考えます。

M_1 = (Q_1, \Gamma_1, \Sigma, \delta_1, p^1_0, \sqcup_1, F_1) : 標準TM

M_2 = (Q_2, \Gamma_2, \Sigma, \delta_1, p^2_0, \sqcup_2, F_2) : 片側無限テープTM

Q_2 = Q_1 \times \{U, D, D'\} （現在の状態 + 上下どちらを見ているか、あるいは特殊な状態か）

\Gamma_2 = \Gamma_1 \times (\Gamma_1 \cup \{$\})

\sqcup_2 = (\sqcup_1, \sqcup_1)

Q_2 = Q_1 \times \{U, D, D'\}

p^2_0 = (p^1_0, U)

\delta_2: Q_2 \times \Gamma \to Q_2 \times \Gamma_2 \times \{L, R\}（次の状態、書き込む内容、ヘッドを動かす向き）

要はテープに上下の概念が加わったことで状態 Q_1 が Q_2 に拡張された格好になっています。基本的に状態が q で上テープを見ている場合は (q, U) と表され、下テープを見ている場合は (q, D) と表されます。また、 \$ は左端下側のマスに存在する特別な記号です。この記号を用いてどのように上下のテープの行き来がなされているかを確認していきましょう。

  • 上テープから下テープへ

これは、もとの標準TMではヘッドを左に動かす操作ですが、テープを折り返した形だとヘッドを右に動かす操作になります。( a_0 → a_{-1} への遷移)　そこに注意して次動作関数を定義します。

  • 下テープから上テープへ

先ほどと話が違ってくるのは、左端にあるのは \Gamma_1に含まれない特殊な記号であるということです。この記号を使わずに下テープから上テープに移動しようとすると、例えば左端から2マス目に来て、その時下のテープを指す状態で、左にヘッドを動かす動作なら上のテープを指すように動作するように次動作関数を定義することになります。特に左端から2マス目を判断するあたりがめんどくさそうですね。分岐条件を追加すると定義が複雑になるので、そうすることなく下テープから上テープに遷移する式を定義したいところです。ここで、新しく定義した状態 D'を活用します。

発想としては、まず状態が (p, D) から(p', D) と遷移することでヘッドが左端に到達します。そしたら無条件で (p', D)から(p'', D') と遷移し、さらに (p'', D')から(p''', U)と遷移します。こうすることでスムーズに下テープから上テープに移動することができました。このような動作を次動作関数 \delta_2 に記述すれば証明は完了です。

 

f:id:mkwamezaki1007:20190119173013j:plain

 

ここで、一つの疑問としてなぜ D' を噛ませるのか、というものが挙げられます。これはヘッドを左右どちらかに動かさなければならないと定義したことに起因します。ヘッドがその位置に留まってもいい定義ならば、次に示す次動作関数を定義すればいいです。

\delta_2((p, D), (a_0, $) = \{(p', U), (a_0, $), S\} (Sはその場にヘッドを留まらせるという意味)

また、そう定義したとしてもやはりその計算可能性に相違がないことが知られています。


2. kテープTM

k テープTMで標準TMをエミュレート可能なことは明らかです。よって、標準TMで k テープTMをエミュレートすることを考えます。これは標準TMのテープを十分な長さを持つ 2k 個のトラックに分割し、そのうち k: 個を通常のテープのように用い、残りの [tex: k 個を各テープに対応するヘッド位置の記録用テープとして用います。

ここで次動作関数についておさらいをします。標準 TM における次動作関数の入力と出力は以下の通りです。

 

入力: （現在の状態, ヘッドの位置に書かれている記号）
出力: （次の状態, 今のヘッドの位置に書き込む記号, 書き込んだ後左右どちらにヘッドを動かすか）

 

k テープ TM においては以下の通りです。

 

入力: （現在の状態, 各ヘッドの位置に書かれている記号）
出力: （次の状態, 今の各ヘッドの位置に書き込む記号, 書き込んだ後左右どちらに各ヘッドを動かすか）

 

 したがって、今考えている 2k 個のトラックに分けた標準 TM で足りない情報は

  • ヘッドの代わりに置いた X の指す内容
  • 各 X の指す内容をどう書き換えるか
  • 各 X は状態に対応して左右どちらに書き写すか

あとは k テープ TM の状態と対応するように標準 TM の状態を定義してあげればよいです。

 

3. 決定性TM

非決定性TMで決定性TMをエミュレート可能なことは明らかです。よって、決定性TMで非決定性TMをエミュレートすることを考えます。

 平たく言えば幅優先探索です。それを3テープの決定性TMで実装します。

1本目のテープは、元の入力を保持します。

2本目のテープは、作業用として1本目のテープのコピーを持ちます。

3本目のテープは、2本目のテープの入力によって生じる分岐先の住所を保持します。

 

f:id:mkwamezaki1007:20190119182233j:plain

 

上図のように、入力に対して非決定的に選ばれる遷移先について、その住所となる番号を決めます。そして同じ高さにあるノードを辞書式に（左から）訪問することにより幅優先探索を実現します。テープ3上に生成した文字列を使い切ったら次の遷移先をテープ3上に書き込みます。（最大の分岐数を b として、 1,2,\dots,b を使い切ったら 11,12,\dots,1b,21,22,\dots を一個ずつ書いては消費していくイメージ）

まとめ

今回は複数のモデルにおけるTMの計算能力の等価性を示しました。

次回は句構造文法とTMの関係についてのお話と万能TMについてです。

 

編集履歴:

2019/1/19 18:54 片側無限テープTMの記号の誤植を修正

2020/10/26 11:00 表現を全体的に修正。

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

情報数学 数学

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

 

注意

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

 

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

  • 読み書き用の無限長のテープを持つ
  • テープには無限個のマス目が存在し、入力記号列はテープ状に存在している
  • 計算の初期状態として、入力記号列の書かれたマス以外は \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 全体的に文章や表現を見直しました

情報数学の講義で学ぶことの概略

情報数学 数学

これは私個人の経験則なのですが、講義の内容が何に役立つのかが見えて来ず、それゆえ勉強に身が入らないということが少なからずあると思います。そこで今日はこの講義で学ぶ内容はそもそもどういった分野に属しているのか、特にチューリングマシンはどういった点で役に立つのかをまとめていきます。

続きを読む

このブログについて

このブログは某大学の"情報数学B"の授業を元にしたものとなっています。私自身の認識を、このページをご覧の皆様と共有し、アウトプットの場とすることが目的です。可能な限り間違いのない記述をするよう努めますが如何せん私自身の理解が浅いもので、読んでいて「これは違うのでは？」ということが多々あると思います。その際は遠慮なくコメントを残していただけると幸いです。

 

また、ここでは一先ず第2回の授業以降、すなわちチューリング機械の導入以降の内容をまとめていきます。第1回に行われた前期の復習を書く予定は今のところございません。予めご了承ください。