情報理論の基礎である計算可能性を、プログラム言語やチューリング機械などさまざまな観点から解説した入門書。練習問題も豊富で、徹底的に基礎理論のみを追求した本書は情報科学系初年級の教科書に最適である。