■異形のテクノロジー■
建物の天井を支えるには、支柱が必要だ。天井が落ちては、シャレにならない。ところが、東京ドームにはあの広い屋根をささえるための支柱がない。屋根を支えているのは、柱ではなく、空気圧なのだ。ドーム内に、常時、空気を送り込み、内側の気圧を外よりも高くして、屋根を押し上げているのである。柱の材質や構造に工夫を凝らしていた建築設計者にとって、このような構造は異形のテクノロジーに見えただろう。
飛行船のように、原理が決まり切ったものにも、異形のテクノロジーは存在する。一般に、飛行船は風船と同じ原理で浮揚する。完全密封された袋の中に、水素やヘリウムなど空気より軽い気体をつめ、浮力をえるのである。水平方向には、航空機同様、プロペラを回転させ移動する。飛行船の飛行原理は220年間変わることはなかった。
ところが、20年前、異形の球体飛行船が出現した。この飛行船は、巨大な球体を回転させ、同時に、水平方向に移動させることにより、球体の下部の圧力を高くし、浮き上がるのである。この浮揚原理は、ベルヌーイの法則で説明されるが、従来の飛行船とは原理が異なる。この原理を用いれば、前後、左右、上下と、UFOのごとく自由自在に飛行できるはずだった。そのため、当時は、100年先をいく未来技術とまで絶賛された。ところが、現在、地球上のどの空にも球体飛行船を見つけることはできない。何があったのかは分からないが、開発が頓挫したことは確かだ。そして、コンピュータの世界でも、異形のテクノロジーは存在する。
■2つのコンピュータ■
デジタル コンピュータには、大きく２つのタイプが存在する。1つは、ノイマン型コンピュータ。ハンガリーの天才数学者フォン ノイマンが提唱したもので、ノイマン マシンとも呼ばれている。現在、地球上で稼働しているコンピュータのほとんどがこれである。
もう1つは、チューリング マシン。イギリスの数学者アラン チューリングが提唱したものだが、技術者でも知らない人が多い。実用レベルで稼働しているものは、たぶん皆無であり、学校で教えているという話も聞かない。つまり、歴史的に見て、チューリング マシンはすでに淘汰されている。
その一番の理由は、たぶん、プログラミングにある。コンピュータに仕事をさせようと、日本語でわめいてみたところで、何も起こらない（2006年11月現在）。コンピュータが理解できる言葉で、指示する必要があるのだ。コンピュータにさせたい仕事を、コンピュータの言葉で置き換える作業をプログラミングといい、その産物をプログラムと呼んでいる。このプログラミングの容易さにおいて、ノイマン マシンは、チューリング マシンを圧倒している。ソフトウェア業界は、一見ハイテクに見えるが、実は典型的な労働集約型産業だ。つまり、最も高くつく人件費に直撃されている。当然、プログラミングが容易な方が生き残る。資本主義の適者生存のルールが、ノイマン マシンを選択し、チューリング マシンを歴史から消し去ったのである。
とはいうものの、ノイマン マシンにどっぷり浸かったコンピュータ技術者が、チューリング マシンのプログラミングを体験してみるのも悪くはない。天才の発想というものを、垣間見ることができるからだ。われわれは、分かりやすく洗練されたノイマン マシンしか知らないが、これに比べると、チューリング マシンは異形だ。そう、驚くほど、異形である。
こんなことを言うと、高見に立った学者から「２つのマシンが違って見えるのは、本質を理解していないからであり、この２つは同じものである」と非難されそうだ。だが、現場のプログラマーは、このようなアーキテクチュア（設計思想）の違いに、好奇心をそそられるのである。ということで、異形のコンピュータ チューリング マシン（Turing Machine）を、丸かじりしてみよう。新鮮に感じること、うけあいである。
■チューリング マシンの原理■
 チューリング マシンは左図のように、データを記憶するメモリセルが連続したテープと、その上を移動するヘッドからなる。ビデオテープをイメージすると分かりやすい。ヘッドは図のように、2方向に移動できるが、1回に移動できるのは1メモリセルのみ。
ヘッドは、真下にあるメモリセルにデータを読み書きできる。ただし、メモリセルに許された値は、「0」か「1」、つまり１ビットだ。これに加え、チューリング マシンのstate（内部状態）を保持する内部レジスタを１つもっている。これが、チューリング マシンのすべてだ。
こんな単純な構造でコンピュータが実現できる？もしチューリング マシンが、ノイマン マシンに取ってかわっていたら、CPUはさぞかし、つつましいものになっていただろう。チップの部品数ははるかに少なく、当然、発熱の問題も起こらない。むろん、現在のインテルの隆盛も怪しい。
余談はさておき、次に、チューリング マシンのプログラミング。チューリング マシンの命令は、下記の５つのパラメータから構成される。
①現在のstate
②現在のメモリセルの値
③新しいメモリセルの値
④新しいstate
⑤ヘッドの移動
以下、各パラメータを詳しく説明する。
上記の命令の「①現在のstate」と「②現在のメモリセルの値」は、この命令が選択され、実行されるための入力条件となる。
また、「③新しいメモリセルの値」と「④新しいstate」と「⑤ヘッド移動」は、この命令の実行内容である。
抽象的な説明で分かりにくいが、以下の具体的プログラミングの後に、読み返していただくと、分かりやすいかもしれない。
下記の表は、命令のパラメータの詳細である。
パラメータ名 |
パラメータの説明 |
| ①現在のstate |
マシンの内部状態を表す （0、1、2、3・・・） |
| ②現在のメモリセルの値 |
ヘッドの真下にあるメモリセルの現在の値（「1」 または 「0」）
「1」 → 「T」で表すことにする
「0」 → 「Ｆ」で表すことにする |
| ③新しいメモリセルの値 |
ヘッドの真下にあるメモリセルに新しく書き込む値（「1」 または 「0」）
「1」 → 「T」で表すことにする
「0」 → 「Ｆ」で表すことにする |
| ④新しいstate |
新しいマシンの内部状態 （0、1、2、3・・・） |
| ⑤ヘッド移動 |
ヘッドの移動する方向 （「R」：右に移動、「L」：左に移動） |
例えば【0 T F 1 R】という命令は、
0：現在のstateが「0」
T：メモリセルの値が「1」 （「1」は「T」で表す ：Trueの意味）
の時に選択実行される命令で、その実行内容は
F：メモリセルに「0」を書き込んで （「0」は「F」で表す ：Falseの意味）
1：stateを「1」に更新し
R：ヘッドを右に移動する
となる。つまり、最初のパラメータ２つが、この命令が実行される条件を、その後の３つのパラメータは、実行される内容を示す。単純だが、これがチューリング マシンの核心である。
次に、チューリング マシンの処理の流れを下の表に示す。チューリング マシンは下記の表の「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」に遭遇したら、それを反転させた後、処理を停止する。
この問題を解決するために必要なプログラム命令は、たったの２つである。それを、下記の表に示す。
命令 |
命令の説明 |
0 F T 0 R |
stateが「0」で、メモリセルの値が「F（0）」なら、メモリセルに「T(1）」を書いて、stateを「0」にして、ヘッドを右に移動する。 |
0 T F 1 R |
stateが「0」で、メモリセルの値が「T(1）」なら、メモリセルに「F(0）」を書いて、stateを「1」にして、ヘッドを右に移動する。 |
１番目の命令は、『ビットの値が「0」なら、「1」に変更する』、２番目の命令は『ビットの値が「1」なら、「0」に変更する』をもくろんでいる。この2つの命令があれば、ビット列 「0010」の各ビットを反転できるはずだ。さっそく、チューリングマシンを実行してみよう。分かりやすくするために、下記の表に、実行の様子を１ステップずつ示す。●はヘッドの位置を示している。この表を順番に追っていけば、チューリングマシンの原理がすべて理解できる。
命令 |
メモリセル |
state |
動作説明 |
start |
● |
|
|
|
|
ビット列 「0010」が、メモリセルに書かれている。ヘッドの位置はビット列の最上位にある。stateは「0」からスタート。 |
0 |
0 |
1 |
0 |
0 |
0 F T 0 R |
|
● |
|
|
|
stateが「0」で、メモリセルの値が「F(0）」なので、メモリセルを「T(1）」に書き込み、stateは「0」のままで、ヘッドを右に移動する。 |
1 |
0 |
1 |
0 |
0 |
0 F T 0 R |
|
|
● |
|
|
同上 |
1 |
1 |
1 |
0 |
0 |
0 T F 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」に反転していないのは、『「1」を反転させた時点で処理を停止する』という約束に従っている。上記の処理のように、【 現在のstate｜現在のメモリセルの値｜…】に一致する命令がないと、そこで処理がhalt（停止）する。逆に、すべての命令を記述しておけば、永遠に処理を続けることになる。そのため、メモリセルが連なるテープは無限の長さをもつことが前提となる。
むろん、チューリング マシンを実装する際には、メモリーは有限なので、halt（停止）の仕組みが必要だ。さもないと、存在しないメモリまでアクセスしようとし、厄介なことになる。つまり、フリーズする。
■チューリング マシンの意義■
単純なビット列の反転処理でも、こんな面白いコンピュータが存在するのだ。よくまあ、こんなアーキテクチャが思いつくものだと、感心する。ノイマン マシンにどっぷり浸かったプログラマーにとって、目から鱗（うろこ）である。構造がシンプルなので、パソコン上で、チューリング マシンのエミュレータも簡単に作れるだろう。エミュレータさえあれば、チューリング マシンのプログラミングが楽しめる。パソコンオタクや、サンデープログラマーの道楽にはうってつけだ。
むろん、チューリング マシンが処理可能なのは、ビット列操作だけではない。『計算可能な問題』であれば、どんな複雑な算術演算も記号処理も計算可能だ。これは、アラン チューリングがすでに証明している。ここで、『計算可能な問題』とは、問題を計算（解決）する手順が、先の《例題》のように命令で記述できる問題を意味している。つまり、アルゴリズムが存在するものなら、なんでも計算できる。
また、チューリング マシンで、より複雑な問題を計算するためには、先に述べたstate の数を増やせばいいことは容易に想像がつく。それでも、たいていの問題は、100ほどのstateで実現できるという。だが、このような構造のコンピュータで、stateが100というのは、頭が痛くなる。お城の中に部屋が10あって、その部屋1つ1つに絵が飾ってあって、それぞれの絵にはお城があって、そのお城には部屋が10あって…などという情景を一瞬にして思い描けるような人でない限り、チューリング マシンのプログラミングは難しいもしれない。
むろん、これは機械語レベルでの話だ。ノイマン マシンにしろ、チューリング マシンにしろ、高級言語をかぶせてしまえば、プログラミングの難しさは変わらない。そうなると逆に、２つのマシンの構造上の違いは見えなくなる。優劣を決めるのは、処理速度とコストパーフォーマンスのみ。そして、この点において、チューリング マシンの優位はかなり疑わしい。
とはいえ、このような議論そのものが間違っているのかもしれない。チューリング マシンは、あくまで『計算する脳』の基本モデルであって、その概念とそのアーキテクチャ（構造）にこそ価値がある。実装上の問題で、騒ぎ立てるのは筋違いかもしれない。コンピュータはサイエンスか否か、という議論もあるが、チューリングの遺産は、間違いなくサイエンスと言えるだろう。そして、『コンピュータ サイエンス』の言葉がもっとも似合うのも、アラン チューリング。だからこそ、情報工学のノーベル賞は『チューリング賞』なのである。
by Ｒ．Ｂ |
