アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

第Ⅰ部

プログラムと機械

計算（computation）とは何でしょうか？ 人それぞれ違った意味で捉えていると思いますが、次の

ことには全員が同意できるはずです。「コンピュータがプログラムを読んで、そのプログラムを実行

し、何らかの入力を読んで、最終的に何らかの出力をするとき、間違いなく、ある種の計算が起こっ

ていると言える」ということです。これは出発点としては、まずまずでしょう。計算とはコンピュータ

がやることに付けた名前です。

このなじみのある計算を行うためには、次の3つの基本的な構成要素が必要です。

●

計算を実行することができる機械（machine）

●

機械が理解できる命令を書くための言語（language）

●

その言語で書かれた、機械が実行すべき計算を正確に記述したプログラム（program）

第Ⅰ部では、機械と言語とプログラムについて、それらが何であり、どのように振る舞うのか、どの

ようにモデル化できるのか、どのように利用すれば役に立つのか、ということについて説明します。こ

れら3 つの構成要素を詳しく調べることで、計算とは何か、それはどのように起こるのか、直感を養い

ます。

まず２章では、意味を記述するさまざまな方法を調べることで、おもちゃレベルのプログラミング言

語を設計、実装します。言語の意味を理解することは、命のないソースコードのかけらを持ってきて、

動的な実行するプロセスとして命を吹き込むということです。それぞれの仕様化テクニックは、私たち

にプログラムを実行するための具体的戦略