本書は 15 の章からなり，(学部や)大学院での半期の講義に適したものとなっ ている．冒頭で述べたように，計算理論は，理論と実用とが出会う場である． 今日，多くのソフトウェアパッケージは，互いに関連し合うおびただしい数の プログラムからなるが，それらが，なぜ，そして，どのように動作するかの 理解を深めることは重要である．

すべてを明解に，簡潔に，かつ，正確に表現するには， しっかりとした形式化が必要である．本書の執筆に当たっては，離散数学の 基礎的な知識を持つ読者を想定している．特に，数学的な主張を証明する ための手段に関する基礎的理解があることが望ましい． その他の必要な事柄については，本文中で説明を与えている．さらに，基本的な概念に ついては例示により説明している．形式的な正確さと直感的なアイディアを うまく両立させることによって，学生と指導者がともに，本書に示されている 多くの素晴らしい見識を享受できるものと確信している．

われわれが最も強調したいことは，情報学における理論と実用の相互作用である． 理論は実用上重要な問題を扱うべきであり，一方、実用に関する情報学は， 最大限の能力を発揮するための確固たる基礎を必要とする． したがって，本書の前半2/3は，形式言語とオートマトン理論にあてている． 形式言語は，様々な場面で出現するため，応用計算機科学にとって必要不可欠である． よって，本書では，文法(生成の形式化)，オートマトン(受理の形式化)，および 正規言語・文脈自由言語に対する文法とオートマトンの関連性を扱っている．

後半の1/3では，部分帰納的関数とチューリング機械を通して，アルゴリズム に対する直感的な理解の定式化を行う．これら二つのモデルの等価性を示し， 万能チューリング機械の存在，すなわち，すべての可能な計算を 実行できるただ一つの計算装置が存在することを証明する． その後，いかなる計算機をもってしてもまったく解くことのできない問題が存 在することを示す．さらに，停止問題，ポストの対応問題の議論を経て， この理論を適用することによって，このような形式言語理論における自然な 問いに対する，より完全な全体像を明らかにする．最後に，不動点定理， 再帰定理，およびライスによる有名な定理を示した後，(抽象的な)計算量クラスに ついて述べ，それらのいくつかの性質について学ぶ．

さらに本書は，チョムスキー-シュツェンベルガーの定理，部分帰納的 関数の解説，デデキントの正当化定理，抽象的計算量クラスとそれらの性質 といった，他書ではほとんど扱われない重要な事柄も含んでいる．

なお，本書には講義ですぐに使える15回分のスライド(日本語版・英語版)が 付属する．この教材は，北海道大学において実際に使われたものである． これらスライドおよび本書は，自ら興味のある章を学ぶことによって 自身の英語スキルを高めたい日本人学生や，日本の大学で計算機科学の勉強を 修めたい外国人留学生に向けたものである．

われわれのこれまでの経験から，計算理論のような高度に専門化された話題を扱う際には， 正確な専門用語を見つけることは，しばしば困難を伴う．こうした作業を容易にすべく， 本文中に用語の和訳を付けてある．重要な専門用語が導入される際には， イタリックで強調され，直後に適切な日本語訳を挿入している．

定義文(Definition)は全体がイタリック体で記述され，その中で定義される用語のみ ローマン体となっている．定義される用語にも日本語訳が付されている

また本書のような教科書は，もちろん参考書としても利用される． そこで，通常の索引，および， 日本語索引の二種類の索引を用意した．

書籍は，生身の教師のように，学生と話をしたり質問に答えたりすることは できない．そのような不便さをカバーするため，課題(problem)と演習(exercise) を付けることとした．課題と演習では難易度については大きな差はない． 唯一の違いは，課題には解答が付いている(添付CD-ROM)が，演習には解答が付いていない という点である．これらの課題と演習は，本文に加えてさらに多くの興味深い 事柄について光をあてるものであり，セミナーで利用したり，あるいは宿題として 課したりするとよい．なお，本書で示した解答は，唯一のものではないことにも注意して もらいたい．この点を強調するために，いくつかの問題に対しては別解を与えている．

最後になるが，本書に沿った学修は，おそらく相当に努力を要するものになると思われる． しかし，それはウィリアム・クラーク博士(北海道大学建学の父，札幌農学校初代教頭)の 激励に沿ったものである．