計算の本質は何だろうか、計算できる関数はどのような構造をもっているか、原理的に計算できない関数があるというがそれは一体どんな関数だろうか、…これらの問題について最初に数学的にわかりやすく解説する。
また、プログラムの意味論や関数型言語と関連して注目を集めているラムダ計算の基礎理論を計算可能性の問題と関連させながら展開する。
従来、ラムダ計算に関する書物は少なく、しかもチャーチ･ロッサの定理や正規形定理などの基本定理の証明をきちんと与えているものは専門家向きのものに限られていたが、本書では簡潔で見通しのよい証明をこれらの基本定理に対して与える。
また、プログラムの数学的意味論にとって不可欠であるラムダ計算のモデルと、それに関するスコットらの理論を紹介する。