日記「芦」
科学は何かを説明するでもなく、解釈をくだすことすらしない。 - John von Neumann チューリングマシンについて 2010/10/23(Sat.)This text was written years ago..
////
チューリングマシンについて
2008 12/25
------------------------------------------------------
・チューリングマシン
チューリングマシンとはチューリングテープという考え方に
基づいてあらゆる計算を行うためのマシンである。
数学的に「状態の集合K, 入力記号の集合Σ, テープ記号の集
合Γ, 状態遷移関数δ, 初期状態S0, 空白記号B, 受理状態F」
と定義されている。
用語や記号は深く考えなくとも、ルールを読めばそういう物
だと分かるハズ。
------------------------------------------------------
・チューリングテープとは
+----------------…
| B | B | B | B |
+----------------…
のように、幅を持ち無限に長いテープの上に値が並んでいる
ものである。はじめテープはBで埋め尽くされいる。
Bは空白という意味の記号である。
------------------------------------------------------
・チューリングマシンで遊ぶルール
用意するのは、チューリングテープと、自分で考えたδ、F。
①まず入力Σを受け付ける。入力は0と1で組み合わされる並
びで、それをチューリングテープの左から埋める。
例えば、「0」を入力すれば、
+--------------------…
| 0 | B | B | B | B |
+--------------------…
「1101」を入力すれば、
+--------------------…
| 1 | 1 | 0 | 1 | B |
+--------------------…
となる。
②現状態が、Fになるまでステップを踏む。
１ステップでは現状態とヘッダの示す値が、δに当てはまる
段を探し、それによって値を書き換え、ヘッダを左右のどち
らかに動かして、状態を変更する。
出てきた用語の説明をする。
現状態というのは、テープの様子ではなく、そういう名前の
変数Xだと思えばよい。Sn(nは自然数)で表され、初期はS0で
δによってS1とかS2になる。Fというのはその現状態のゴール
のことで、F=S5なら、現状態がS5になるのがゴール。
無事ゴールすると、マシンはYesを返して終了する。
ステップというのはターンとかフェイズとかそういう感じ。
δを説明する前にヘッダという概念を説明する。
[v ヘッダ]
+--------------------…
| 1 | 1 | 0 | 1 | B |
+--------------------…
[v ヘッダ]というのが文字通りヘッダである。vによって、
常にテープ上のどれか一つの値を指している。
このヘッダはvの下にある値を読み取ったり、あるいは値を
書き換えることができる(ただし空白を意味するBに書き換
えることはできない)。さらに、左右どちらかに１つ動ける。
右に一つ動けば
[v ヘッダ]
+--------------------…
| 1 | 1 | 0 | 1 | B |
+--------------------…
である。
δは次のような表。
F=S4
現状態 | ヘッダの指す値 || 書き換える値 | ヘッダの動く方向 | 次の状態
-------+----------------++--------------+------------------+---------
S0 | B || B | 右 | S3
S0 | 0 || 0 | 右 | S3
S0 | 1 || 0 | 右 | S1
-------+----------------++--------------+------------------+---------
S1 | B || B | 左 | S3
S1 | 0 || 1 | 右 | S2
S1 | 1 || 1 | 右 | S3
-------+----------------++--------------+------------------+---------
S2 | B || 1 | 右 | S4
S2 | 0 || 0 | 左 | S2
S2 | 1 || 0 | 左 | S3
-------+----------------++--------------+------------------+---------
上の例では
まず、入力した後
現状態は初めS0であるから、上の表のS0の段(3つある)を見て
ヘッダ(初めは一番左にある)の指す値が
B→Bに書き換えヘッダを右に1つ動かし、状態をS3にする
0→0に書き換えヘッダを右に1つ動かし、状態をS3にする
1→0に書き換えヘッダを右に1つ動かし、状態をS1にする
これが１ステップである。
次のステップでも同様。状態が違うので該当する段を見る。
と、いきなり状態S3なのに、その段がない、という場合には
Noを返してマシンを終わる。
-------------------------------------------------------
・まとめ
以上のようにこのマシンはYesかNoを返して終わることになる。
上のδ例では実は入力が「10」ならYes、その他ならNoを返す
という非常に単純なプログラムである。しかし、上手に作る
ことで大抵のことはできる。それもそのはず、チューリング・
マシンは「チューリング完全」という言葉を作ったように、
チューリング完全なのである。つまり、現在コンピュータで
できるプログラムは全てチューリングマシンで計算することが
できる、ということが1964年に数学的に証明されている。
文；枚方圏内
////
コメ(0) | トラ(0)
(c)Kero's World