長尾高弘のレビュー一覧

世界でもっとも強力な9のアルゴリズム

ジョン・マコーミック / 長尾高弘

ページランク、公開鍵暗号、２フェーズコミットなどIT系の人間にはある程度常識となっている著名なアルゴリズムを平易に解説している本。数式や抽象的な記述を極力排除した平易な解説が特徴なのだが、それが逆に少々まどろっこしいという印象もある。数式嫌いの人にはとても良い本だと思います。

個人的には第十章、決定不能性の章がおもしろかった。存在し得ないプログラム、を具体例を通して解説されておりとてもわかりやすい。全てのプログラムを対象としたクラッシュ検出プログラムというのが実現不能であることを具体例を通じてわかりやすく証明しています。チューリングなどが研究していた内容。要するに、”全てのプログラム”を対象とすると、プログラムには自分自身も含まれ、自己言及が発生するとおかしくなる、というのが肝だと思います。ゲーデルの不完全性定理などと通じるないようですね。ただ筆者も述べているように、”決定不能性がコンピュータの利用に及ぼす実際の影響はない”。あくまでも理論的な限界の追求ですね。なのであまり応用的な面では重要ではないのでしょうが、コンピュータ科学の理論としてはおもしろいと思います。