2 コンピューターのモデル

この辺の話は、「Interface 2002年9月号」と「ファインマン　計算機科学」、 「数学セミナー　2003年12月号」を参考にしています。

2.1 コンピューターの動作

コンピューターの基本的な動作は、非常に簡単です。1人の学生に登場しても らって、CPUとメモリーの役割を担ってもらいます。メモリは、私が用意した 小さな箱です。それに格納されている命令に従って、計算をしてもらいます。 簡単な計算

• まずは、$2\times3$の計算

を行ってもらいます。

このプログラムは、

00番地

08番地のデータをCPUの記憶領域1に格納する。

01番地

CPUの記憶領域2の値を1にする。

02番地

記憶領域1の値と08番地の値を加算して、記憶領域1に格納す る。

03番地

記憶領域2の値を1増加させる。

04番地

記憶領域2から09番地の値を引き算する。結果が0ならば、CPU の記憶領域aの値を1にする。

05番地

記憶領域aの値が1以外ならば、3番地の命令を実行する。

06番地

記憶領域1の値を10番地に格納する。

07番地

おわり。

08番地

2が格納されている。

09番地

3が格納されている。

10番地

計算につかう記憶領域。

となっています。実際ののコンピューターの動作は、これをとてつもない速度 で実行します。パソコンの3GHzのCPUでは、すうクロックで1つの命令を実行す ると、約1秒間に億のオーダーの命令を実行します。またメモリーは、 500Mbyteで、約5億個の記憶領域が用意されています。コンピューターは単純 な動作しかしませんが、非常に高速で、大量のデータを処理します。これによ り複雑なことを行っているように見えます。

このコンピューターのモデルで理解して欲しいことは、

• プログラムのデータもメモリ上に格納される。
• 命令に従い、データを書き換えている。

です。

2.2 チューリング機械

先に生徒諸君にコンピューターの動作を行ってもらったように、コンピューター というものは「メモリ中のデータとコンピューターの内部状態に従い、メモリー のデータを逐次的に書き換える計算機」と定義できます。こういうものを世界 で最初に提案したのは、当時、ケンブリッジ大学の大学院生であったアラン・ チューリングということらしい。1930年代の半ばのことです。

現在、コンピューターの理論的モデルと言われるのが、図 2に示すチューリング機械です。その特徴は、次の 通りです。

• 書き換え可能な無限に長いテープと、オートマトンと言われる移動可 能な機械からできている。
• テープには、いろいろな記号が書かれている。
• オートマトンには、テープの内容を読み書き可能なヘッドと内部状態 を記憶する装置、テープの任意の位置に移動する装置から構成されてい る。
• オートマトンの動作(テープの読み書き)や移動は、今の場所のテープ の記号と内部状態により決まる。

図 2: チューリング機械

これが、コンピューターそのものです。今は、分からなくても、そのうち理解 できるでしょう。書き換え可能なテープはメモリーに、オートマトンはCPUに 相当します。テープに書かれた記号は、プログラムであったりデータであった りします。内部状態はレジスタ³の 値に対応します。

あるときチューリング機械が、図1の状態であったとします。テープの内容を 読むあるいは書き直す、内部状態を変える、移動することのどれかが次の動作 になります。次の動作を決めるのは、テープの内容と内部状態により一意に決 まります。要するに、テープの上を行ったり来たりして、内部状態を変えたり、 テープの内容を読み書きしている自動機械がチューリング機械です。

このような動作をするチューリング機械で、どんなことができるのしょうか?。 このような単純な機械で、ありとあらゆる計算ができるのです。今まで、学習 してきた計算は、記号の操作の繰り返しになっています。人間の脳で計算する ときも、計算と言えば記号の操作の繰り返しのはずです。要するに、チューリ ング機械ではこの種の計算が、可能なわけです。ただ、チューリング機械で計 算できないものもあります。この問題は、込み入って複雑なので、ここでは取 り扱いません。

チューリング機械の概要が分かったと思います。要するに言いたいことは、計 算するという動作は、チューリング機械で表現できると言うことです。計算す るという一見、知的な作業が、おもちゃのようなチューリング機械で表せこと は驚きです。

2.3 ノイマン型コンピューター

ここで、少しコンピューターの発明されたころの話をします。1940年頃、ベル研 にコンプレックスカリキュレータというものがあり、それはプログラムは人間 が手で入れるもので、電卓と同じようなんものです。つまり、プログラム は、それを操作する人の頭にあり、人の手がインターフェースです。これでは、 とても高速にプログラムが実行できるとはいえません。

次の進歩は、プログラムが自動で計算機に送り込まれ、それに従い実行される 機械の発明でです。ドイツのZ3とハーバード大学のマークIである。これらの 機械は、計算はリレーで行われました。プログラムは、Z3の場合はフィルムに、 マークIの場合は紙テープに書かれていました。プログラムの実行速度は、フィ ルムや紙テープの読み取り速度で制限されます。これは、高速に計算する上で 非常に大きな問題でした。

1946年、砲弾の弾道計算用にENIACと名づけられた真空管式の電子計算機が開 発されました。当時としては、とてつもない速度で計算することができる機械 でしたが、大きな問題がありました。計算の内容、現在でいうプログラムを変 えるとき、それはプログラムボード呼ばれる配線板上の配線を組み替える必要 がありました。この作業は大変で、1日程度の時間が必要であったようである。 当然、次のコンピューターを作るとき、この点の改良が議論されたのは言うま でも無い。プログラムの変更が大変ですが、先の紙テープのように外部からプ ログラムを送るのではなく、本体に内蔵していた点では大きな進歩です。これ により、高速に計算ができたわけです。

次のEDVACというコンピューターの開発では、プログラムを配線ではなく、メ モリーの中に入れることが議論されました。こうすることにより、プログラム の変更が容易でかつ高速で計算するコンピューターが出来上がります。この開 発の中に、天才数学者ノイマンがおり、以降、このようにプログラムを内蔵し たものをノイマン式コンピューターと言われるようになりました。ただし、こ のアイディアを出したのがノイマンかと言われると、定かではありません。こ のコンピューターを実現するためのメモリーの開発は大変だったようです。

紆余曲折の後、プログラムと計算処理の対象であるデータは、同じメモリー上 に置かれるようになりました。このように、同じメモリー上に命令とデータが あるようなものをノイマン型コンピューターと言います。世界中のほとんどの コンピューターがこのノイマン型のコンピューターで、

• 1次元的に並んだメモリーがあり、そこにプログラム(命令)もデータも 格納される。メモリーの内容は、自然数の番地で参照できる。
• メモリーに格納されたプログラム(命令)とデータの見かけ上の区別は ない。プログラムをデータとして見ることも、データをプログラムとし てみることもできる。

の特徴をもっています。チューリング機械そのものです。

ホームページ: Yamamoto's laboratory
著者: 山本昌志