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

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

3.1 コンピューターの動作

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

まずは， $2\times3$ の計算

を行い，コンピューターの動作の基本を理解してもらう．

この計算を行うこのプログラムは，次のとおりである．

00番地: 08番地のデータをCPUの記憶領域aに格納する．
01番地: CPUの記憶領域bの値を1にする．
02番地: 記憶領域bから09番地の値を引き算する．結果が0ならば，06番地の命令を実行する．
03番地: 記憶領域aの値と08番地の値を加算して，記憶領域aに格納する．
04番地: 記憶領域bの値を1増加させる．
05番地: 02番地の命令を実行する．
06番地: 記憶領域aの値を10番地に格納する．
07番地: おわり．
08番地: 2が格納されている．
09番地: 3が格納されている．
10番地: 計算につかう記憶領域．

気が付いたと思うが，足し算を繰り返すことにより，掛け算をの演算を実行しているのである．普通のCPUは乗算ができないのである．

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

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

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

である．

3.2 チューリング機械

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

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

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

**図 3:** チューリング機械
$\includegraphics[keepaspectratio, scale=1.0]{figure/Turing_machine.eps}$

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

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

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

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

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

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

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

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

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

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

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

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

プログラムとデータを別のメモリーに置く、コンピューター(CPU)もある．このような方式をハーバードアーキテクチャーと言う．

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

Yamamoto Masashi
平成19年6月24日