計算理論の基礎 [原著第 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 情報の定義

どんなに計算資源を積んでも、原理的に解けない問題がコンピュータには存在します。その事実を雰囲気ではなく定義と証明で確かめるための巻が『計算理論の基礎 [原著第 3 版] 2. 計算可能性の理論』 (Michael Sipser 著、田中圭介 / 藤岡淳 監訳、阿部正幸 / 植田広樹 / 太田和夫 / 渡辺治 訳、共立出版、2023 年 5 月刊) です。MIT での Sipser 教授の講義ノートをもとにまとめられた標準的教科書 Introduction to the Theory of Computation の第 3 版日本語版を 3 分冊にしたうちの第 2 巻で、第 1 巻はオートマトンと言語、第 3 巻は複雑さの理論を扱い、章番号は第 1 巻からの通し番号です。訳者まえがきによれば原著は 1996 年の初版が瞬く間にこの分野の標準的な教科書となり、2005 年に第 2 版が出ています。

第 3 章から第 6 章、Turing 機械から判定不可能性 / 帰着 / 再帰定理へ

本巻に収められているのは第 3 章から第 6 章までの 4 章です。第 3 章は Church-Turing の提唱を主題に、Turing 機械の正式な定義と例、複数テープ Turing 機械や非決定性 Turing 機械、列挙装置といった変型と他のモデルとの等価性、そして Hilbert の問題を手がかりにしたアルゴリズムの定義へ進みます。第 4 章「判定可能性」は、正規言語と文脈自由言語に関連する判定可能問題を確かめたあと、対角線論法を用いて判定不可能言語と Turing 認識不可能な言語の存在を示します。第 5 章「帰着可能性」は言語理論における判定不可能問題を計算履歴を用いた帰着で扱い、単純な判定不可能問題を経て、計算可能な関数と写像帰着可能性の正式な定義に至ります。第 6 章「計算可能性の理論における先進的な話題」は、自己参照とその応用を含む再帰定理、判定可能な理論と判定不可能な理論を対置する数理論理における判定可能性、Turing 帰着可能性、最小長記述と圧縮不可能な文字列とランダム性を扱う情報の定義の 4 節で構成され、各章末には演習、問題、解答が置かれています。

停止問題と帰着が示す計算の限界、計算可能性理論の技術背景

計算可能性の理論が答えようとするのは、アルゴリズムで解ける問題と解けない問題の境界はどこにあるのかという問いです。その前提として、アルゴリズムとは何かを数学的に固定する必要があり、Turing 機械という単純な機械モデルがその役割を担います。複数テープや非決定性といった拡張を加えても認識できる言語の範囲が変わらないという等価性の結果は、この定義が特定の機械の細部に依存しない頑健なものであることの根拠で、直観的なアルゴリズムの概念と Turing 機械が一致するという Church-Turing の提唱を支えています。判定不可能性の証明の核心は対角線論法で、Turing 機械の記述が可算個しかない一方で言語は非可算個あるという数え上げの議論から、どんな機械でも判定できない言語が存在することが導かれ、その具体例として、与えられた機械が与えられた入力で停止するかを判定する問題、いわゆる停止問題の判定不可能性が示されます。帰着はここで得た 1 つの判定不可能性を別の問題へ運ぶ技法で、ある問題が解けるなら停止問題も解けてしまうことを示せば、その問題も解けないと結論できます。この考え方は実務にも直結していて、任意のプログラムについて停止や到達可能性を厳密に判定するツールが作れない以上、静的解析 や検証ツールは必ず近似や制限付きの判定に頼ることになります。再帰定理は Turing 機械が自分自身の記述を得られることを保証する結果で、自己複製するプログラムの存在や判定不可能性の別証明に使われ、情報の定義の節で扱われる最小長記述による情報量の考え方は、圧縮とランダム性を計算の言葉で定義し直す入口になります。著者まえがきによれば、第 2 巻と第 3 巻では擬似コードを使わず散文体でアルゴリズムを記述し、Turing 機械のプログラミングは簡単に済ませる方針が採られており、細部の実装より問題の直観的な理解と概観を重視する姿勢が貫かれています。

学部上級 / 大学院初級の教科書としての前提知識と、分冊 / 第 3 版の読み方

著者まえがきは本書を計算機科学理論の学部上級あるいは大学院初級の教科書として書いたと述べ、定理を証明することに慣れている学生よりも、この種の経験に乏しい学生を対象にできるよう工夫したとしています。したがって数学的な厳密さは求められますが、証明の型を一から学ぶ読者を締め出す本ではありません。ただし第 4 章の冒頭で正規言語と文脈自由言語に関連する判定可能問題を扱うように、本巻は第 1 巻のオートマトンと形式言語、そして第 0 章の数学的準備と証明のタイプを前提に組み立てられているので、第 2 巻から読み始めるなら少なくとも有限オートマトンと文脈自由文法の定義は別途押さえておく必要があります。訳者まえがきによれば、初版は合冊でしたが教育現場からページ数が多く高価格で教科書に指定しにくいとの声があり、第 2 版から教科書として指定可能な価格にするための分冊化が行われ、第 3 版では電子版が追加されました。訳者は 1995 年春に NTT 研究所へ招聘教授として招かれた Sipser 教授の講義を受けたメンバーで、本巻の第 3 章と第 4 章は藤岡氏、第 5 章は太田氏、第 6 章は第 3 版では田中氏が翻訳し、全体の調整は藤岡氏が担当しています。第 3 版の変更点として版元は問題と解答の追加と、第 2 版刊行後の研究の進展についての説明を挙げています。同じく第 3 版で新設された決定性文脈自由言語の節は、著者まえがきで 2.4 節と明記され、版元公開の詳細目次でも第 1 巻の第 2 章に置かれているため、本巻の収録範囲には含まれません。

アルゴリズムの実務で使う計算量の感覚だけを得たい人や、プログラムを書いて動かすことで学びたい人には本書は遠回りで、その目的なら アルゴリズム本の選び方 で紹介している実装中心の本のほうが早く効きます。逆に、情報系の学部で計算理論やオートマトンの科目を履修する学生、大学院で計算量理論や暗号理論へ進む前に計算可能性の基礎を固めたい人、あるいは停止問題や決定不能性という言葉を見かけるたびに素通りしてきたエンジニアが、その正体を一度根元から確かめたい場合に、定義から証明まで自力で追える本書は投じた時間が長く効く教科書です。計算機科学 の理論科目を教える側と学ぶ側の双方に届く日本語版として初版から訳し継がれてきた 3 分冊のうち、計算そのものの能力と限界を扱うこの第 2 巻は、第 3 巻の複雑さの理論へ進むための土台にもなります。