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

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

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

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

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

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

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

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

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

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

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