計算理論の基礎 [原著第 3 版] 2.計算可能性の理論(ケイサンリロンノキソゲンチョダイサンハンニケイサンカノウセイノリロン)

Michael Sipser 教授による “ Theory of Computation ” の講義は MIT 屈指の名講義で、教室には活気と笑いが絶えることはない。本書はその講義ノートをもとにまとめられた、この分野の標準的教科書である。
定理を述べたあと直ちに証明に取りかからず、証明のアイデアを与える工夫、証明の失敗例に言及して理解を深めさせるなど、随所に講義の雰囲気が感じられる、教育的配慮の行き届いた教科書になっている。
第 3 版では、「決定性文脈自由言語」に関する節が新たに加えられたほか (第 2 巻) 、問題や解答が追加されるとともに、いくつかの話題に関して、第 2 版刊行後の研究の進展について説明を加えた。
第 3 章 Church – Turing の提唱
3.1 Turing 機械
3.2 Turing 機械の変型
3.3 アルゴリズムの定義
第 4 章 判定可能性
4.1 判定可能な言語
4.2 判定不可能性

第 5 章 帰着可能性
5.1 言語理論における判定不可能問題
5.2 単純な判定不可能問題
5.3 写像帰着可能性

第 6 章 計算可能性の理論における先進的な話題
6.1 再帰定理
6.2 数理論理における判定可能性
6.3 Turing 帰着可能性
6.4 情報の定義

「コンピュータには原理的に解けない問題がある」という事実を、雰囲気ではなく証明で理解するための巻です。 Michael Sipser 教授の定番教科書 "Theory of Computation" 邦訳の第 2 巻にあたり、共立出版から 2023 年に原著第 3 版として刊行されました。翻訳は田中圭介氏、藤岡淳氏、阿部正幸氏らによるものです。第 1 巻がオートマトンと形式言語という制限された計算モデルを扱ったのに対し、本巻では Turing 機械を導入し、計算そのものの能力と限界に踏み込みます。

章立ては、 Turing 機械とその変型からアルゴリズムの定義に至る Church-Turing の提唱、判定可能な言語と判定不可能性、写像帰着による判定不可能問題の間の関係づけ、そして再帰定理や数理論理における判定可能性、 Turing 帰着可能性といった先進的な話題まで。停止問題に代表される「解けない問題」を確定させたうえで、帰着というテクニックで判定不可能性が問題から問題へ伝播していく様子を追う構成は、計算可能性理論の考え方の核心をそのまま体験させてくれます。定理の前に証明のアイデアを示す Sipser 流の教育的な書き方は本巻でも一貫しています。

読む前提として、第 1 巻で扱うオートマトンと言語の基礎、および証明を読み書きする体力は必要です。学部後半から大学院初年級の理論系講義に対応する水準で、停止問題や決定不能性といった言葉を見かけるたびに素通りしてきたエンジニアが、その正体を一度根元から確かめる読書にも適しています。