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

高岡詠子【著】

2014/11/24

名前はよく聞くチューリングだけど、実はよく分かってないこともあって読んでみた。
正直、やっぱりというかなんというか、読んでもまだ良くわからない部分も多かった。アルゴリズムや論理演算の話は分かるのだけど・・・。
とにかく、『計算できる』とは、チューリングマシンで計算できるものをいうらしい。なお、計算できるというのはある問題の手順を有限で表せるということで、1/3や、πなどは無限の数値になるけど、計算手順は有限だから計算できるということになるのだとか。まあ、それは確かにそうなのかも。
そういえば、よく聞くNP問題だけど、ようやく意味を理解できた。そういうことだったのか。そういや、ぷよぷよはNP完全性とかいう論文が前に話題になっていたような気が。
ところで、1/3を2進数で表すと、0と1が交互に現れる数値になるのだとか。これは初めて知った。
そういや、この本に書いてあった1024個のものから他より重さが重い1つを探す問題だけど、この本では10回で終わるアルゴリズムを紹介してたけど、もっと効率的にやれば7回でできるよなと思った。

2014/04/13

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

2014/03/24

人間の行う足し算引き算から”計算”を説き起こし、機械にその計算をさせるには”計算の手順”（アルゴリズム）が必要になり、さらにオートマトン、チューリングマシンの解説と進んでいく。
プログラムを書く上で必須な”計算量”の説明がとてもわかりやすい。この計算量とP=NP問題の解説は簡潔でわかりやすく、この第6章を読むだけでもこの本の価値はあると思う。