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

第Ⅱ部

計算と計算可能性

第Ⅰ部では、命令型プログラミング言語、状態機械、汎用コンピュータといった、皆さんになじみの

ある計算を扱ってきました。そして、計算というのは多かれ少なかれ、システムを使って情報を操作

することで質問に答えるプロセスだということを学びました。

第Ⅱ部では、もう少し冒険してみましょう。なじみのないところにある計算を探すことから始めて、

計算する機械にできることの根本的限界について調べていきます。

私たちプログラマは、世界のメンタルモデルに合わせて設計された言語と機械を使って、日々の仕

事をしています。私たちが言語と機械に求めているのは、アイデアから実装へと簡単に変換してくれ

る機能です。こうした人間中心の設計は、必要だからではなく便利だからというのが動機になっていま

す。チューリングマシンのような単純な設計でさえ、紙と鉛筆で仕事をしている数学者のことを思い出

させてくれます。

ところが、実際に計算が起こるのは、私たちにとってなじみのある、扱いやすい機械だけではありま

せん。人間にとって内部動作を制御したり理解するのが難しくても、同等の計算能力を備えたシステ

ムは他にもたくさんあります。６章では、便利な機能がほとんどない最小限の言語でプログラムを書い

てみることで、こうした考えについて調べます。続く７章では、さまざまな単純なシステムを見てい

き、それらがどうやって複雑な機械と同等の計算を実行するのか調べます。

完全な能力を持った計算が多種多様なシステムで可能なことを確かめたら、８章では、