Aritalab:Lecture/Automata/TM - Revision history

Adm at 03:05, 7 May 2012

2012-05-07T03:05:35Z

Adm: /* 決定性１テープチューリング機械 */

2011-10-25T15:54:18Z

‎決定性１テープチューリング機械

Adm: /* 決定性１テープチューリング機械 */

2011-10-25T15:34:44Z

‎決定性１テープチューリング機械

Adm: /* 決定性１テープチューリング機械 */

2011-10-24T23:52:30Z

‎決定性１テープチューリング機械

Adm: /* 決定性１テープチューリング機械 */

2011-10-24T09:14:17Z

‎決定性１テープチューリング機械

Adm: /* 決定性１テープチューリング機械 */

2011-10-24T07:54:03Z

‎決定性１テープチューリング機械

Adm: /* チューリング機械 */

2011-10-24T07:52:25Z

‎チューリング機械

Adm: /* チューリング機械 */

2011-10-24T07:30:57Z

‎チューリング機械

Adm at 05:36, 7 July 2011

2011-07-07T05:36:34Z

Adm: /* 非決定性チューリング機械 */

2011-07-07T05:34:46Z

‎非決定性チューリング機械

← Older revision		Revision as of 03:05, 7 May 2012
Line 1:		Line 1:
		+	[[Aritalab:Lecture/Automata\|形式言語理論のトップページヘ]]
	==チューリング機械==		==チューリング機械==

@@ Line 17: / Line 17: @@
 状態遷移関数は
 : &delta;(q<sub>0</sub>, 0) = (q<sub>1</sub>, 1, +1) 　[状態、テープ記号、ヘッド位置]
-のように与えます。これは状態 q<sub>0</sub> のときにヘッド下に記号 0 があれば、次の状態 q<sub>1</sub> に移動してヘッドの記号を 1 に書き換え、ヘッドを右に 1 だけ移動させるという意味します。これが 1 ステップ分の動作です。
+のように与えます。これは状態 q<sub>0</sub> のときにヘッド下に記号 0 があれば、次の状態 q<sub>1</sub> に移動してヘッド位置の記号を 1 に書き換え、ヘッドを右に 1 だけ移動させるという意味します。これが 1 ステップ分の動作です。
 TM のコンディションは現在状態 q 、テープの開始位置から現在のヘッド位置までの内容全て s, 現在のヘッド位置からテープの終了位置までの内容全て t を三つ組みにした (q, s, t) で一意に指定できます。これを様相といいます。
 様相 S<sub>1</sub> から　S<sub>2</sub> に1ステップで移動できるとき、S<sub>1</sub> &rArr; S<sub>2</sub> と書きます。

@@ Line 20: / Line 20: @@
 TM のコンディションは現在状態 q 、テープの開始位置から現在のヘッド位置までの内容全て s, 現在のヘッド位置からテープの終了位置までの内容全て t を三つ組みにした (q, s, t) で一意に指定できます。これを様相といいます。
 様相 S<sub>1</sub> から　S<sub>2</sub> に1ステップで移動できるとき、S<sub>1</sub> &rArr; S<sub>2</sub> と書きます。
-入力列 x に対して、ある受理状態 f &isin; F と何らかのテープ記号列 y, z &isin; &Gamma;<sup>*</sup> が存在して、(q<sub>0</sub>, &epsilon;, x) &rArr;...&rArr; (q, y, z) であれば、 x は受理されたといいます。
+入力列 x に対して、ある受理状態 q<sub>f</sub> &isin; F と何らかのテープ記号列 y, z &isin; &Gamma;<sup>*</sup> が存在して、(q<sub>0</sub>, &epsilon;, x) &rArr;...&rArr; (q<sub>f</sub>, y, z) であれば、 x は受理されたといいます。
 受理されない語に対して、TM は停止しない場合もありえます。

@@ Line 90: / Line 90: @@
 つまり、10 の入力文字列にかかわらずヘッド位置を +1 させていき、b を見つけた時点で &minus;1 戻ります。戻った位置が 0 なら更にもうひとつ戻り、二つ 0 が続いたときのみ q<sub>Y</sub> 状態になります。
-; 文字列の長さの差を計算するDTM
+;例：文字列の長さの差（または引き算）を計算するDTM
 <center>
 &Gamma; = { 0, 1, $, b }, &Sigma; = {0, 1}<br/>
-Q = { ちょっと複雑 }
+状態集合 Q = { ちょっと複雑 }
 </center>
-プログラムを書き下すのは煩雑なので、ヘッドの動きだけで解説します。
+プログラム（＝状態遷移関数）を書き下すのは煩雑なので、ヘッドの動きだけで解説します。
 二つの文字列の長さだけが 0<sup>m</sup>10<sup>n</sup> とテープに書かれていると仮定します。
-ここで m - n &le; 0 ならその長さ分の0, m - n < 0 なら0を返すプログラムを考えます。
-まずDTMは最初の 0 を $ に置き換え、右へ移動して 1 の右隣にある 0 を 1 に変えます。そして、次に左方向に $ に出会うまで戻ります。これを繰り返します。
+ここで m - n > 0 ならその長さ分の 0 を返し、m - n &le; 0 なら長さ分の 1 を返すプログラムを考えます。
 すると最後に
-# 0<sup>n</sup> が全て 1 に書き換わり、右に 0 を探しに行って空白に出会う
+# m > n の場合： 0<sup>m</sup> を n+1 回 b に書き換え、右に 0 を探しにいって空白 b に出会う
-# 0<sup>m</sup> が全て 1 に書き換わり、左に 0 を探しに行って $ に出会う
+# m &le; n の場合： 0<sup>n</sup> を m 回 1 に書き換え、左に 0 を探しに行って b に出会う
-のどちらかに遭遇します。前者のときは、テープに n+1 個の $ が書き込まれているので右端の $　を 0 に書き換え、残った 1 を全て b にします。
+のどちらかに遭遇します。前者のときは、テープに n+1 個の b が書き込まれているので一度左端に戻って最右の b を 0 に書き戻し、0 をこえて右側に移動し、残った 1 を全て b にします。
-後者のときは、結果が 0 になるので、残った01の文字を全て b にします。
+後者のときは右側に移動し、残った 1 を全て b に、更にその右に残った 0 を全て 1 に変えます。（このとき 0 が残っていない可能性もあり、その時の最終結果は全て b です。）
 ===多重トラックチューリング機械===

@@ Line 16: / Line 16: @@
 テープはあらかじめ空白で埋められているとし、初期状態は q<sub>0</sub> です。
 状態遷移関数は
-: &delta;(q<sub>0</sub>, 0) = (q<sub>1</sub>, 0, +1)
+: &delta;(q<sub>0</sub>, 0) = (q<sub>1</sub>, 1, +1) 　[状態、テープ記号、ヘッド位置]
 のように与えます。これは状態 q<sub>0</sub> のときにヘッド下に記号 0 があれば、次の状態 q<sub>1</sub> に移動してヘッドの記号を 1 に書き換え、ヘッドを右に 1 だけ移動させるという意味します。これが 1 ステップ分の動作です。
 TM のコンディションは現在状態 q 、テープの開始位置から現在のヘッド位置までの内容全て s, 現在のヘッド位置からテープの終了位置までの内容全て t を三つ組みにした (q, s, t) で一意に指定できます。これを様相といいます。

@@ Line 66: / Line 66: @@
 |style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:1em"| b
 |style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:1em"| 1
-|style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:1em"| 1
+|style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:1em"| ...
 |style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:1em"| 0
 |style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:1em"| 0
@@ Line 78: / Line 78: @@
 </center>
-例として 1100 と書いてあるテープ上で01列の開始部分（左端）を初期ヘッド位置としてスタートさせます。例えば 1100 という入力に対する動作を考えてみます。
+例として 1...00 と書いてあるテープ上で01列の開始部分（左端）を初期ヘッド位置としてスタートさせます。
 # 初期状態 q<sub>0</sub>
 ## テープの入力が0でも1でも、初期状態 q<sub>0</sub> のままヘッドを +1 します

@@ Line 5: / Line 5: @@
 オートマトンとの根本的な違いはテープ上に自由に読み書きができる点です。
 まず、決定性の１テープチューリング機械 (DTM: Deterministic one-tape Turing Machine) を定義しましょう。
@@ Line 22: / Line 23: @@
 受理されない語に対して、TM は停止しない場合もありえます。
-;入力された二進数が4の倍数であることを認識するDTM
+;例：入力された二進数が4の倍数であることを認識するDTM
 <center>
 &Gamma; = { 0, 1, b }, &Sigma; = {0, 1}<br/>
-Q = {q<sub>0</sub>, q<sub>1</sub>, q<sub>2</sub>,
+Q = {q<sub>0</sub>, q<sub>1</sub>, q<sub>2</sub>, q<sub>Y</sub>, q<sub>N</sub>}
-q<sub>3</sub>, q<sub>Y</sub>, q<sub>N</sub>}
+| &nbsp;
-−
+|
 {| class="wikitable"
-| q || 0 || 1 || b
+|+ 状態遷移関数
 |-
-| q<sub>0</sub>
+! q<sub>0</sub>
 | (q<sub>0</sub>, 0, +1)
 | (q<sub>0</sub>, 1, +1)
 | (q<sub>1</sub>, b, -1)
 |-
-| q<sub>1</sub>
+! q<sub>1</sub>
 | (q<sub>2</sub>, b, -1)
-| (q<sub>3</sub>, b, -1)
+| (q<sub>N</sub>, b, -1)
 | (q<sub>N</sub>, b, -1)
 |-
-| q<sub>2</sub>
+! q<sub>2</sub>
 | (q<sub>Y</sub>, b, -1)
 | (q<sub>N</sub>, b, -1)
 | (q<sub>N</sub>, b, -1)
 |-
 |}
-</center>
-このDTMを
-<center>
 {| style="border-collapse:collapse; text-align:center"
 | || || ||
 |style="text-align:left"| ↓
@@ Line 62: / Line 65: @@
 |style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:1em"| b
 |style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:1em"| b
-|style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:5em"| 01の列
+|style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:1em"| 1
 |style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:1em"| b
 |style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:1em"| b
@@ Line 68: / Line 74: @@
 |style="border-bottom:1px solid; border-top:1px solid; border-left:1px solid; width:3em"| .....
 |-
 |}
 </center>
-と書いてあるテープ上で01列の開始部分（左端）を初期ヘッド位置としてスタートさせましょう。
-すると10の入力にかかわらずヘッド位置を +1 させていき、b を見つけた時点で -1 移動して戻ります。戻った位置が 0 なら更にもうひとつ戻り、二つ 0 が続いたときのみ q<sub>Y</sub> 状態になります。
+例として 1100 と書いてあるテープ上で01列の開始部分（左端）を初期ヘッド位置としてスタートさせます。例えば 1100 という入力に対する動作を考えてみます。
 ; 文字列の長さの差を計算するDTM

← Older revision		Revision as of 05:36, 7 July 2011
Line 113:		Line 113:

	結果として、UTMの計算能力でさえ、もとのDTMの計算能力と差がないことがわかります。		結果として、UTMの計算能力でさえ、もとのDTMの計算能力と差がないことがわかります。
		+
		+	<div align=right>
		+	次→　[[Aritalab:Lecture/Algorithm/NP\|クラスNP]]
		+	</div>

@@ Line 91: / Line 91: @@
 ===非決定性チューリング機械===
-非決定性チューリングマシン (UTM: Undeterministic Turing Machine) の場合、各状態と各テープ記号について動作の選択肢が有限個存在します。
+非決定性チューリングマシン (NDTM: Non-deterministic Turing Machine) の場合、各状態と各テープ記号について動作の選択肢が有限個存在します。
 これら選択肢の最大値を r とし、これら選択肢を 1 から r までの数字で表現します。