【感想・ネタバレ】チューリングの計算理論入門 チューリング・マシンからコンピュータへのレビュー

高岡詠子

本書は、コンピュータの原理としてのチューリング･マシンを解説するとともに、決定問題を解決した有名な｢チューリング･マシンの停止問題｣も分かりやすく説明します。さらに計算量と、7大難問の一つ｢P=NP問題｣についても、わかりやすく解説します。(ブルーバックス･2014年2月刊)※この商品は紙の書籍のページを画像にした電子書籍です。文字だけを拡大することはできませんので、タブレットサイズの端末での閲読を推奨します。また、文字列のハイライトや検索、辞書の参照、引用などの機能も使用できません。

[ブクログ · ★★★★☆]

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

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

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

[ブクログ · ★★★★☆]

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

[ブクログ · ★★★★☆]

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

[ブクログ · ★★★★☆]

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

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

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

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

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

[ブクログ · ★★★★☆]

これだけ易しく説明してもらえて、ようやくわかってきた気がする。
チューリングマシンが現在のコンピュータの原理となっている理由や、アルゴリズムとは何かなどを。P=NPについては間違えて理解していたことがわかった。今まで読んだ関連書籍を読み返す必要がある。