BeneDict 地球歴史館

BeneDict 地球歴史館
menu

週刊スモールトーク (第73話) チューリングマシンの原理

カテゴリ : 科学

2006.11.19

チューリングマシンの原理

■異形のテクノロジー

東京ドームの屋根はあんなに広いのに、柱が1本もない。一体、どうやって支えているのだ?答は空気圧。ドームの中に空気を送り込み、内側の気圧を外側よりも高くして、屋根を押し上げているのである。アーキテクチャ(基本構造)の根本が違うわけで、まさに、異形のテクノロジーだ。

飛行船が浮く原理は風船と同じ。密封された袋の中に、空気より軽い水素やヘリウムつめ、浮力をえる。プロペラを回せば、水平移動もできる。この飛行原理は220年間変わることがなかった。ところが、20年前、飛行原理が全く異なる球体飛行船が登場した。球体を回転させながら、水平移動すると、球体の下部の圧力が上部の圧力より高くなり、浮きあがるのである(マグヌス効果)。原理は古いが、これで飛行船を飛ばすという発想が凄いのだ。ということで、こちらも異形のテクノロジー。

発明には、改良・改善を突き抜けて、発想からして違う革新的なテクノロジーが存在する。東京ドームや球体飛行船もその一つだろう。そして、コンピュータの世界にも、こんな”異形”が存在する。

■2つのコンピュータ

デジタル コンピュータには2つのタイプがある。1つはノイマン型コンピュータ。ハンガリーの数学者フォン ノイマンが提唱したもので、ノイマンマシンとも呼ばれている。現在、地球上で稼働しているコンピュータのほとんどがこれ。もう1つは、イギリスの数学者アラン チューリングが提唱したチューリングマシン。こちらは、概念の域を出ず、実用化はされていない(と思う)。

ではなぜ、チューリングマシンは実用化されなかったのか?おそらく、プログラミングの問題。コンピュータに仕事をさせるには、ソフトウェアが必要だ。文字を書くならワード、表計算ならエクセル、メールならメーラーという風に。このソフトウェアを作ることをプログラミングというが、その容易さで、ノイマンマシンはチューリングマシンを圧倒する。ノイマンマシンは、チューリングマシンより、ソフトの開発費が少なくてすむわけだ。資本主義の適者生存のルールが適用されたのだろう。

しかし ・・・

チューリングマシンは、おそろしく異形に見える。ノイマンマシンに慣れたせいかもしれいないが、それだけではなさそうだ。とにかく、発想が尋常ではないのだ。どうして、こんなことが思いつくのか?天才とはこのようなものなのか?と考え込んでしまう。ということで、異形のコンピュータ「チューリング マシン(Turing Machine)」を丸かじりしてみよう。感動すること、うけあいである。

■チューリング マシンの原理

TuringMachine チューリング マシンは図のように、データを記憶するメモリセルが連続したテープと、その上を移動するヘッドからなる。ビデオテープをイメージすると分かりやすい。

ヘッドは図のように、2方向に移動するが、1回で移動できるのは1メモリセルのみ。さらに、ヘッドは真下のメモリセルの値を読んだり、値を更新する(書く)ことができる。ただし、メモリセルに許された値は、「0」か「1」、つまり1ビット。これに加え、チューリング マシンのstate(内部状態)を保持する内部レジスタを1つ持っている。これが、チューリング マシンのすべてである。

こんな単純な仕掛けでコンピュータが実現できる?もし、チューリングマシンが、ノイマンマシンに取ってかわっていたら、CPUはさぞかし、つましいものになっていただろう。チップの部品数ははるかに少なく、当然、発熱の問題も起こらない。もちろん、インテルの隆盛も怪しい。

さて、いよいよ、チューリングマシンのプログラミング。チューリングマシンの命令は、下記の5つのパラメータで構成される。
①現在のstate(内部状態)
②現在のメモリセルの値
③新しいメモリセルの値
④新しいstate(内部状態)
⑤ヘッドの移動
以下、パラメータを詳しく説明する。

「①現在のstate」と「②現在のメモリセルの値」は、この命令が選択・実行される条件である(入力)。また、「③新しいメモリセルの値」と「④新しいstate」と「⑤ヘッド移動」は、この命令の実行内容である(出力)。下記の表にパラメータの詳細を記す。

パラメータ名
パラメータの説明
①現在のstate マシンの内部状態を表す (0、1、2、3・・・)
②現在のメモリセルの値 ヘッドの真下のメモリセルの現在の値(「1」 または 「0」)
③新しいメモリセルの値 ヘッドの真下のメモリセルに新しく書き込む値(「1」 または 「0」)
④新しいstate 新しいマシンの内部状態 (0、1、2、3・・・)
⑤ヘッド移動 ヘッドの移動する方向 (「R」:右に移動、「L」:左に移動)

例えば【0 1 0 1 R】という命令は、

0:現在のstateが「0」
1:メモリセルの値が「1」

の時に選択・実行される命令で、その実行内容は

0:メモリセルに「0」を書き込んで
1:stateを「1」に更新し
R:ヘッドを右に移動する

となる。つまり、最初のパラメータ2つがこの命令が選択・実行される条件を、その後の3つのパラメータは、実行内容を表す。

次に、チューリングマシンの処理の流れを下表に示す。チューリングマシンは下記の表の「step 1」から「step 6」までを繰り返す。

「step1」で、ヘッドの真下のメモリセルの値を読む。その値「②現在のメモリセルの値」と「①現在のstate」が一致する命令を、命令リストから捜す。そこで、一致する命令がなければ、実行停止。あれば、その命令に従い、下記の表のstep3~5を実行する。これを繰り返すわけだ。ここで、具体的なプログラムを書いてみよう。

処理の流れ
step 1 ヘッドの真下のメモリセルの値を読む
step 2 「①現在のstate」と「②現在のメモリセルの値」に一致する命令を捜し、なかったら実行停止
step 3 命令で指示された 「③新しいメモリセルの値」 をヘッドの真下のメモリセルに書き込む
step 4 命令で指示された 「④新しいstate」 にstateを更新する
step 5 命令に指示された 「⑤ヘッド移動」に従い、ヘッドを移動する
step 6 step 1 に戻る
■チューリング マシンでプログラミング

《例題》 ビット列 「0010」の各ビットを左端から順番に反転し、「1」に遭遇したら、それを反転した後、処理を停止する。

この問題を解決するために必要な命令は以下の2つ。

命令
命令の説明
0 0 1 0 R
stateが「0」で、メモリセルの値が「0」なら、メモリセルに「1」を書いて、stateを「0」にして、ヘッドを右に移動する。
0 1 0 1 R
stateが「0」で、メモリセルの値が「1」なら、メモリセルに「0」を書いて、stateを「1」にして、ヘッドを右に移動する。

1番目の命令はビット反転「0 → 1」、2番目の命令はビット反転「1 → 0」をもくろんでいる。この2つの命令があれば、ビット列 「0010」の各ビットを反転できるはずだ。さっそく、チューリングマシンを実行してみよう。下記の表に、実行の様子を1ステップずつ示す。●はヘッドの位置を示している。この表を順番に追っていけば、チューリングマシンの基本原理が理解できる。

命令
メモリセル
state
動作説明
start
       
ビット列 「0010」が、メモリセルに書かれている。ヘッドの位置はビット列の最上位にある。stateは「0」からスタート。
0
0
1
0
0
0 0 1 0 R
 
     
stateが「0」で、メモリセルの値が「0」なので、メモリセルを「1」に書き換え、stateは「0」のままで、ヘッドを右に移動する。
1
0
1
0
0
0 0 1 0 R
   
   
同上
1
1
1
0
0
0 1 0 1 R
     
 
stateが「0」で、メモリセルの値が「1」なので、メモリセルを「0」に書き換え、stateを「1」に更新し、ヘッドを右に移動する。
1
1
0
0
1
halt
     
 
stateが「1」の命令が存在しないので、実行を停止する。
1
1
0
0
1

ビット列「0010」が、「1100」にビット反転したことがわかる。最後のビット「0」が反転していないのは、その一つ前の「1」を反転させた時点で処理を停止したからである。このように、【 現在のstate|現在のメモリセルの値|・・・】に一致する命令がないと、そこで処理を停止する(halt)。もし、すべての命令を記述しておけば、永遠に処理を続ける。その場合、ヘッドがテープの長さを超えて移動しないようにする必要がある。無限長のテープなどないのだから。

■チューリング マシンの意義

この例題を、ノイマンマシンでプログラムすると、
①もし、メモリセルの値が「0」なら、「1」に変更して右に移動し、同じ処理を繰り返す。
②もし、メモリセルの値が「1」なら、「0」に変更して終了する。

ノイマンマシンの方が断然分かりやすい。とはいえ、チューリングマシンの発想のユニークさ、凄さも分かっていただけたと思う。チューリングマシンは構造がシンプルなのでエミュレータも簡単に作れる。エミュレータがあれば、パソコンでチューリングマシンのプログラミングが楽しめる。サンデープログラマの道楽にはうってつけだ。

チューリングマシンが処理できるのは、ビット列操作だけではない。「計算可能な問題(アルゴリズムが存在する)」ならどんな計算も可能だ。ただし、先の例題ではstateが2つ(0と1)だったが、問題が複雑なら、stateの数を増やす必要がある。それでも、ほとんどの問題は100を超えることはないという。

しかし、チューリングマシンで、stateが100はというのはつらい。考えただけで、頭が痛くなる。というわけで、プログラミングの容易さを考えれば、ノイマンマシンに軍配が上がる。もっとも、ノイマンマシンとチューリングマシンの優劣を決めるのは不毛だろう。チューリングマシンは、あくまで「計算する脳」のモデルであって、概念が”凄い”のだから。そして、「コンピュータ サイエンス」が似合うのも、チューリングマシン。だから、コンピュータサイエンスのノーベル賞は「チューリング賞」なのである。

《完》

by R.B

関連情報