週刊スモールトーク　（第７３話）　チューリングマシンの原理

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

■異形のテクノロジー 　東京ドームの屋根はあんなに広いのに、柱が１本もない。一体、どうやって支えているのだ？答は空気圧。ドームの中に空気を送り込み、内側の気圧を外側よりも高くして、屋根を押し上げているのである。アーキテクチャ（基本構造）の根本が違うわけで、まさに、異形のテクノロジーだ。 　飛行船が浮く原理は風船と同じ。密封された袋の中に、空気より軽い水素やヘリウムつめ、浮力をえる。プロペラを回せば、水平移動もできる。この飛行原理は220年間変わることがなかった。ところが、20年前、飛行原理が全く異なる球体飛行船が登場した。球体を回転させながら、水平移動すると、球体の下部の圧力が上部の圧力より高くなり、浮きあがるのである（マグヌス効果）。原理は古いが、これで飛行船を飛ばすという発想が凄いのだ。ということで、こちらも異形のテクノロジー。 　発明には、改良・改善を突き抜けて、発想からして違う革新的なテクノロジーが存在する。東京ドームや球体飛行船もその一つだろう。そして、コンピュータの世界にも、こんな”異形”が存在する。 ■2つのコンピュータ 　デジタル コンピュータには2つのタイプがある。1つはノイマン型コンピュータ。ハンガリーの数学者フォン ノイマンが提唱したもので、ノイマンマシンとも呼ばれている。現在、地球上で稼働しているコンピュータのほとんどがこれ。もう1つは、イギリスの数学者アラン チューリングが提唱したチューリングマシン。こちらは、概念の域を出ず、実用化はされていない（と思う）。 　ではなぜ、チューリングマシンは実用化されなかったのか？おそらく、プログラミングの問題。コンピュータに仕事をさせるには、ソフトウェアが必要だ。文字を書くならワード、表計算ならエクセル、メールならメーラーという風に。このソフトウェアを作ることをプログラミングというが、その容易さで、ノイマンマシンはチューリングマシンを圧倒する。ノイマンマシンは、チューリングマシンより、ソフトの開発費が少なくてすむわけだ。資本主義の適者生存のルールが適用されたのだろう。 　しかし ・・・ 　チューリングマシンは、おそろしく異形に見える。ノイマンマシンに慣れたせいかもしれいないが、それだけではなさそうだ。とにかく、発想が尋常ではないのだ。どうして、こんなことが思いつくのか？天才とはこのようなものなのか？と考え込んでしまう。ということで、異形のコンピュータ「チューリング マシン（Turing Machine）」を丸かじりしてみよう。感動すること、うけあいである。 ■チューリング マシンの原理 　チューリング マシンは左図のように、データを記憶するメモリセルが連続したテープと、その上を移動するヘッドからなる。ビデオテープをイメージすると分かりやすい。 　ヘッドは図のように、2方向に移動するが、1回で移動できるのは1メモリセルのみ。さらに、ヘッドは真下のメモリセルの値を読んだり、値を更新する（書く）ことができる。ただし、メモリセルに許された値は、「0」か「1」、つまり１ビット。これに加え、チューリング マシンのstate（内部状態）を保持する内部レジスタを１つ持っている。これが、チューリング マシンのすべてである。 　こんな単純な仕掛けでコンピュータが実現できる？もし、チューリングマシンが、ノイマンマシンに取ってかわっていたら、CPUはさぞかし、つましいものになっていただろう。チップの部品数ははるかに少なく、当然、発熱の問題も起こらない。もちろん、インテルの隆盛も怪しい。 　さて、いよいよ、チューリングマシンのプログラミング。チューリングマシンの命令は、下記の5つのパラメータで構成される。 �@現在のstate（内部状態） �A現在のメモリセルの値 �B新しいメモリセルの値 �C新しいstate（内部状態） �Dヘッドの移動 以下、パラメータを詳しく説明する。 　「�@現在のstate」と「�A現在のメモリセルの値」は、この命令が選択・実行される条件である（入力）。また、「�B新しいメモリセルの値」と「�C新しいstate」と「�Dヘッド移動」は、この命令の実行内容である（出力）。下記の表にパラメータの詳細を記す。 パラメータ名 パラメータの説明 �@現在のstate マシンの内部状態を表す （0、1、2、3・・・） �A現在のメモリセルの値 ヘッドの真下のメモリセルの現在の値（「1」 または 「0」） �B新しいメモリセルの値 ヘッドの真下のメモリセルに新しく書き込む値（「1」 または 「0」） �C新しいstate 新しいマシンの内部状態 （0、1、2、3・・・） �Dヘッド移動 ヘッドの移動する方向 （「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」で、ヘッドの真下のメモリセルの値を読む。その値「�A現在のメモリセルの値」と「�@現在のstate」が一致する命令を、命令リストから捜す。そこで、一致する命令がなければ、実行停止。あれば、その命令に従い、下記の表のstep3〜5を実行する。これを繰り返すわけだ。ここで、具体的なプログラムを書いてみよう。 処理の流れ step 1 ヘッドの真下のメモリセルの値を読む step 2 「�@現在のstate」と「�A現在のメモリセルの値」に一致する命令を捜し、なかったら実行停止 step 3 命令で指示された 「�B新しいメモリセルの値」 をヘッドの真下のメモリセルに書き込む step 4 命令で指示された 「�C新しいstate」 にstateを更新する step 5 命令に指示された 「�Dヘッド移動」に従い、ヘッドを移動する 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」にして、ヘッドを右に移動する。 　１番目の命令はビット反転「0 → 1」、2番目の命令はビット反転「1 → 0」をもくろんでいる。この2つの命令があれば、ビット列 「0010」の各ビットを反転できるはずだ。さっそく、チューリングマシンを実行してみよう。下記の表に、実行の様子を１ステップずつ示す。●はヘッドの位置を示している。この表を順番に追っていけば、チューリングマシンの基本原理が理解できる。 命令 メモリセル 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」に変更して右に移動し、同じ処理を繰り返す。 �Aもし、メモリセルの値が「１」なら、「0」に変更して終了する。 　ノイマンマシンの方が断然分かりやすい。とはいえ、チューリングマシンの発想のユニークさ、凄さも分かっていただけたと思う。チューリングマシンは構造がシンプルなのでエミュレータも簡単に作れる。エミュレータがあれば、パソコンでチューリングマシンのプログラミングが楽しめる。サンデープログラマの道楽にはうってつけだ。 　チューリングマシンが処理できるのは、ビット列操作だけではない。「計算可能な問題（アルゴリズムが存在する）」ならどんな計算も可能だ。ただし、先の例題ではstateが2つ（0と1）だったが、問題が複雑なら、stateの数を増やす必要がある。それでも、ほとんどの問題は100を超えることはないという。 　しかし、チューリングマシンで、stateが100はというのはつらい。考えただけで、頭が痛くなる。というわけで、プログラミングの容易さを考えれば、ノイマンマシンに軍配が上がる。もっとも、ノイマンマシンとチューリングマシンの優劣を決めるのは不毛だろう。チューリングマシンは、あくまで「計算する脳」のモデルであって、概念が”凄い”のだから。そして、「コンピュータ サイエンス」が似合うのも、チューリングマシン。だから、コンピュータサイエンスのノーベル賞は「チューリング賞」なのである。 by Ｒ．Ｂ