05turing_machine.tex

%#!platex main.tex

\chapter{チューリングマシン}

\mystrong{まだここの部分書いてない!}

\section{チューリングマシン(Turing machine, TM)}

\subsection{時点表示(Instaneous description)}
\mystrong{時点表示}とは，ある時点でのTMの状態の記述のことである．その表記は，以下のようになる．

 \begin{eqnarray*}
  \alpha_1 &:& テープ状のヘッドより左の記号列 \\
  \alpha_2 &:& テープ状のヘッドの位置およびそれより右の記号列(ただし，テー
   プの右端まで続くブランク(以下，\mystrong{B})は除く) \\
  q &:& 有限制御部の状態
 \end{eqnarray*}
 このときのTMの時点表示は，
 \[
  \alpha_1 \hspace{1ex} q \hspace{1ex} \alpha_2
 \]
 ある時点ではTMは全て有限の状態であることに注意(テープの右端まで続く$B$
 は無限長であり得るが，$\alpha_2$でそれを無視している)．

\subsection{TMの動作例}

\myfigure{img/05ab.eps}{同数の$aa\cdots , bb \cdots$から成る記号列を受理する
 TM}

\begin{myexample}{同数の記号から成る記号列を受理するTM}
 \myexamplelabel{ex:05ab}
 \[
 L = \{a^n b^n \, | \, n \ge 1\}
 \]
 ，すなわち，同数の$aa\cdots , bb \cdots$から成る記号列
 を受理(=最終状態に達する)するTMを考える．

 これは，
 「入力記号$a,b$と$B$の他に$X,Y$を使う．$a \rightarrow X,
 b\rightarrow Y$に書き換えていく(それにより，もう読んだ文字を判別する)．」
 という方針によって構成できる．まずは，どんな動作にすれば良いかを箇条書
 きにしてみる．

 \begin{enumerate}
  \item ヘッド位置の$a$を$X$に書き換え．
  \item 右に動いていき，最も左側にある$b$を$Y$に書き換える．(先にブラン
        ク$B$が見つかれば，$a$の方が多い) \label{en:2}
  \item 左に動いていき$X$を探し，その1つ右を見る．
  \item そこが$a$であれば，$X$に書き換えて\ref{en:2}に戻って繰り返し．
  \item そこが$a$でなければ，右に動いて$b$を見つける前に$B$に達
        したらOK.($b$が見つかれば$b$の方が多い)
 \end{enumerate}

 このTMを定式化する．それは，次の有限の大きさの動作表を作ることに対応す
 る．結果として，表\ref{tb:05ab}のように，確かに表にできる．ただし，表に
 おいて，$q_0$はTMの開始状態，$q_f$はTMの終了状態，'-'は何もしないことを
 表す記号，$(q_i , A, \{L,R\})$は，「状態$q_i$に移り，テープ上の現在ヘッ
 ダの指す文字を$A$に書き換えた後，左か右に動く」ことを表すのに注意．

 TMにおいて「受理しない」とは，「最終状態に達しない」ということなので，
 例えばテープの1文字目に$b$がきた場合はその時点で受理しないことが確定す
 ることを表から確かめて欲しい．

 さて，このTMが入力$aabb$を受理する様子を，時点表示を用いて確かめる．

 \begin{enumerate}
  \item $q_0\hspace{1ex} aabb$
  \item $X\hspace{1ex} q_1\hspace{1ex} abb$
  \item $Xa\hspace{1ex} q_1\hspace{1ex} bb$
  \item $X\hspace{1ex} q_2\hspace{1ex} aYb$
  \item $q_2\hspace{1ex} XaYb$
  \item $X\hspace{1ex} q_3\hspace{1ex} aYb$
  \item $XX\hspace{1ex} q_1\hspace{1ex} Yb$
  \item $XXY\hspace{1ex} q_1\hspace{1ex} b$
  \item $XX\hspace{1ex} q_2\hspace{1ex} YY$
  \item $X\hspace{1ex} q_2\hspace{1ex} XYY$
  \item $XX\hspace{1ex} q_3\hspace{1ex} YY$
  \item $XXY\hspace{1ex} q_4\hspace{1ex} Y$
  \item $XXYY\hspace{1ex} q_4$
  \item $XXYYB\hspace{1ex} q_f$
 \end{enumerate}
\end{myexample}

\begin{table}
 \caption{同数の記号から成る記号列を受理するTMを表す表(横:読み取る文字,
 縦:状態)}
 \begin{center}
  \begin{tabular}{c|c|c|c|c|c}
   \hline
    & $a$ & $b$ & $X$ & $Y$ & $B$ \\
    \hline \hline
   $q_0$ & $(q_1, X, R)$& - & - & - &\\ \hline
   $q_1$ & $(q_1, a, R)$ & $(q_2, Y, L)$ & - & $(q_1, Y, R)$ \\ \hline
   $q_2$ & $(q_2, a, L)$ & - & $(q_3, X, R)$ & $(q_2, Y, L)$ & - \\ \hline
   $q_3$ & $(q_1, X, R)$ & - & - & $(q_4, Y, R)$ & - \\ \hline
   $q_4$ & - & - & - & $(q_4, Y, R)$ & $(q_f, B, R)$ \\ \hline
   $q_f$ & - & - & - & - & -  \\ \hline
  \end{tabular}
  \label{tb:05ab}
 \end{center}
\end{table}

\subsection{TMの拡張}
TMに様々な拡張を施しても，拡張前のTMで同じことができる．より具体的には，
同じ受理言語を持つということ．

まず，以下のような比較的単純な拡張を考える．

\myfigure{img/05multi_track.eps}{多重トラックを持つTM}

\begin{description}
 \item [メモリを積んだTM] \mbox{} \\
             FCに有限ビッ
             トの記憶があって，それを制御に使えると考えて良い． \footnote{FCの
             各状態に対して，記憶する$m$ビットの内容に対応する$2^m$個の状態を
             作れば良い．それで，$q_0$を$0$に，$q_5$を$101$にとかすればよい．}
 \item [多重トラックを持つTM(図\ref{fig:img/05multi_track.eps})] \mbox{} \\
             この遷移関数は
             \[
             \delta : Q \times \Gamma^k \rightarrow Q \times \Gamma^k \times
             \{L, R\}
             \]
             で表される写像となるが，これは，テープ記号を$|\Gamma|^k$種にすれば，単一トラックで実現可
             能なことである． \footnote{例えば，多重トラックで「一気に$a,b,c$を読み取る」こ
             とを，テープ記号を増やした単一トラックで「$\zeta$を読み取ること」
             に対応させたりすれば良い．}
\end{description}

このようにTMを拡張すると，TMは次のことができるのが容易に分かる．
\footnote{このように拡張しないでももちろんできます．例えば，印付け
は，テープ状でデータ部分とデータを指す部分を大きく離せばできますね．}

\begin{description}
 \item[印つけ] \mbox{} \\
            2重トラックを持つTMを使えば，片方のトラックを印つけに使える．例えば，もう読んだ
            ところの2トラック目を$1$で埋めるなど．
 \item[記号の挿入] \mbox{} \\
            \begin{enumerate}
             \item テープ位置の記号をFCに覚える(FCの状態数がテープ記号集
                   合$|\Gamma|$
                   よりも十分に大きければ，FCの状態をテープ記号に対応さ
                   せることができる)．
             \item 挿入したい記号を書き込んで右へ．
             \item 1へ戻って繰り返し．
            \end{enumerate}
            ただしこのやり方は，挿入部より右の記号を全てずらしているので
            時間は掛かる． \footnote{データ構造のベクタ(配列)が挿入に
            弱いとされるのと同じことですね．}
 \item[記号の削除] \mbox{} \\
            \begin{enumerate}
             \item 右に動いてヘッド位置の記号を覚える．
             \item 左に動いて覚えた記号を書いて右へ．
             \item 1に戻って繰り返し．
            \end{enumerate}
\end{description}

更なる拡張を見てみる．

\begin{description}
 \item[多テープのTM] \mbox{} \\
            図5．$k$本のテープを持つ多テープのTMは，$2k$本のトラックを持つ他
            トラックのTMでシミュレート可能．

            多テープの各テープに対応するトラックを，以下のようにペアにす
            る(図6)
            \begin{itemize}
             \item ひとつはテープの内容
             \item もうひとつは，多テープのヘッド位置の印づけ
            \end{itemize}
            各トラックの印づけした位置を順次探し，そこの記号をFCに記憶し
            ていけば良い．

            
\end{description}

以上，いくつかの拡張を見たが，これらはは所詮テープを増やしたりしただけで
あり，多項式時間におさまる計算である．\mystrong{ここの記述は弱い．もう
ちょっと授業進んだら補完します．}

\subsection{非決定性TM(Non-deterministic turing machine, NTM)}
TMの拡張として，NFAに類似した以下の特徴を持たせることができる．
\begin{itemize}
 \item 動作が複数種類あり得る．
 \item 最終状態に至る可能性があれば受理．
\end{itemize}
このようなTMを，\mystrong{非決定性TM}(以下，\mystrong{NTM})と呼ぶ．

NTMは，決定性TM(DTM)\footnote{拡張していないTMをNTMと対比させるとき，特
にこう呼ぶ．}でシミュレート可能である．

以下で，実際のシミュレートの過程を追ってみる．方針を示すために，図
\ref{fig:img/05dtm_sim_ntm.jpg}を見て欲しい．

\myfigure{img/05dtm_sim_ntm.jpg}{DTMによるNTMのシミュレーション}

この木はTMの探索空間を表していて，各ノードは一意な(状態，ヘッド位置，テープ状態)，す
なわち，TMの一状態に対応している．

これらノードのうち，(いくつかある)最終
状態を素直に\mystrong{深さ優先探索}で探すのがNTMと言える．各ノードから子
ノードに移るときに，候補がいくつかあるのがNTMたる所以だ．

一方，これらノードを順番を決めて\mystrong{幅優先探索}で探すことによ
り，DTMでNTMをシミュレートできる．
以下，具体的なシミュレート法を記述する．

まず，次の3本のテープを持つDTMを用意する．

\begin{description}
 \item[テープ1] 入力記号列．読み込み専用．
 \item[テープ2] 1から$r$までの数の有限列．ここで$r$は，現ノードから見た
            子ノードの数．例えば，図
            \ref{fig:img/05dtm_sim_ntm.jpg}の各深さのノードに左から
            $1,2,\cdots$と番号が付いていたとすると，深さ3段目の左から2番
            目のノードにいることを表すには，テープ2に$113$を書く．このよ
            うに，長さ$n$の列は，深さ$n$のノードにいることを示す．
 \item[テープ3] 作業用．
\end{description}

このDTMは，以下のアルゴリズムに従って動作する．

\begin{mypre}{DTMによりNTMをシミュレートするアルゴリズム}
for (n = 0; true; ++n) {  // nはツリーの深さに対応
  長さnの1からrの数の列を初期化 on テープ2;
  while (全てのノードを表す列をテープ2に生成し終わっていない) {
    テープ1の内容をテープ3にコピー;  // 各ループで，元の入力記号列を破壊しないため
    テープ2の内容に沿ってノードを移動;  // そのようなノード移動になるようにTMは動作する
                                        // この際，テープ1には手を触れず，テープ3を読み書きする
    if (受理ノードに達した) 成功;
    else 次の長さnの1からrの列を生成 on テープ2;
  }
}
\end{mypre}

このアルゴリズムを見て分かったとおり，終了状態までのステップが$n$だとす
ると，NTM/NTMをシミュレートしたDTMの計算量は$r^n$になる．


\subsection{Random Access Machine}
TMは，基本的にヘッド位置の左右一つ分までしか読み書きしないマシンであった
が，以下のようにランダムアクセス可能なマシンもTMでシミュレートできる．
\begin{itemize}
 \item 任意の自然数を保持できる，$0,1,2 , \cdots$の番号のついた無限
       個のメモリ語
 \item 任意の自然数を保持できる有限本のレジスタ
 \item 有限種の命令，個々の命令はTMでシミュレート可能
 \item 命令はメモリに収める．次命令の選択は命令で可能
\end{itemize}
このシミュレートは，多テープのTMで可能．

\subsubsection{構成}
\begin{description}
 \item[テープ0] メモリを表現
 \item[テープ1] プログラムカウンタ(メモリの番地を指す)
 \item[テープ2から(2+k)] k本のレジスタ
\end{description}

\subsubsection{動作}
\begin{enumerate}
 \item テープ1の内容と合うものをテープ0から探し出す \label{en:05RAM1}
 \item その内容を命令として実行(TM内でシミュレート可能)
 \item \ref{en:05RAM1} に戻り繰り返し
\end{enumerate}

この計算も多項式時間で収まる．このように，TMでは現代のコンピュータのシミュレー
トまでできてしまう．


\section{チャーチ=チューリングのテーゼ(Church-Turing Thesis)}
\mystrong{チャーチ=チューリングのテーゼ(Church-Turing Thesis)}，或いは
\mystrong{チャーチ=チューリングの仮説(Church-Turing Hypothesis)}とは，
\[
 計算可能なものは，TMで処理可能
\]
という主張である．これは，そもそも「計算」という概念をはっきり定義してい
ないので，証明するような事柄ではなく，ただの主張らしい．


\section{決定性2スタックマシン}
\myfigure{img/05_2stackDPDA.eps}{決定性2スタックマシン}

図\ref{fig:img/05_2stackDPDA.eps}で表される，\mystrong{決定性2スタックマシン}を考える．
これは，TMを完全にシミュレートできる2本のスタックを持つDPDA(決定性プッシュダウンオートマトン)であり，
\begin{itemize}
 \item 1本のスタックは，TMのヘッドより右の記号を収納
 \item もう一本のスタックは，TMのヘッドより左の記号を収納
\end{itemize}
という構成を取る．便宜的に，前者を右，後者を左と呼ぶことにすると，例えば
TMのヘッドを右に動かす動作は，右のスタックからポップした記号を左のスタッ
クにプッシュする動作になる．

次に，決定性2スタックマシンをシミュレートすることのできる，計数機械を見る．

\section{計数機械(Counter machine)} \label{sec:05counter}
\mystrong{計数機械(Counter machine)}は，以下のような構成を持つ．
\begin{itemize}
 \item 読み込み専用の入力テープ
 \item 有限本の$\pm 1$できるカウンタ
 \item 有限制御部
 \item 以下のような遷移関数
       \[
       (カウンタが0か否か)^n \times \Sigma \times Q \rightarrow (カウン
       タの増減)^n \times Q \times {L,R}
       \]
\end{itemize}

計数機械には，以下のような能力がある．
\begin{description}
 \item[加算] \mbox{} \\
            $A + B$を考えたとき，$A$の数だけあるカウンタを$-1$し，その後
            で$B$の数だけそのカウンタを$+1$すればよい．

 \item[減算] \mbox{} \\
            $A + B$を考えたとき，$A$の数だけあるカウンタを$-1$し，その後
            で$B$の数だけそのカウンタを$-1$すればよい．
            
 \item[定数倍の乗算] \mbox{} \\
            カウンタ$A$に$j$が入っているとき，カウンタ$B$に$k \times j$
            を入れる．

            これは，$A$をループ回数をカウンタ変数とみなし，ループのよう
            な形で実装できる．

            すなわち，$A$が0になるまで$-1$ずつ減らしながら，$B$を$k$ずつ増
            やす．$k$ずつ増やすのは，有限制御部の記憶を利用すれば可能．

 \item[定数での除算] \mbox{} \\
            カウンタ$A$に$j$が入っているとき，カウンタ$B$に$j / k$を入れ
            る．

            これは，$A$が0になるまで$k$ずつ減らしながら，$B$を1つずつ増
            やすことで実装できる．

 \item[定数での剰余] \mbox{} \\
            カウンタ$A$に$j$が入っているとき，FCの状態を$j \mod k$に対応
            させる．

            これは，$A$が0になるまで$-1$ずつ減らしながら，FCの状態を$k$
            種の中で順に変えていくことでできる．
\end{description}

\subsection{計数機械によるTMのシミュレート}
この小節で示すことを始めにまとめておく．ここで，$\Rightarrow$記号
は，「左辺は右辺でシミュレートされる」ことを示す．
\begin{eqnarray*}
  &決&定性2スタックマシンの1本のスタック \Rightarrow 計数機械の2本のカウンタ \\
  &\therefore& 2本のスタック \Rightarrow 4本のカウンタ  \\
 &4&本のカウンタ \Rightarrow 2本のカウンタ \\
  &\therefore& 2本のスタック \Rightarrow 2本のカウンタ \\
 &\therefore& 決定性2スタックマシン \Rightarrow 2本のカウンタを持つ計数機
  械 \\
 &T&M \Rightarrow 決定性2スタックマシン \\
 &\therefore& \mystrong{TM \Rightarrow 2本のカウンタを持つ計数機械}
\end{eqnarray*}

まず，計数機械のカウンタ2本で，1本のスタックを以下のようにしてシミュレー
トする．

対象のスタックが$k-1$種のスタック記号
\[
 Z_1, Z_2, \cdots , Z_{k-1}
\]
を持つとする．スタックの内容が
\[
 Z_{i_1}, Z_{i_2}, \cdots, Z_{i_m}
\]
であるとき，これを$k$進法の記述と見て自然数にエンコードする．
\[
 j = i_m + k i_{m-1} + k^2 i{m-2} + \cdots + k^m i_0
\]
ただし，スタックが空なら$j=0$

このようにカウンタ$j$をスタック記号$Z_1, Z_2, \cdots , Z_{k-1}$に対応さ
せると，確かにシミュレートできていることを確認する．

\begin{itemize}
 \item スタックに$Z_r$ をプッシュするには，カウンタを
       \[
        j' = k j + r
       \]
       とすればよい．尚，このような計算が計数機械に可能なこと
       は，\ref{sec:05counter}で示した．
 \item スタックからポップするには，
       \[
        j' = j / k
       \]
       とすればよい．
 \item スタックトップによって決定性2スタックマシンの動作を変えるには，
       \[
        j \mod k
       \]
       によって計数機械のFCの状態を変えればよい．
\end{itemize}

従って，4本のカウンタを持つ計数機械により，決定性2スタックマシンをシミュ
レートできる．

更に，4カウンタの計数機械は，2カウンタの計数機械でシミュレート可能
である．

4本のカウンタが$i, j, k, l$という値を持つとき，これを
\[
 I = 2^i \times 3^j \times 5^k \times 7^l
\]
という値を持つ1本のカウンタで一意に表現できる．例えば，4本のカウンタのう
ち，$i$を$1$増やすには，$I$を2倍すればよい．逆に，$k$を$1$減らすようなと
きは，$I$を$5$で割ればよい．また，$l$がゼロか否かの判定は，$I$を$7$で割っ
た剰余を見ればよい．

以上をまとめると，\mystrong{2カウンタの計数機械でTMはシミュレート可能で
ある}と言える．

\section{TMのテープ記号の制限}
テープ記号を3種$\{0,1,B\}$としても，一般のTMをシミュレート可能．元のテー
プ記号を$k$種とすると，$\log_2 k$個の$0/1$でエンコードすればよい．


\section{万能チューリングマシン(Universal Turing Machine)}
\mystrong{万能チューリングマシン(Universal Tring Machine)}とは，どんなTM
でもシミュレートできるTMである．\footnote{エミュレータの理論の基礎になっ
てます．}

これは，
\[
 [シミュレート対象のTMの記述]\, [区切り文字\$]\, [入力記号列]\, [ブランク \cdots]
\]
という入力をとり，自らの状態を
\[
 シミュレート対象の <状態，ヘッド位置の記号，次状態，書き込む記号，左右>
\]
の組を表す状態として持つTMである．

シミュレート対象のTMの状態数や入力記号の種類数には上界はないが，有限であ
る．従っ
て，シミュレータTMも有限の状態数と入力記号でシミュレートできる．

\subsection{多テープTMでの実現}
入力の他に，作業テープを2本使う．内訳は，シミュレート対象のTMの動作関数
で1本，シミュレート対象のTMの状態で1本．

入力テープの内容と状態テープの内容を用いて，動作関数テープ(先の入力)を探
索し，見つかった動作を実行すればよい．