やさしい計算理論(ヤサシイ ケイサン リロン)

コンピュータにはどんな問題でも解けるのか。この問いに答えるには、そもそも「計算する」とは何かを機械のモデルとして定義しなければなりません。丸岡章氏による本書は、その計算理論への入門書で、サイエンス社の「 Information & Computing 」シリーズから 2017 年 12 月に刊行されました。副題の「有限オートマトンからチューリング機械まで」が、そのまま学びの道筋を示しています。

有限オートマトンという最も単純な計算モデルから出発し、モデルの能力を段階的に引き上げながら、万能の計算モデルであるチューリング機械へ到達する。この積み上げは計算理論という科目の定石ですが、状態遷移や形式言語の抽象的な議論は初学者が最初に苦しむ関門でもあります。「やさしい」と冠する本書は、その関門を読者の理解の速度に合わせて越えさせることを狙った編集で、数学的な厳密さを捨てずに敷居を下げる路線の教科書と位置づけられます。

正規表現がなぜ「正規」なのか、構文解析器の背後に何があるのか、決して停止しないプログラムを事前に検出できないのはなぜか。実務で出会うこれらの疑問は、すべて計算理論の言葉で初めて正確に語れます。情報系の学部生はもちろん、量子計算のような発展的な話題へ進む前に古典的な計算モデルの基礎を固めたい人にとっても、最初の一冊に選びやすい難易度です。読み終えたとき、「計算できる」という言葉の輪郭がはっきり変わっているはずです。