チューリング機械の様々なモデルについて - はてぃーぽったーの備忘録

※結構長くなります

概要
計算能力の等価性の証明
まとめ

概要

今回はチューリング機械(以降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$ を一個ずつ書いては消費していくイメージ）