Download presentation
Presentation is loading. Please wait.
1
チューリング機械 状態の有限集合 ヘッドの方向を表す。 L：１コマ左へ R：１コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数 初期状態 空白記号 受理状態の有限集合
2
チューリング機械の１ステップの動作（１） 有限制御部 のとき 状態 … …
3
有限制御部 に遷移する。 状態 … …
4
チューリング機械の１ステップの動作（２） 有限制御部 のとき 状態 … …
5
有限制御部 に遷移する。 状態 … …
6
初期様相 で定義されているステップから動作を開始して， 有限制御部 状態 … … …
7
以下，ステップを繰り返し，
8
動作停止時の様相 のとき， 入力語を受理する。 停止して， 有限制御部 状態 … …
11
… …
12
… …
13
… …
14
… …
15
… …
16
… …
17
… …
18
… …
19
… …
20
… …
21
… …
22
… …
23
… …
24
… …
25
… …
26
… …
27
… …
28
… …
29
… …
30
… …
31
… …
32
… …
33
… …
34
… …
35
… …
36
… …
37
… …
38
… …
39
… …
40
… …
41
… …
42
… …
43
… …
44
… …
45
… …
46
… …
47
… …
48
… …
49
… …
50
… …
51
… …
52
受理状態で停止したので，M41は入力語aaaabbbbを受理する。
… …
53
なお， である。
133
受理状態に遷移したので, M42 は入力語 aaaabbbbaaaa を受理する。
134
である。
Similar presentations
