What Can Be Computed? A Practical Guide to the Theory of Computation（何が計算できるか：計算理論の実践ガイド）

引用

MacCormick, J. (2018). What Can Be Computed? A Practical Guide to the Theory of Computation. Princeton University Press.

章の要約

本書は18章からなる。導入の概観、計算可能性理論の第I部（第2–9章）、計算複雑性理論の第II部（第10–14章）、起源と応用の第III部（第15–17章）、そして短い結論である。教員向けの序文では、本書がどの種類の理論の授業に向くか、何を含め何を除いたか、本書に基づく授業の組み方を論じている。出版社によれば、本書は計算可能性と複雑性に同じ比重を置き、本文ではPythonのプログラムを使い（Java版はオンライン）、標準的な定理を完全な厳密さで述べて証明する。講義スライドとPythonのプログラムは付属サイトで公開されている。各章の末尾には演習がある。

第1章：Introduction: What Can and Cannot Be Computed?（序論：何が計算でき、何が計算できないか）

問題を、扱いやすい問題、扱いにくい問題、計算不能な問題に分類し、本書のより詳しい概観を示し、前提知識、目標、計算理論を学ぶ理由を述べる。

第2章：What is a Computer Program?（コンピュータプログラムとは何か）

第I部を通じて使うモデルを定める。一つの文字列を受け取り一つの文字列を返す「SISO」Pythonプログラムである。必要なPythonの知識、問題のあるプログラム、Pythonプログラムの形式的定義、判定プログラムと等価なプログラム、現実のプログラムとこのモデルの関係を扱う。

第3章：Some Impossible Python Programs（ありえないPythonプログラム）

他のプログラムを解析するプログラム（yesOnString.py、yesOnSelf.py、notYesOnSelf.py）に背理法を適用して、ある種のプログラムは存在しえないことを示す。そこから、完璧なバグ発見プログラムは不可能だが、有用なバグ発見プログラムは不可能ではないと結論する。

第4章：What is a Computational Problem?（計算問題とは何か）

グラフ、アルファベット、文字列、言語を導入し、計算問題とその分類を定義して、問題を「解く」こと、言語を認識することと判定することの形式的な意味を与える。

第5章：Turing Machines: the Simplest Computers（チューリング機械：最も単純なコンピュータ）

チューリング機械を定義し、いくつかの自明でない機械を作り、単一テープから多テープの機械へ、さらにPythonプログラムへと進む。逆方向として、Pythonでチューリング機械を模倣する。最後に、古典的なコンピュータが量子コンピュータを模倣できること、そして既知のすべてのコンピュータがチューリング等価であることを述べる。

第6章：Universal Computer Programs: Programs That Can Do Anything（万能プログラム：何でもできるプログラム）

万能Pythonプログラムと万能チューリング機械、現実世界における万能計算、他のプログラムを書き換えるプログラム、そして決定不能だが認識可能な問題を示す。

第7章：Reductions: How to Prove a Problem is Hard（帰着：問題が難しいことの証明法）

易しさを示す帰着と難しさを示す帰着、チューリング帰着の形式的定義と性質を導入し、プログラムに関するものではない問題も含めて、計算不能な問題を次々に示す。計算不能性の証明技法のまとめも付く。

第8章：Nondeterminism: Magic or Reality?（非決定性：魔法か現実か）

非決定性Pythonプログラムと計算木を定義し、非決定性が計算可能なものの範囲を変えないことを示し、非決定性チューリング機械を形式的に与えて、認識不能な問題と、非決定性を学ぶ意義を論じる。

第9章：Finite Automata: Computing With Limited Resources（有限オートマトン：限られた資源での計算）

決定性と非決定性の有限オートマトンとその等価性、正規表現、正規でない言語、正規言語の組み合わせを扱う。

第10章：Complexity Theory: When Efficiency Does Matter（複雑性理論：効率が問題になるとき）

漸近的な実行時間とビッグO記法、プログラムの実行時間の求め方、複雑性にとって計算モデルがなぜ重要か、そして複雑性クラスを導入する。

第11章：Poly and Expo: the Two Most Fundamental Complexity Classes（PolyとExpo：最も基本的な二つの複雑性クラス）

クラスPolyとExpoを定義し、それらが計算モデルに依存しないことを示し、Expoに属するがPolyに属さない問題としてHALTEXを示して、入力の不合理な符号化について論じる。

第12章：PolyCheck and NPoly: Hard Problems That Are Easy to Verify（PolyCheckとNPoly：検証は易しい難問）

多項式時間検証器とクラスPolyCheckを定義し、非決定性によってNPolyを定義して両者が一致することを証明し、非決定性は効率よく計算できるものの範囲を変えるように見えると論じる。

第13章：Polynomial-time Mapping Reductions: Proving X is as Easy as Y（多項式時間写像帰着：XがYと同じくらい易しいことの証明）

多項式時間写像帰着を定義し、ハミルトン閉路の問題で例示し、CIRCUITSAT、SAT、3-SATを帰着によって結びつける。

第14章：NP-Completeness: Most Hard Problems Are Equally Hard（NP完全性：たいていの難問は同じくらい難しい）

P対NP、NP完全性とNP困難性、P = NPならば何が起こるか、NPの中で「最も難しい」問題としてのCIRCUITSAT（クック・レビンの定理）、NP完全性の広がり、その証明技法を扱う。

第15–17章：The Original Turing Machine（元祖チューリング機械）；You Can't Prove Everything That's True（真であることすべてを証明できるわけではない）；Karp's 21 Problems（カープの21問題）

第15章はチューリングの1936年の「計算機械」の定義を読み、チャーチ・チューリングの提唱を論じる。第16章は決定不能性を機械的証明とゲーデルの算術の不完全性に結びつける。第17章はカープの21のNP完全問題に関する論文と、問題間の帰着をたどる。

第18章：Conclusion: What Will Be Computed?（結論：何が計算されるのか）

何が計算できるかについての大きな考え方を短く振り返る。

主要概念

第1–4章：プログラムと問題

• 扱いやすい問題、扱いにくい問題、計算不能な問題：本書全体を組み立てる三つの分類。
• SISO Pythonプログラム：一つの入力文字列を一つの出力文字列に写すプログラムで、本書の主な計算モデル。
• 認識と判定：言語に属する文字列を受理することと、常に停止して正しく「はい」か「いいえ」を答えることの違い。

第5–9章：機械、万能性、帰着

• チューリング等価性：チューリング機械、Pythonプログラム、既知のすべてのコンピュータが同じものを計算するという結果。
• 万能プログラム：入力として与えられた任意のプログラムを実行できるプログラム。
• チューリング帰着：ある問題が解ければ既知の計算不能問題も解けることを示して、その問題の計算不能性を証明する方法。
• 非決定性：可能性の木へと枝分かれする計算。計算可能なものの範囲は広げない。
• 有限オートマトンと正規表現：限られた資源で計算するモデル。

第10–14章：複雑性

• PolyとExpo：多項式時間と指数時間で解ける問題。標準的なPとNPに移る前に本書が使う独自のクラス名である。
• 検証器とPolyCheck：提示された解を素早く確かめるプログラムと、そうした検証器をもつ問題のクラス。NPolyと等しいことが示される。
• 多項式時間写像帰着：ある問題を別の問題に効率よく変換すること。
• NP完全性とクック・レビンの定理：NPの中で最も難しい問題で、最初の例がCIRCUITSATである。

第15–18章：起源と応用

• チャーチ・チューリングの提唱：人間が規則に従って計算できるものは機械も計算できるという主張。
• 不完全性：決定不能性の帰結として、算術の真の命題の中には証明できないものがあること。

批判的分析

長所

• 実際のプログラムを入口にする。 出版社の説明、章題、そして The Ubyssey の書評（Angela Tian、2018年8月）は、いずれも同じ設計を示している。不可能性、万能性、帰着は、まず読者が実行できるPythonプログラムで論じられ、その後に標準的なチューリング機械による定式化が来る。
• バランスのとれた範囲。 第I部と第II部は計算可能性と複雑性にほぼ同じ分量を割いており、複雑性の部はPolyとExpo、検証器、帰着をゆっくり積み上げてからNP完全性に至る。
• シラバスを越えた背景。 第III部はチューリングの原論文を読み、決定不能性をゲーデルの不完全性定理に結びつけ、カープの21問題をたどる。
• 補助教材。 講義スライドとプログラムが付属サイトで公開されている。Ubysseyの書評は、各章末の演習と、各文献を説明する参考文献一覧にも触れている。

短所

• 形式言語は手薄。 有限オートマトンと正規表現は1章のみで、文脈自由文法、プッシュダウンオートマトン、チョムスキー階層は章の話題に含まれていない。それらを扱う授業では別の教科書が必要になる。
• Pythonが前面に出る。 読者はPythonを読むことに慣れている必要がある。Ubysseyの書評も、Pythonの例を理解するにはプログラミング経験が要ると述べている。
• 標準的でない名称。 本書はPとNPに結びつける前に、Poly、Expo、PolyCheck、NPolyという独自のクラスで議論を進める。学生は、他の教科書や試験で使われる標準的な記法とこれらの名前を対応づける必要がある。
• 複雑性はNP完全性で終わる。 章題を見る限り、空間計算量や、乱択や近似といったその先の話題は扱われていない。

コースにおける位置づけ

計算理論のコースの中で、本書は最もプログラムを中心に据えた入門書である。もう一つの入門的な教科書である Linz と Rodger の An Introduction to Formal Languages and Automata は、紙幅の大半をオートマトン、文法、プッシュダウンオートマトンに充て、構文解析の部で終わる。MacCormick はその紙幅を計算可能性と複雑性に使っている。形式言語を中心とする授業では Linz と Rodger を主教科書にし、計算可能性とNP完全性の部分に MacCormick を使うとよい。「コンピュータには何ができるのか」を中心とする授業では、その逆になる。

Sipser の Introduction to the Theory of Computation、Hopcroft、Motwani、Ullman の Introduction to Automata Theory, Languages, and Computation、Kozen の Automata and Computability は、同じ定理を標準的なチューリング機械の記法で、より多くの形式言語理論とともに扱う。MacCormick はそれらに進む前の直観的な一巡目としてよく機能する。Arora と Barak の Computational Complexity は、第14章をはるかに超えて複雑性を扱う大学院向けの教科書である。

本書の使い方

出版社は本書を、この分野に初めて触れる学部生向けに、最小限の前提知識で書かれ、独習にも適したものと説明している。実際には、Pythonを含む入門プログラミングの授業と、背理法による証明に多少触れた経験があれば、最初の章がすんなり進む。

• 中核： 第1章、続いて第I部（第2–8章）と第II部（第10–14章）を順に読む。二つの部は互いに積み重なっており、とくに非決定性（第8章）がNPoly（第12章）の土台になる。
• 第9章： 授業が有限オートマトンを扱うなら必須。そうでなければ軽く読めばよい。
• 第III部： 任意の発展的内容。第16章は論理や数学に関心のある学生に、第17章はNP完全性をもっと練習したい学生に向いている。

付属サイトからプログラムをダウンロードし、読みながら実行するとよい。とくに、他のプログラムを解析するプログラムから不可能性の議論が組み立てられる第3、6、7章でそうすること。あるプログラムが存在しえないという証明を読む前に、そのプログラムを書き換えてみるとよい。Poly、Expo、PolyCheck、NPolyに出会うたびに、標準的な名前を横に書き添えておけば、他の教科書への移行が楽になる。