算術士になるため算術の専門家である tri_iro さんに文献などをいろいろ聞いた記録:あとの参照用についでに算術以外もいろいろまとめた方の市民

この記事は13分で読めます

このサイトは学部では早稲田で物理を, 修士では東大で数学を専攻し, 今も非アカデミックの立場で数学や物理と向き合っている一市民の奮闘の記録です. 運営者情報および運営理念についてはこちらをご覧ください.

理系のための総合語学・リベラルアーツの視点から数学・物理・プログラミング・語学 (特に英語) の情報を発信しています. コンテンツアーカイブに見やすくまとめているのでぜひご覧ください.


追記
やたべさんから次のようなご指摘を頂いたので
タイトルなど少し書き換えた.

追記終わり

算術士を目指したいので算術の専門家である
tri_iro さんにいろいろ聞いたらいろいろ教えてもらったのでその記録.

まだもう少し続く.

tri_iro さんが RT していた魔法少女.

他の RT.

そしてやりたいのはこれだ.

他にも RT.

ゼルプスト殿下の RT.

あと別件だが再帰理論のも転載しておこう.

再帰理論をやろうと思っても、やっている人がまわり居なくてどうしていいかさっぱりわからないので、よかったら良い教科書か入門書を教えてください!
■和書:
初めに述べておくと、和書では個人的なオススメ本は一つもありませんが、一応、和書から紹介。

■ マイケル・シプサ 『計算理論の基礎』
オススメ度:☆ 難易度:☆
もし、『計算可能性』について全く知らないのであれば、再帰理論を学び始める一歩手前に。

■ 廣瀬 健 『計算論』
オススメ度:? 難易度:?
一応、和書なのでリストに挙げておきますが、内容知りません。

■ 篠田 寿一 『帰納的関数と述語』
オススメ度:☆☆ 難易度:☆
再帰理論の和書としては、一番有名なのかな。
【利点】 一から丁寧に書かれているため、予備知識一切なしに読むことが出来る。
【欠点】 話題のチョイスが極めて独特でマニアックなので、標準的な教科書とは言い難い。再帰理論の標準的トピックが省略されて、抽象計算量など再帰理論と関係の薄い話題にページを割いている。

■ 田中 一之 『逆数学と二階算術』
オススメ度:☆☆ 難易度:☆☆☆
再帰理論と逆数学をまとめて勉強したい人にオススメ。
【欠点】 薄い本なので、説明も薄く、ある程度予備知識を持ってる人じゃないと読むのはしんどいかも。

■ 田中 尚夫 『選択公理と数学』
オススメ度:☆☆☆☆ 難易度:☆☆
再帰理論の本ではないんですが、再帰理論のアイデアやテクニックがかなり用いられているので、再帰理論の本と並行に読むと楽しいかも。選択公理ちゃんマジ公理。

■ 新井 敏康 『数学基礎論』
オススメ度:☆☆☆☆ 難易度:☆☆
第2章と第6章が再帰理論の話題。再帰理論を含む、数学基礎論の色んな分野の古典をまとめて一気に勉強したい!という人にオススメ。
【利点】 再帰理論が誕生した当初の’40年代~’50年代の重要な定理には一通り触れてくれているので有難い。
【欠点】 逆に言うと、’40年代~’50年代よりも後の研究にはほとんど触れられていない。あくまで古典。

■ 李 昂生 『可计算性理论』
オススメ度:☆ 難易度:☆☆☆
まともな再帰理論の教科書が一つも出版されていない日本とは異なり、中国語の再帰理論の教科書はそれなりにあります。「英語よりも中国語の方が得意だぜ!」という奇特な方へのオススメ本はコレ!
【利点】 再帰理論の基本的証明技法である優先法 (priority argument) について詳細に書かれており、 Lachlan’s nonbounding theorem などの monstrous injury priority argument を用いた証明も丁寧に解説されている。
【欠点】 言語の壁は厚い。

■洋書

■ Cutland, “Computability: an introduction to recursive function theory” (1980)
オススメ度:☆ 難易度:☆
極めて普通の入門書。再帰理論の入門書というよりは、計算可能性の初歩に関するトピック。

■ Martin Davis, “Computability and Unsolvability” (1958)
オススメ度:? 難易度:?
読んだことないけど、よく話を聞くので。

■ Barry Cooper “Computability Theory” (2002, 2011)
オススメ度:☆☆☆☆☆ 難易度:☆
個人的に初学者へのオススメの一品はコレ。
【利点】 初歩から超丁寧に書かれていながら、結構深く広い話題に発展する理想的な教科書。
【欠点】 解析的階層や認容順序数などの再帰理論における主要なトピックの一部には全く触れられていない。

■ Hartley Rogers, Jr., “The Theory of Recursive Functions and Effective Computability” (1967)
オススメ度:☆☆☆☆ 難易度:☆☆
古いけど色褪せない輝きを放つ、古典的な再帰理論の名著。
【利点】 1940年代~1950年代の再帰理論研究の集大成。
【欠点】 ちょっと古臭くて読みにくい。

■ Manuel Lerman, “Degrees of Unsolvability: Local and Global Theory” (1983)
オススメ度:☆☆☆ 難易度:☆☆
次数の大域的構造が好きで好きでたまらない人へ贈る、職人の技術が詰め込まれた書籍。
【利点】 無料公開されました!
【欠点】 優先法の話題が全く載ってないのが致命的な欠点か。

■ P. Odifreddi, “Classical Recursion Theory” (1989)
オススメ度:☆☆☆☆ 難易度:☆
再帰理論の古典について、幅広く網羅的に書かれたオススメの名著。
【利点】 やたら重くて硬いので、装備すると攻撃力がかなり上昇する。
【欠点】 個々の話題の取り扱いが非常に薄いため、証明技術などをこの書籍で身につけようとするのは困難。

■ P. Odifreddi, “Classical Recursion Theory: Volume II” (1999)
オススメ度:☆☆☆ 難易度:☆☆
上記の本の続編。しかし、1巻に比べると話題のチョイスが若干迷走している感じ。
【利点】 話題の幅広さ。
【欠点】 3巻出る出る詐欺。

■ Robert Soare, “Recursively Enumerable Sets and Degrees” (1987)
オススメ度:☆☆☆☆ 難易度:☆☆
再帰理論の基本的な証明技術を学ぶための教科書。一方で、話題が限定的なので、再帰理論の概観を眺めるという点では微妙。
【利点】 再帰理論の基本的技術を網羅的に取り扱っている。
【欠点】 再帰理論の研究トピックの極一部にしか触れていない。

■ Gerald E. Sacks, “Higher Recursion Theory” (1990)
オススメ度:☆☆☆☆ 難易度:☆☆☆☆
解析的階層の理論から順序数上の再帰理論までを統一的に取り扱った名著。記述が若干古臭いのだけれど、それにも関わらず読みやすい気がします。
【利点】無料公開されました!
【欠点】記述が若干古臭い。

■ Jens E. Fenstad, “General Recursion Theory: An Axiomatic Approach” (1980)
オススメ度:☆ 難易度:☆☆☆
用語が独特で若干読みにくい。意外と深い内容が書かれているんだけど、マニア層向け。

■ M. C. Fitting, “Fundamentals of Generalized Recursion Theory” (1981)
オススメ度:☆ 難易度:☆☆☆
同上。マニア層向け。

■ Peter G. Hinman, “Recursion-Theoretic Hierarchies” (1978)
オススメ度:☆☆☆ 難易度:☆☆☆
階層理論の話題が網羅されているのは嬉しい.この分野の入門書として最低限必要な話題である算術的階層・解析的階層・算術的強制法・基底定理の古典的結果は網羅されている。話題のチョイスが良い代わり、記述が古臭くて読みにくいのが残念。
【利点】 古典的な Δ^1_2 集合の理論のバイブル。
【欠点】 ちょっと論理論理しすぎてて読みづらいかも。

■ Manuel Lerman, “A Framework for Priority Arguments” (2010)
オススメ度:☆☆ 難易度:☆☆☆☆☆
優先法マニア待望の、優先法に特化した教科書だよー!!
【利点】 優先法を理解している人が読むと、思考を整理できるかも。
【欠点】 優先法を既に理解している人じゃないと読める代物じゃない。

■ Ash and Julia Night, “Computable Structures and the Hyperarithmetical Hierarchy” (2000)
オススメ度:☆☆☆☆ 難易度:☆☆☆
再帰モデル理論の基本的な教科書。個人的にはかなりオススメ。
【利点】 超算術的階層や解析的階層についても一緒に学べる。
【欠点】 特になし。

■ Yuri L. Ershov and Sergei S. Goncharov, “Constructive Models” (2000)
オススメ度:☆☆ 難易度:☆☆
再帰モデル理論の基本的な教科書。こちらはかなりベーシックなモデル理論。
【利点】 上の本よりは初等的な内容から書かれているかも。
【欠点】 個人的にはちょっと読みづらく感じる。

■ “Handbook of Computability Theory” (1999)
オススメ度:☆ 難易度:☆☆☆
標準的教科書に比べて勝ってる部分はあまり無いような……。

■ “Handbook of Recursive Mathematics, Volume 1: Recursive Model Theory” (1998)
オススメ度:☆☆☆☆ 難易度:☆☆☆
再帰モデル理論に関する基本的話題を一通り知りたい人のためのハンドブック。

■ “Handbook of Recursive Mathematics, Volume 2: Recursive Algebra, Analysis and Combinatorics” (1998)
オススメ度:☆☆☆ 難易度:☆☆☆
再帰数学、逆数学に関する基本的話題を一通り知りたい人のためのハンドブック。

■ Andre Nies “Computability and Randomness” (2009)
オススメ度:☆☆☆ 難易度:☆☆
ランダムネスの基本的な教科書その1

■ Hirschfeldt and Rod Downey “Algorithmic Randomness and Complexity” (2010)
オススメ度:☆☆☆☆ 難易度:☆☆
ランダムネスの基本的な教科書その2

■ Marian B. Pour-El and J. Ian Richards, “Computability in Analysis and Physics” (1989)
オススメ度:☆☆☆ 難易度:☆
計算可能解析の古典的な良書。解析学や物理学と計算可能性の関係を知りたい方にはオススメ。

■ K. Weihrauch, “Computable Analysis” (2000)
オススメ度:☆☆☆ 難易度:☆
計算可能解析の基本的な教科書。上の本よりはスッキリと書かれている。位相空間論と計算可能性の関係を知りたい方にはオススメ。

■ Stephen G. Simpson “Subsystems of Second Order Arithmetic” (1999, 2009)
オススメ度:☆☆☆ 難易度:☆☆
逆数学の基本的な教科書。
後半の ω-モデルの章と β-モデルの章を読めば、再帰理論との関連性が明確になると思います。ただし、この本は再帰理論の専門的知識を使うトピックを可能な限り避けているので、前半部分は再帰理論っぽさは少ないかも。

■ 近刊予定
■ Douglas Cenzer and Jeff Remmel, “Effectively closed sets”
近年、ランダムネスを初めとする様々な分野で重要性が認識されてきたΠ^0_1集合の理論に特化した教科書。期待の一品。

■ Robert I. Soare, “Computability Theory and Applications I: The Art of Classical Computability”
再帰理論の新たなる教科書を目指して執筆中の教科書。Π^0_1集合の理論や再帰理論の微分幾何への応用などが重点的に書かれる予定らしい。

■ Robert I. Soare, “Computability Theory and Applications II: Applications of Computability”
上の本の2巻。

■ John Longley and Dag Normann, “Computability At Higher Types”
高階の計算可能性理論の教科書らしい。

■ Damir D. Dzhafarov and Carl Mummert, “Reverse Mathematics”
Simpson本との棲み分けのために、おそらく再帰理論的な視点を重視してくると思われます。
逆数学のための再帰理論の技術や証明技法を解説した技術的教科書になると推測。

■ 近隣分野の良書

■ Sanjay Jain, Daniel N. Osherson, James S. Royer, Arun Sharma, “Systems That Learn: An Introduction to Learning Theory” (1999)
オススメ度:☆ 難易度:☆
計算論的学習理論の中でも、特に帰納的推論について詳しく書かれた教科書。
初学者向けに非常に丁寧に書かれていて読みやすい。

■ Jon Barwise “Admissible Sets and Structures: An Approach to Definability Theory” (1975)
オススメ度:☆☆☆☆ 難易度:☆☆☆☆
順序数上の再帰理論を展開するための認容集合の理論について書かれた教科書。
集合論と証明論の知識も多少持っていた方が読みやすい。

■ Yiannis N. Moschovakis “Descriptive Set Theory” (1980, 2009)
オススメ度:☆☆☆☆☆ 難易度:☆☆☆☆
“Handbook of Mathematical Logic” では、記述集合論は再帰理論の項目に分類されていたので、これも再帰理論の教科書だと思います! 古典記述集合論のバイブルとも言うべき名著。個人的には超オススメです。

■ Kechris “Classical Descriptive Set Theory” (1995)
オススメ度:☆☆☆ 難易度:☆☆☆
Moschovakis本とは方向性がかなり違うけれど、これも古典記述集合論のかなりの良書。
ロジック慣れしていない人にはこちらの方が読み易いかも。


とりあえず手許にあった再帰理論関連の教科書を一通りレビューしました。

結論として、個人的なオススメ教科書は:

■初めて再帰理論を学ぶ人:
Barry Cooper “Computability Theory”
P. Odifreddi, “Classical Recursion Theory”
Hartley Rogers, Jr., “The Theory of Recursive Functions and Effective Computability”

■更に一段階進んで再帰理論を知りたい人:
Manuel Lerman, “Degrees of Unsolvability: Local and Global Theory”
Gerald E. Sacks, “Higher Recursion Theory”
Ash and Julia Night, “Computable Structures and the Hyperarithmetical Hierarchy”
Yiannis N. Moschovakis “Descriptive Set Theory”

という感じかなあ、と思います。

追記 2
やたべ・tri_iro さん間でさらにやり取りがあったので追記する.
いろいろただで教えてもらえてこんなにありがたいことはない.
私も頑張ろう.

  • このエントリーをはてなブックマークに追加
  • LINEで送る

関連記事

  1. この記事へのコメントはありません。

  1. この記事へのトラックバックはありません。

このサイトについて

数学・物理の情報を中心にアカデミックな話題を発信しています。詳しいプロフィールはこちらから。通信講座を中心に数学や物理を独学しやすい環境づくりを目指して日々活動しています。
  • このエントリーをはてなブックマークに追加
  • LINEで送る

YouTube チャンネル登録

講義など動画を使った形式の方が良いコンテンツは動画にしています。ぜひチャンネル登録を!

メルマガ登録

メルマガ登録ページからご登録ください。 数学・物理の専門的な情報と大学受験向けのメルマガの 2 種類があります。

役に立つ・面白い記事があればクリックを!

記事の編集ページから「おすすめ記事」を複数選択してください。