チューリングを読む コンピュータサイエンスの金字塔を楽しもう

著者名：チャールズ・ペゾルド【著】/井田哲雄【訳】/鈴木大郎【訳】/奥居哲【訳】/浜名誠【訳】/山田俊行【訳】

日経BP（2021/02発売）

• ISBN：9784822283728

内容説明

■コンピュータと数学の限界に答えを出す!
イギリスの数学者アラン・チューリングは1936年に、「計算可能数とその決定問題への応用」という
論文を発表しました。後に「チューリング機械」と呼ばれる想像上のコンピュータが初めて示された論文です。
チューリング機械は有限個の状態をとれる機械がテープのマス目を読み書きするだけのたいへん単純な機械です。
それは計算することの原理的な仕組みと限界を明らかにするための機械でした。

驚くべきことに、あらゆるチューリング機械は一つの整数で表すことができます。そのことは、計算可能な数の
全体が可算無限個であり、連続体をなす実数全体のうちのほんの一部でしかないということを意味しているのです。

さらにチューリングは、テープ上の記号の複写や消去といったチューリング機械の動作のいわばサブルーチンを
組み合わせて、あらゆるチューリング機械の動作を模倣できる「万能機械」を構成しました。万能機械は今日のコン
ピュータの原型のようなものです。この観点から見ると、一切のデジタルコンピュータはチューリング機械の実用版
なのです。
本書はチューリングの「計算可能数とその決定問題への応用」の原論文を楽しむためのガイドブックです。原論文をゆっ
くりと、逐一注釈していきます。原論文を理解するために必要な数学的な準備や、戦争の時代を生きたチューリングの波乱の
生涯にもたっぷりとページを割いて話を進めていきます。

目次

第１部　基礎（ディオファントスここに眠る／無理数と超越数／進歩の世紀）
第２部　計算可能数（アラン・チューリングの受けた教育／動く機械／加算と乗算／またの呼び名はサブルーチン／すべては数／万能機械／コンピュータと計算可能性／機械と人間）
第３部　決定問題（論理と計算可能性／計算可能関数／主要な証明／ラムダ計算／連続体をめぐって）
第４部　展望（万物はチューリング機械か／ディオファントスの長き眠り）

感想・レビュー

※以下の感想・レビューは、株式会社ブックウォーカーの提供する「読書メーター」によるものです。

[ぺ]

チューリングの論文「計算可能数とその決定問題への応用」の注釈書。注釈に加え、論文を読むための数学的な基礎知識やチューリングを取り巻く歴史的背景などを詳述しているため、600頁の大作となっている。論文自体は言わずもがな、論文の注釈でさえも現在の私の知識状態では理解することが非常に困難(というか無理)。数理論理学と情報工学の分野に明るく、更に根気のある人でないと全て読むのは厳しいかと。しかし、史実の描写と著者の哲学的考察は非常に面白く引き込まれた。良作。

2013/09/11

[Akiro OUED]

テープに０と１を印字する規則を定め、そこから具体的に万能機械を構成した。その論文を本書のような解説なしで理解した査読者も賢い。命題を数値化したゲーデルのアイディアなしでも、チューリングは、計算機械が個別の記述数を持つ、というアルゴリズムの数値化にたどり着いたろうね。好著。

2022/03/05

[takao]

難しいな。

2017/05/09

[やす]

情報処理関係の「チューリングの大聖堂」「インフォメーション」と並んで勝手に３部作と呼んでしまおう。３作ともチューリングは主役級であるが本作はチューリングの論文の解説書。チューリングマシンそのものが定義された論文だけに重みが違う。しかし難解度はMAXで歯が立たない。創生期から文字列処理ってのがメイン機能であり、関数の概念やバーチャルマシンの概念がそもそもあったってのが物凄いところ。今も変わらずVM立てて関数設計し文字列を処理しているからなあ。最初期の概念マシンの面白いところはネイティブな数値型がないところ

2013/08/26

[Tm]

チューリングマシンについて知りたくて読み始めた　第１章が　ディオファントスここに眠る　で　最終章が　ディオファントスの長き眠り　になっている　ディオファントスの碑文　ユークリッドの公準　チューリングマシンにできることできないこと　人はマシンか　宇宙はチューリングマシンか　ブラウワーの実数論　そして最後の一節は　人生の意味が人それぞれであるように、解のあるディオファントス方程式もあればそうでないものもある。あとの多くのことは、決して知ることはできないのだろう　で終わる　また読み返したい

2020/01/02