書評　計算機科学

• 計算理論の基礎１

計算理論の基礎 [原著第2版] 1.オートマトンと言語

情報理論周りはそこまで詳しくないですが、ボリューミーですが、わかりやすい本かと思います。計算理論は、計算機(コンピュータ)の動作原理を数学/数理論理学を用いて展開する分野です。
この本シリーズ一貫して、定理の後にいきなり証明に入るのではなく、証明の理由というかなぜそのような証明になるのか、証明のアイデアやポイントは何になるのか、に重きを置いており、この分野の初学者にも親切です。自分もすごく助かりました。
上記はその１巻で主にオートマトン、文脈自由言語の話になります。オートマトンは状態マシンの数学的モデルであり、計算機科学の基礎になります。決定性と非決定性の概念が出てきますが、これが計算理論と物理学とで、若干異なっているので注意が必要です。
文脈自由言語はプログラミング言語におけるコンパイルの数学的モデルで、新しいプログラミング言語を開発する際の必須知識になります。

• 計算理論の基礎２

計算理論の基礎の２巻です。2巻では計算可能性の理論がメインとなります。１巻で定義したオートマトンの知識を用いて、チューリングマシンという計算機の数学的モデルを定義していきます。
計算可能性の理論ですが、具体的にはチャーチ/チューリングのテーゼの話、チューリングマシンを使って、ある命題が計算可能かどうかの判定することは可能か、ある命題は既存の命題に帰結することができるか、等がメインとなります。このあたりの証明に際し、自然数全体と有理数全体の集合のサイズが等しい証明に使われる対角線論法を用いたりして興味深いです。

• 計算理論の基礎３

3巻では計算複雑性の話になります。２巻では計算可能かどうかの判定問題を扱いましたが、3巻では計算可能な問題をもう少し掘り下げ、計算時間の観点もしくは計算メモリの観点によって分類することを行います。いわゆる\(\mathrm{N\neq NP}\)予想で有名な、クラスPやクラスNPを定義していきます。クラスNPを「多項式で解けない問題」と勘違いしている方を見かけますが、これは間違いで正しくは「非決定性チューリングマシンで多項式時間でとける問題」となります。つまりNon-Polynomialではなく、Non-deterministic Polynomial となります。
計算時間によって分類したクラスN、NPと計算メモリの観点で分類した集合との間にどのような包含関係があるかを示す階層性の問題についても触れています。

正直私は証明の隅々まで理解したとはとてもいえないです、、しかしこの本で証明されている定理や考え方は、システム開発する上でも有用であることに気づけたので、それでも十分価値があったと思っています。