チューリングマシンとは? ざっくりまとめ

チューリングマシンについて、ざっくりとまとめてみました!

チューリングマシンとは

ざっくり言えば「抽象化されたコンピュータ」

チューリングマシンは、コンピューターの仕組みを抽象化したものです。

「本物のコンピューターができる仕事ならば、チューリングマシンにもその仕事ができる」という特徴があります。

チューリングマシンは、長さが無限のテープを記憶装置として使い、テープヘッドを左右に動かして文字を読み書きすることができます。文字を読み書きしつつ、最後に「受理(accept)」するか「拒否(reject)」するかを出力します。

超ざっくり言えば、

チューリングマシンは、テープを読み書きして、最終的に「お前はOK」なのか「お前はNG」なのかを判断する。

ということです。

チューリングマシンを決める7つの要素

チューリングマシンは、7つの要素で決めることができます。その7つの要素とは、

  1. Q: チューリングマシンが取ることのできる状態(states)の種類
  2. \Sigma: テープに最初に書かれている文字(alphabet)=入力の種類
    • 空白文字␣は含まない
  3. \Gamma: テープに書かれる文字の種類
    • 空白文字␣を含む、\Sigmaを含む
  4. \delta: チューリングマシンの1回ごとの動作。動作を決める関数を遷移関数と呼ぶ。
    • (条件=入力)
      1. どんな状態下で
      2. どんな文字を読むと
    • (結果=出力)
      1. マシンの状態がどんな状態に変化し
      2. どんな文字をテープに書き
      3. テープヘッドが左右どちらに動くか
  5. q_0: 最初のチューリングマシンの状態
  6. q_{\mathrm{accept}}: 最後に受理するときのチューリングマシンの状態
  7. q_{\mathrm{reject}}: 最後に拒否するときのチューリングマシンの状態

のことです。

テープは無限の長さを持っていて、はじめ、ある部分以外は空白で埋められています。

\def\arraystretch{1.5} \begin{array}{|c||c:c:c:c:c:c:c:c:c:c:} \hline \text{テープ} & \cdots & \text{␣} & \text{␣} &\text{あ} & \text{い} & \text{う} & \text{え} & \text{お} & \text{␣} & \text{␣} & \cdots \\ \hline \end{array}

本記事では、このように書くのは面倒なので、空白文字を省略して書きます。…は文字を省略しているものだと思ってください。

\def\arraystretch{1.5} \begin{array}{|c||c:c:c:c:c} \hline \text{テープ} & \cdots & \text{い} & \text{う} & \text{え} & \cdots \\ \hline \end{array}

遷移関数の表し方

遷移関数の表し方は \delta(\text{状態},\text{読んだ文字}) = (\text{新状態},\text{書き込む文字},\text{左or右}) です。

次のように、q_\text{ア}の状態で「う」が「あ」に書き換わってヘッドが右に進み、状態がq_\text{イ}に移行(yield)した場合を考えます。

\def\arraystretch{1.5} \begin{array}{c||c:c:c:c:c} \text{旧テープ} & \text{あ} & \text{い} & \colorbox{lightblue}{\text{う}} & \text{え} & \cdots \\ \hline \text{新テープ} & \text{あ} & \text{い} & \color{red}{\text{あ}} & \colorbox{lightblue}{\text{え}} & \cdots \end{array} \hspace{1em} \def\arraystretch{1.5} \begin{array}{c||c} \text{旧状態} & q_\text{ア} \\ \hline \text{新状態} & q_\text{イ} \end{array}

この場合、

\delta(q_\text{ア},\text{う}) = (q_\text{イ},\text{あ},\text{右})

と表すことができます。

計算状況(configuration)の表し方

ある時点でチューリングマシンを止めたときのマシンの状態テープの内容ヘッドの位置をまとめて計算状況(configuration)といいます。下の図では、計算状況がすべてわかりますね。

\def\arraystretch{1.5} \begin{array}{|c||c:c:c:c:c} \hline \text{テープ} & \text{あ} & \text{い} & \colorbox{lightblue}{\text{う}} & \text{え} & \cdots \\ \hline \end{array} \hspace{1em} \def\arraystretch{1.5} \begin{array}{|c||c|} \hline \text{状態} & q_\text{ア} \\ \hline \end{array}

上のように書くのは面倒なので、計算状況をまとめて1行で書き表す方法があります。上の計算状況をまとめて書き表すと

\text{あ} \text{い} q_{\text{ア}} \text{う} \text{え} \cdots

となります。

  • ヘッドより左側の文字
  • ヘッドの状態
  • ヘッドの位置にある文字とヘッドより右側の文字

を順番にならべればよいわけです。

認識と決定

認識

チューリングマシンMが受理する文字列を集めたものを

  • Mの言語(the language of M)、あるいは
  • Mによって認識された言語(the language recognized by M)といい、

L(M)で書き表します。

チューリングマシンが言語を認識するとき、言語はチューリング認識可能であるともいいます。

決定

チューリングマシンは、最後に受理する場合、最後に拒否する場合の他に、ループする場合があります。チューリングマシンが止まらず、延々と動き続ける場合です。

ループにはまらず、すべての入力に対して受理or拒否を決めることができるチューリングマシンを考えます。このようなマシンが言語を認識することを、マシンが言語を決定するといいます。このように、少なくとも1つのチューリングマシンによって決定される言語は、(チューリング)決定可能であるといいます。

まとめ

チューリングマシンのまとめ

  • チューリングマシンとは、抽象化されたコンピュータである
  • チューリングマシンは、無限の長さのテープに書かれている文字列を読み書きして、文字列を受理するか拒否するかを決める。
  • マシンは受理も拒否もせずに、ループする場合がある。
  • マシンが受理する文字列を集めたものを認識された言語という。
  • 全入力に対して必ず受理/拒否の判断をするチューリングマシンが、ある言語を認識することを決定するという。

参考文献

Sipser, M. (2013). Introduction to the Theory of Computation.