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

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

認識と決定（判定）の違い、決定可能言語の例

情報数学 数学

今回はチューリング機械の決定可能性に関する話です。

目次

 

受理・認識・決定（判定）

下図に示すようなことを説明していきます。（ C_1\in Q ではないです）

f:id:mkwamezaki1007:20190121200717j:plain

認識と決定の違い

計算状況についての記事で最後に触れたように、TM の状態には大きく分けて三つのものがあります。

  1. 受理状態
  2. 拒否状態
  3. ループ状態

この中では特に 3 番目のループ状態が異質に見えます。例えば DFA で考えると適当な入力を与えて遷移させれば、入力を使い切った段階で動作が停止します。つまり、入力となる各文字は使いきりです。したがって、入力が有限長である限りは必ず有限時間内に動作が停止します。一方で TM のヘッドは左右に動き、それゆえ与えられた入力に対して停止しないことがあり得ます（無限ループを起こすプログラムを書いたことがあると思いますが、そういった類の動作です）。

 

TM M の入力 w に対する受理・認識・判定について説明する前に、開始状況・受理状況・拒否状況について定義しておきます。

M=(Q, \Gamma, \Sigma, \delta, p_0, \sqcup, F) として、

  • 開始状況: (q_0, w, 1) と表される計算状況（ q_0\in Q は初期状態）
  • 受理状況: (q_{accept}, w', i') と表される計算状況（ q_{accept}\in Q は受理状態）
  • 拒否状況:  (q_{reject}, w', i') と表される計算状況（ q_{reject}\in Q は拒否状態）

これらの定義のもとで、 M が入力 w\in \Gamma^* を受理することを以下のように定めます。

  1. C_1 は入力 w に対する M の開始状況
  2. 各 i に対し C_i は C_{i+1} に移る
  3. C_k が受理状況
  • 1-3を満たすような計算状況 C_1\dots C_k が存在する時、 M は w を受理するという。入力に対する拒否も同様に定義する。

 

受理が定義できたところで、 M が言語 L\subset \Gamma^* を認識することについても定義します。

  • M が受理する入力の集合を L とするとき、 M は L を認識するという。

これらの定義から、以下の事実が分かります。

  • M が受理する入力の全体を L(M) （ M が認識する言語と呼ぶ）とすると、

　　　　 w\in L(M) \Rightarrow M は入力 w に対して必ず停止する

　 が成り立つ。

一方で、 w\notin L(M) についての言及はなく、拒否するかループするかは分かりません。もしこの場合の挙動が拒否に限定されていれば、いかなる入力に対しても計算が停止するという嬉しい性質が得られます。以上の考察を踏まえ、 M が言語を判定することを定義します。

  • M が認識する言語を L(M) とする。ある言語 L'\subset \Gamma^* に対し、 \forall w'\in L' に対して
  1. w'\in L(M) \Rightarrow M は w' を受理する
  2. w'\notin L(M) \Rightarrow M は w' を拒否する

　 が成り立つ時、 M は L' を判定するという。

 

この話の締めくくりとして、Turing 認識可能な言語と Turing 判定可能な言語を定義します。

  • 任意の言語について、その言語を認識するような Turing 機械が存在する時、その言語を Turing 認識可能と呼ぶ。
  • 任意の言語について、その言語を判定するような Turing 機械が存在する時、その言語を Turing 判定可能と呼ぶ。

 

決定可能（判定可能）言語

ここでは決定可能言語の例について述べていきます。

が、まだ準備中です（いかんせん全部やろうとすると量が…優先的に書いてほしいものがあればコメント等で教えてください）