チューリングの計算理論入門 の商品レビュー

高岡詠子【著】

2024/01/17

大学の授業で必要だったので読んだ本。
チューリングマシンについてはすでに勉強していたため特に目新しいことはなかったけれど、先にこの本を読んでいたら理解がもっとスムーズにできたかもしれない。

後半にある計算量についての話が、今まで見たことあるけれどよくわからなかったことが説明されており楽しく読むことが出来た。
計算量の話でO(n)とかO(log n)とかなんだ？といった状態だったのが二分木探索での説明のおかげで理解することができた。

ので、これからは計算量を気にしていかないといけないね。

2022/01/03

図書館で借りた。
情報工学の基本的な分野である、チューリングマシン、オートマトンといった側面からコンピュータの基礎を学べる本。情報系大学の初等教育といったところ。
語り口はやさしく、得意でない方がはじめるにはお勧め。

2020/09/18

チューリングの理論だけでなく，P≠NP問題についても分かりやすくまとめられていてとても面白かった．

初学者が計算機科学に興味を持つためには良い1冊だと思います．

欲を言えば，もう少しアラン・チューリングの生い立ちや人物像について触れて欲しかったです．

2019/08/29

新50ポンド札にチューリングが採用される！
大戦中に暗号解読に多大な役割を果たし、
私たちの暮らしに影響を与えた数学者、ご存知ですか？

2019/03/04

現在コンピュータなしでは日々の生活が成り立たないと実感するが、そのコンピュータの万能性を保証する理論がタイトルの計算理論との事。計算の定義やアルゴリズムの概念等を踏まえ決定問題から着想されたチューリングマシンの解説はとても参考になった。

2018/10/19

チューリングは何を証明しようとしていたのか。チューリング・マシンを使ってアルゴリズムが記述できる問題は計算可能であると証明した。つまり、アルゴリズムが記述できない問題は計算不能である。ヒルベルトの「決定問題」を解決するべくチューリング・マシンのアイデアは生まれた。

2018/08/05

予備知識ゼロでも理解できるように書いてあるチューリングマシンのすごく丁寧な入門書。

チューリングは抽象的なモデルを組み立てることで決定問題を解いた。つまり、決定問題を解くという目的のために「チューリングマシン」を作り出したわけですね。それはゲーデルのゲーデル文と同じように画期的なアイデアで、結果、決定問題のために作ったこのアイデアが、後にコンピュータを生み出すことになった。出来すぎです。

数学者がこういう抽象的な概念を創造するっていうところがたまりません。

あらためて思うのは、チューリングマシンの考案にはヒルベルトの貢献も非常に重要だったという事ですね。なんだよ、問題出しただけじゃねーかとか思っていたけど、ヒルベルトが課題を浮き彫りにしたからこそゲーデルやチューリングが生まれたわけですから。後から見れば課題を見つけ出すってことの究極版だったわけですね。

ヒルベルトは数学世界の理想のためにこれらの問題を出した。その卓越した洞察力もさることながら、すごく人間味溢れる視野ですよね。

はぁ、天才たちの足跡はどれもたまらないですね。
チューリングマシンのエッセンスに触れられる本書、面白かったです。

2015/12/25

ヨーロッパ物理学連合の会誌『EurophysicsNews』連載コラムの中から、人気の高かったテーマを厳選。単純だけれど奥深い物理の楽しさをお届け。

2015/10/10

チューリングマシンをメインの題材として計算機科学の専門知識をあまり持たない読者にもわかるように「計算」とは何かを平易な言葉で考察している。

そもそもチューリングマシンが考案されるきっかけとなったのは、ヒルベルトの出した課題である決定問題である。この問題を解くためには「計算」を数学的に厳密に表現する必要があり、その手段としてチューリングマシンが考案されたのである。そして、このチューリングマシンが物理的に実現されたものがコンピュータなのである。

我々が普段触れているコンピュータはフォンノイマン型コンピュータと呼ばれ、名前の通り、ジョンフォンノイマンという天才が具体的な形で考案した仕組みで動作する機械である。ただ、フォンノイマンが何の概念がないところから１から発明したわけではなく、それぞれの年代の計算に対する概念の開拓の歴史を汲み取って考案したのである。ブール代数等々。

チューリングマシンの具体的動作をステップバイステップで説明している一般書はなかなかないであろう。丁寧に説明がなされているので非常にわかりやすい。万能チューリングマシンについても説明があってよい。

時間計算量の導入からN=NP問題についてもさくっと概説あり。

2015/08/12

全章にわたって、身近な事柄から理論へ掘り下げていくかたちで、知識を広げてくれた本。
広い意味での計算をコンピュータがどのように実行しているのか、コンピュータと数学はどのようにつながっているのかを概観できる。
全編ですます調、語りかける感じ書かれているため、読みやすいほうだと思う。

# 読後感
歴史的、数学的な解説を通して、知識が肉付けされ、また断片的だった知識が統合されていく体験をした。

# 各章の主題
1 計算とは何か
2 計算機の歴史、アルゴリズム
3 オートマトンと単能チューリングマシン
4 ヒルベルトの決定問題
5 万能チューリングマシン
6 計算量、P対NP問題、NP完全とNP困難
7 電子計算機の実現、Computer Science Unplugged、2進数、ブール代数と論理回路

# 各章の感想詳細

第3章の「オートマトンと(単能)チューリングマシン」では、簡単な問題について、チューリングマシンがどのようなアルゴリズムを実行するのかが紹介されている。この本でいちばん分かりやすく、楽しめた部分かもしれない。
・空白を読み取るまで0を1に書き換える
・3+2
・0と1を交互に表示する
・掛け算

4章の決定問題では、停止性問題について、歴史的経緯をおりまぜながら、要点を簡潔に示している。(これは、『9のアルゴリズム』本で、現代的な喩え(クラッシュ判定)を用いて、段階を追って書かれていたのとは対照的。)

5章と6章はとたんに難易度が上がった感じがした。
5章 万能チューリングマシンのところは、丸呑みした読んだ感じ。全般的に直感的には理解できなかったが、現代的なコンピュータのモデルということで、関数や条件分岐など、慣れ親しんだ概念も登場する。
6章では、アルゴリズムの評価基準である計算量について、具体例とともに丁寧に解説している。情報処理の試験では計算量理論が、現代暗号の安全性と数学的につながっていることが解説されている部分が、個人的に関心をひかれた。