§E15.4Turing 機械

最終更新

Turing 機械は、有限個の状態と遷移規則によって、有限文字列に対する一段ずつの計算を定める。無限テープは各入力で無限量の情報を同時に与える装置ではなく、計算の進行に応じて有限個のマスを使用するための記憶領域である。本記事では、配置、計算、受理、および停止を区別して定義し、テープ数や非決定性を変更しても、認識可能言語と決定可能言語のクラスが変わらないことを証明する。

1 単テープ決定性 Turing 機械

定義 1.1. 単テープ決定性 Turing 機械 (single-tape deterministic Turing machine) は

M=(Q,Σ,Γ,δ,q0,qacc,qrej)M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{acc}},q_{\mathrm{rej}})

という組である。ここで、QQは有限状態集合、Σ\Sigmaは入力アルファベット、Γ⊇Σ\Gamma\supseteq\Sigmaは空白記号⊔∉Σ\sqcup\notin\Sigmaを含むテープアルファベットであり、q0,qacc,qrej∈Qq_0,q_{\mathrm{acc}},q_{\mathrm{rej}}\in Qは互いに異なる。遷移関数は

δ ⁣:(Q∖{qacc,qrej})×Γ⟶Q×Γ×{L,R,S}\delta\colon (Q\setminus\{q_{\mathrm{acc}},q_{\mathrm{rej}}\})\times\Gamma \longrightarrow Q\times\Gamma\times\{L,R,S\}

である。L,R,SL,R,Sは、それぞれヘッドを左へ一マス動かす、右へ一マス動かす、および現在位置にとどめる命令を表す。受理状態と拒否状態からは遷移しない。

以下では、Turing 機械を TM と略記する。テープのマスをN\mathbb Nで添字付ける。有限入力から有限段だけ計算した時点では、空白でないマスは有限個に限られる。この有限性を配置の定義に組み込む。

定義 1.2.MMの配置 (configuration) は三つ組

C=(q,h,T)C=(q,h,T)

である。q∈Qq\in Qは現在状態、h∈Nh\in\mathbb Nはヘッド位置、T ⁣:N→ΓT\colon\mathbb N\to\Gammaは有限個の位置を除いて⊔\sqcupを値にとるテープ内容である。

q∉{qacc,qrej}q\notin\{q_{\mathrm{acc}},q_{\mathrm{rej}}\}かつδ(q,T(h))=(q′,a,D)\delta(q,T(h))=(q',a,D)とする。T′T'を

T′(i)={a,i=h,T(i),i≠hT'(i)= \begin{cases} a,&i=h,\\ T(i),&i\ne h \end{cases}

で定め、h′h'を、D=SD=Sならhh、D=RD=Rならh+1h+1、D=LD=Lかつh>0h>0ならh−1h-1、D=LD=Lかつh=0h=0なら00とする。このときCCからC′=(q′,h′,T′)C'=(q',h',T')へ一段で遷移する (one-step transition) といい、C⊢MC′C\vdash_M C'と書く。

入力w=a0⋯an−1∈Σ∗w=a_0\cdots a_{n-1}\in\Sigma^*に対する初期配置はC0=(q0,0,Tw)C_0=(q_0,0,T_w)である。ただし、Tw(i)=aiT_w(i)=a_i(i<n)(i<n)であり、i≥ni\ge nではTw(i)=⊔T_w(i)=\sqcupである。w=εw=\varepsilonの場合には全マスが空白である。

定義 1.3. 入力ww上のMMの計算 (computation) は、初期配置C0C_0から始まる、次のいずれかの配置列である。

  1. 全てのi∈Ni\in\mathbb NについてCi⊢MCi+1C_i\vdash_M C_{i+1}を満たす無限列C0,C1,C2,…C_0,C_1,C_2,\ldots。
  2. 全てのi<ti<tについてCi⊢MCi+1C_i\vdash_M C_{i+1}を満たし、CtC_tから一段で遷移する配置が存在しない有限列C0,…,CtC_0,\ldots,C_t。

(2)の列を極大有限計算 (maximal finite computation) という。遷移関数は全ての非停止状態とテープ記号の組で定義されるため、極大有限計算の最終状態はqaccq_{\mathrm{acc}}またはqrejq_{\mathrm{rej}}である。最終状態がqaccq_{\mathrm{acc}}であるときMMはwwを受理 (acceptance) し、qrejq_{\mathrm{rej}}であるときMMはwwを拒否 (rejection) する。いずれかの極大有限計算になるときMMはwwで停止 (halting) する。決定性により、各入力の計算は一意である。

定義 1.4. TMMMが言語L⊆Σ∗L\subseteq\Sigma^*の認識器 (recognizer) であるとは、任意のw∈Σ∗w\in\Sigma^*について

w∈L⟺M が w を受理するw\in L\quad\Longleftrightarrow\quad M\text{ が }w\text{ を受理する}

ことをいう。w∉Lw\notin Lの場合には、MMは拒否しても停止しなくてもよい。認識器をもつ言語を認識可能言語 (Turing-recognizable language) という。

MMがLLの決定器 (decider) であるとは、MMがLLを認識し、さらに全てのw∈Σ∗w\in\Sigma^*で停止することをいう。決定器をもつ言語を決定可能言語 (decidable language) という。

命題 1.5. 決定可能な言語は認識可能である。

証明.LLの決定器をDDとする。w∈Lw\in LならばDDは停止して受理し、w∉Lw\notin LならばDDは停止して拒否する。後者の動作は認識器の定義で許される。したがって、同じ機械DDがLLの認識器である。▨

例 1.6 (一進加算). 入力1m#1n1^m\#1^nから1m+n1^{m+n}を得る機械は、#\#を一時記号に置き換え、右側に残る11を一つずつ印付けし、そのたびに左側の列の右端へ11を移すことによって構成することができる。例えば11#11111\#111では、右側の三つの11を処理した後に1111111111が残る。

「右側の未処理記号を探す」「その記号に印を付ける」「左側の右端を探して11を書く」「区切りまで戻る」という各局面には有限個の状態しか要らない。反復回数は入力テープ上の記号数によって定まり、状態数によって定まるのではない。

TM が関数を計算することの一般の定義は、計算可能関数の記事の§E15.7 定義 1.1で与える。本例は、その定義に先立って、一段ずつの書換えとして計算の進行を追うものである。

2 多テープ機械の単テープ模倣

定義 2.1. 正の整数kkに対し、kkテープ決定性 Turing 機械 (k-tape deterministic Turing machine) は、定義 1.1と同じ有限集合Q,Σ,ΓQ,\Sigma,\Gammaと状態q0,qacc,qrejq_0,q_{\mathrm{acc}},q_{\mathrm{rej}}をもち、遷移関数を

δ ⁣:(Q∖{qacc,qrej})×Γk⟶Q×Γk×{L,R,S}k\delta\colon (Q\setminus\{q_{\mathrm{acc}},q_{\mathrm{rej}}\})\times\Gamma^k \longrightarrow Q\times\Gamma^k\times\{L,R,S\}^k

とした組である。配置は、状態q∈Qq\in Q、ヘッド位置h1,…,hk∈Nh_1,\ldots,h_k\in\mathbb N、および有限個の位置を除いて⊔\sqcupを値にとるテープ内容T1,…,Tk ⁣:N→ΓT_1,\ldots,T_k\colon\mathbb N\to\Gammaからなる組(q,h1,…,hk,T1,…,Tk)(q,h_1,\ldots,h_k,T_1,\ldots,T_k)である。δ(q,T1(h1),…,Tk(hk))=(q′,a1,…,ak,D1,…,Dk)\delta(q,T_1(h_1),\ldots,T_k(h_k))=(q',a_1,\ldots,a_k,D_1,\ldots,D_k)のとき、一段の遷移では、各iiについて位置hih_iへaia_iを書き、定義 1.2と同じ規則（左端で左へ動く命令は左端にとどまる）でヘッド位置hih_iをDiD_iに従って更新し、状態をq′q'へ移す。

入力wwの初期配置では、第11テープの内容を単テープの場合と同じTwT_wとし、他のテープを全マス空白とし、全てのヘッドを位置00に置く。計算、受理、拒否、および停止は、定義 1.3と同じ文言で定める。

次の証明では、一つの模倣配置が元の機械の一つの配置を正確に符号化するという不変条件を定め、元の一段ごとにその不変条件が保存されることを示す。

定理 2.2. 任意のkkテープ決定性 TMMMに対して、単テープ決定性 TMSSを構成することができる。任意の入力wwについて、次の三条件が成り立つ。

  1. MMがwwを受理することとSSがwwを受理することは同値である。
  2. MMがwwを拒否することとSSがwwを拒否することは同値である。
  3. MMがwwで停止することとSSがwwで停止することは同値である。

証明. テープ記号a∈Γa\in\Gammaに対して、ヘッドがそのマスを走査していることを表す印付き記号a˙\dot aを新たに用意する。SSのテープには

# u1 # u2 #⋯# uk #\#\,u_1\,\#\,u_2\,\#\cdots\#\,u_k\,\#

を置く。MMの第iiテープの内容をTiT_i、ヘッド位置をhih_iとする。uiu_iは位置00からある位置ℓi\ell_iまでを表す有限文字列であり、ℓi≥hi\ell_i\ge h_iかつ、全ての非空白位置jjについてℓi≥j\ell_i\ge jを満たす。位置jjの文字はTi(j)T_i(j)であり、位置hih_iの文字だけに印を付ける。ℓi\ell_iはこの条件を満たす最小値でなくてもよく、末尾に任意個の余分な空白記号を含めてよい。この形式の文字列を整形式符号と呼ぶ。整形式符号から余分な末尾の空白を無視して得る配置をDecode⁡\operatorname{Decode}と書き、配置CCを表す任意の整形式符号をcode⁡(C)\operatorname{code}(C)と書く。

SSは最初の有限回の走査で入力wwを整形式符号へ変換する。第1テープの符号にはwwを置き、その先頭記号に印を付ける。w=εw=\varepsilonなら⊔˙\dot\sqcupを置く。第2テープ以降の符号は⊔˙\dot\sqcupとする。したがって、得られた符号はMMの初期配置を表す。

整形式符号がMMの配置CCを表していると仮定する。SSは左から右へ一回走査し、各uiu_iの印付き記号を有限制御へ記憶する。kkとΓ\Gammaは固定された有限集合なので、kk個の記号とMMの現在状態をSSの有限状態に記憶することができる。その情報からMMの遷移関数を一回適用し、新状態、各テープへの書込み記号、および移動方向を得る。

次にSSは符号全体を走査し直す。各uiu_iでは、以前の印付き記号を指定された記号へ書き換え、移動方向に従って左隣または右隣の記号へ印を移す。左端で左へ動く場合には印を同じ位置に残す。右隣が区切り#\#である場合には、その直前へ空白記号を挿入してから印を移す。挿入は、右側にある有限文字列を一マスずつ右へずらす有限の走査で実行することができる。全ての更新を終えた後、SSは左端へ戻る。得られた文字列は、MMの次の配置C′C'の整形式符号である。符号を一段分更新する操作をUpdate⁡\operatorname{Update}と書けば、不変条件は

Decode⁡(Update⁡(code⁡(C)))=C′\operatorname{Decode} \bigl(\operatorname{Update}(\operatorname{code}(C))\bigr)=C'

である。この等式は、code⁡(C)\operatorname{code}(C)が余分な末尾の空白を何個含む場合にも成り立つ。

初期符号が初期配置を表し、模倣する一段が整形式性と配置の対応を保存するため、帰納法により、MMのtt段後の配置とSSのtt回目の模倣後の符号は全てのt∈Nt\in\mathbb Nについて対応する。MMの状態がqaccq_{\mathrm{acc}}またはqrejq_{\mathrm{rej}}になったとき、SSは対応する受理状態または拒否状態へ移る。それ以外では次の一段を模倣する。したがって、受理、拒否、および停止について三つの同値が全て成り立つ。▨

3 非決定性機械の決定性模倣

定義 3.1. 非決定性 Turing 機械 (nondeterministic Turing machine)NNは、定義 1.1の遷移関数を、各組(q,a)∈(Q∖{qacc,qrej})×Γ(q,a)\in(Q\setminus\{q_{\mathrm{acc}},q_{\mathrm{rej}}\})\times\Gammaに対して空でない有限集合

δ(q,a)⊆Q×Γ×{L,R,S}\delta(q,a)\subseteq Q\times\Gamma\times\{L,R,S\}

を割り当てる写像へ置き換えた組である。配置C=(q,h,T)C=(q,h,T)は単テープ決定性 TM と同じ三つ組である。(q′,a′,D)∈δ(q,T(h))(q',a',D)\in\delta(q,T(h))の一つを選んで定義 1.2と同じ規則で更新した配置C′C'の各々へ、CCから一段で遷移することができる。

入力ww上の計算木 (computation tree) は、初期配置を根とし、停止状態にない各配置の子を、そこから一段で遷移することができる全ての配置とする有限分枝木である。根から始まる極大な配置列を分枝 (branch) という。遷移先の集合が常に空でないため、分枝が有限であることと、その最終配置の状態がqaccq_{\mathrm{acc}}またはqrejq_{\mathrm{rej}}であることは同値であり、このとき分枝は停止する (halt) という。状態qaccq_{\mathrm{acc}}の配置へ到達する分枝を受理分枝 (accepting branch) という。

NNがwwを受理する (accept) とは、ww上の計算木に受理分枝が存在することをいう。NNが言語L⊆Σ∗L\subseteq\Sigma^*の認識器 (recognizer) であるとは、任意のw∈Σ∗w\in\Sigma^*について、w∈Lw\in LとNNがwwを受理することが同値であることをいう。全ての入力で全ての分枝が停止する非決定性 Turing 機械を決定器 (decider) とし、決定器は、受理分枝がなく全分枝が停止した入力を拒否する (reject) と定める。LLの決定器とは、LLを認識する決定器のことである。

時間や空間の資源を測る後続の記事では、読取り専用入力テープと固定有限本の作業テープをもつ非決定性機械が§E15.11 定義 1.1として別に定式化される。その定式化と本記事の単テープ非決定性機械はテープの構成だけが異なり、§E15.11 命題 1.3により、多項式時間の範囲で同じ言語のクラスを受理する。本記事では資源を測らないため、単テープの定式化だけを用いる。

深さ優先探索は、停止しない一つの分枝だけを探索し続ける可能性がある。したがって、模倣には計算木を深さの小さい順に調べる幅優先探索を用いる。

定理 3.2. 任意の非決定性 TMNNに対して、単テープ決定性 TMDDを構成することができる。

  1. 任意の入力wwについて、NNにwwを受理する分枝が存在することと、DDがwwを受理することは同値である。
  2. NNが全入力で全ての分枝を停止させるならば、DDは全入力で停止し、NNが受理分枝をもつ場合に限って受理する。

証明. 各配置から出る遷移に1,…,b1,\ldots,bの番号を付ける。ここでbbは全ての配置に共通する有限の上界であり、存在しない番号は無効な選択とする。有限語α=i1⋯it∈{1,…,b}∗\alpha=i_1\cdots i_t\in\{1,\ldots,b\}^*は、初期配置から順に第iji_jの遷移を選ぶ長さttの候補分枝を表す。

まず三テープ決定性機械BBを構成する。第1テープに入力ww、第2テープに候補語α\alpha、第3テープにNNの作業テープの複製を置く。BBは

ε, 1,…,b, 11,12,…,bb, …\varepsilon,\ 1,\ldots,b,\ 11,12,\ldots,bb,\ \ldots

という長さ優先順で候補語を一つずつ生成する。各α\alphaについて第3テープを初期配置へ戻し、第1テープの入力を用いて、α\alphaが指定する遷移を最大∣α∣|\alpha|段だけ実行する。途中で無効な選択または停止配置に達した候補は、その時点で調査を終える。受理配置に達した候補を見つけた場合にはBBは受理する。

BBは、同じ長さの候補語を調べる間、その深さにある有効な非停止配置が一つでも見つかったかを有限制御に記録する。ある深さの全候補を調べ終え、受理配置も有効な非停止配置もなければ、計算木を調べ尽くしたので拒否する。

NNに長さttの受理分枝があれば、その遷移番号列α\alphaは有限個の先行候補の後に必ず調べられ、BBは受理する。逆に、BBが受理するのは、ある候補語が実際にNNの受理分枝をたどった場合だけである。したがって、受理について同値が成り立つ。

次に、入力ww上でNNの全ての分枝が停止すると仮定する。この計算木の深さには有限の上界が存在する。実際、任意に深い節点が存在すると仮定する。根の子は有限個なので、そのうち一つは任意に深い子孫をもつ。その子に対して同じ選択を繰り返すと、有限分枝性により無限分枝を構成することができ、全分枝が停止するという仮定に反する。深さの上界をddとすると、BBは深さddまでの有限個の候補を調べた時点で、未停止の有効候補が残らないことを確認することができる。受理分枝を発見していなければ、その時点で拒否するようにBBを構成する。したがって、全分枝が停止する入力ではBBも停止する。

最後に、定理 2.2をBBへ適用して単テープ決定性機械DDを得る。同定理は受理、拒否、および停止を保存するため、DDは主張された二条件を満たす。▨

系 3.3. 単テープ決定性 TM、多テープ決定性 TM、および非決定性 TM のいずれを用いても、認識可能言語のクラスは同じであり、決定可能言語のクラスも同じである。

証明. 単テープ決定性 TM は、多テープ決定性 TM のテープ数を一つにした特別な場合であり、非決定性 TM の各配置からの遷移先を一つにした特別な場合でもある。したがって、単テープ決定性 TM で認識または決定することができる言語は、他の二モデルでも認識または決定することができる。

逆に、多テープ決定性 TM には定理 2.2を適用し、非決定性 TM には定理 3.2を適用する。前者は受理と停止を保存し、後者は受理を保存するとともに全分枝停止の場合には模倣機械も停止する。したがって、他の二モデルで認識または決定することができる言語は、単テープ決定性 TM でもそれぞれ認識または決定することができる。両向きの包含から二つの言語クラスはモデルに依存しない。▨

4 列挙器と認識器

機械モデル間の模倣とは別に、言語を入力ごとに判定する方法と、言語の要素を順次出力する方法を比較する。

定義 4.1. 列挙器 (enumerator) は、作業テープに加えて出力テープをもち、計算中に区切り記号で区切られた有限文字列を順次出力する決定性 TM である。列挙器EEが出力する文字列全体をL(E)L(E)と書く。出力順序は任意であり、同じ文字列を複数回出力してもよい。EE自身は停止してもしなくてもよい。

次の証明では、列挙器から認識器を作る方向には出力の監視を用い、認識器から列挙器を作る方向には全入力に対する計算の交差実行を用いる。一つの入力の非停止によって、後続入力の調査を妨げないことが後者の要点である。

定理 4.2. 言語L⊆Σ∗L\subseteq\Sigma^*が列挙器によって列挙されることと、LLが Turing 認識可能であることは同値である。

証明. まずL=L(E)L=L(E)となる列挙器EEがあるとする。認識器RRは入力wwを保存してEEを一段ずつ模倣し、文字列が一つ出力されるたびに、その文字列とwwを比較する。一致すれば受理する。w∈L(E)w\in L(E)ならばEEは有限時点でwwを出力するため、RRは受理する。w∉L(E)w\notin L(E)ならば一致は起こらず、RRは停止しないか、EEの停止後に受理しない状態で停止するようにしてもよい。したがってRRはLLを認識する。

逆に、LLの認識器をRRとする。Σ∗\Sigma^*の全要素を長さ優先の辞書式順序でs0,s1,s2,…s_0,s_1,s_2,\ldotsと並べる。列挙器EEは段階t=0,1,2,…t=0,1,2,\ldotsにおいて、R(s0),…,R(st)R(s_0),\ldots,R(s_t)の各計算を初期状態からtt段ずつ模倣する。あるR(si)R(s_i)がtt段以内に受理することを確認したらsis_iを出力する。既に出力したかを記録して重複を避けてもよいが、重複は列挙言語を変えない。

si∈Ls_i\in Lならば、ある有限段数rrでR(si)R(s_i)は受理する。t≥max⁡{i,r}t\ge\max\{i,r\}となる段階でEEはその受理を確認してsis_iを出力する。si∉Ls_i\notin LならばR(si)R(s_i)は受理しないので、EEはsis_iを出力しない。したがってL(E)=LL(E)=Lである。両方向の構成により同値が成り立つ。▨

注意 4.3 (Church–Turing の提唱). 「有限の手続きによって有効に計算することができる」という形式化以前の概念が、Turing 機械による計算可能性で尽くされるという主張は Church–Turing の提唱であり、数学的定理ではない。 Church–Turing の提唱に対して、本記事で証明した機械モデル間の同値や、別の形式的計算モデルとの同値は、各モデルの定義から証明される数学的定理である。

5 演習

問題 5.1.

  1. 単テープ TM の配置(q,h,T)(q,h,T)から一段遷移したとき、空白でないテープ位置が有限個のままであることを示せ。
  2. 多テープ模倣で印付き記号を使わず、各テープの内容だけを連結した場合に、元の配置を一意に復元することができない理由を説明せよ。
  3. 非決定性機械の計算木を深さ優先で探索すると、受理分枝が存在しても受理することができない場合がある。そのような計算木を一つ記述せよ。
  4. 認識器から列挙器を作る証明で、R(s0)R(s_0)の計算が終わるまで待ってからR(s1)R(s_1)を始める方法が正しくない理由を説明せよ。
解答 (演習の要点).
  1. 一段で書き換える位置はヘッド位置の一つだけなので、有限集合へ高々一要素を加えた集合も有限である。
  2. テープ内容だけでは各ヘッドが走査している位置を特定することができず、次に読む記号を決定することができない。
  3. 例えば根の第1子から無限分枝が続き、第2子が直ちに受理する木では、第1子を先に深さ優先で調べる探索は第2子へ到達しない。
  4. s0∉Ls_0\notin Lの場合にR(s0)R(s_0)が停止しなければ、その方法はs1s_1以降を一度も調べない。段階ごとの有限模倣が必要である。

▨

参考文献

  1. Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, Boston, 2013.Turing 機械の定義、モデルの変種、列挙器、および決定可能性を参考にした。
  2. John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 3rd ed., Pearson, 2007.Turing 機械の構成と計算能力が変種に依存しないことを参考にした。

前提記事