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

高岡詠子

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

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

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

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

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

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