チューリングマシンについて 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 | +--------------------… となる。 A現状態が、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年に数学的に証明されている。 文；枚方圏内