アンダースタンディングコンピューテーションを読みました

学校では実務に即した設計や実装を学んでいたので、学術的な
計算機科学をちゃんとやってみたいな、と思い、そのきっかけに読んでみました。

完全に初学者で、本も読み終わりましたが全て理解したとは言いがたいです。
が、面白かった。次に読むべき本、もたくさん紹介してくれたので少しづつ
進めていこうと思います(アルゴリズムへの関心も持てました)

全体の流れ

以下の様な構成になっています。基本的には
最初から最後まで順番に読み進めるように書かれています。

  • 計算機の意味論について
  • 決定性オートマトンと非決定性オートマトン
  • そこにスタックというストレージを与える(プッシュダウンオートマトン)
  • シミュレートしたオートマトンの限界とチューリングマシン
  • 万能チューリングマシンとは、万能性とは
  • チューリングマシンと同等の能力をもつその他の機械と、そのシミュレート
  • 万能チューリングマシンの能力を上げるということ (=不可能)
  • 万能チューリングマシンには実現できないこと

よかったところ

日常的にプログラムを書くが、計算機科学はサッパリ、という僕のような方は
多いと思いますが、そういう人を対象に書かれています。

全編を通してRubyを用いて様々な古典的な計算機をシミュレートしています。
これは僕の勝手な予想ですが、なぜRubyが用いられているのか、おそらく

  • モンキーパッチングが可能で、定義済みのクラスを簡単に変更できる
  • irbという優れたREPLが存在する
  • 動的型である

なのだと思います。

オートマトン -> プッシュダウンオートマトン -> チューリングマシン
の流れは非常にわかりやすく、Rubyさえ書けて読めれば自然と納得できると思います。


ちょっと大変だったところ

大きく2つ、読み進めるうえで理解が進みづらい部分がありました。

1つは、しょっぱなの『意味論』について。
何度も読むか、ほかの本も読んだりしないと難しいかもしれません。

プログラミング言語がどのような『文法』で描かれて、どのように
簡約されていくか、みたいな約束の集合、だと今のところ思ってます。

もう一つは6章『無からのプログラミング』で
procだけで型なしラムダ計算をシミュレートしてみよう、という内容なんですが
何度も脳内スタックがオーバフローしました。

ざっと読んで後でコード書こうかな、と思ったけどほとんどコードで構成された
章で、変数定義とprocの生成しか許されていないため、大量の簡約が
行われます。これを解説を読みながら、プログラムを書いて、そして納得するのが
非常に難しかった・・・。(仕方ないけど)コンビネータの話も、いわゆるおまじない的だった


読みなおしたいところ

  • 意味論について(2章)
    • 意味論とは何か、が自分で説明できない
  • 万能チューリングマシンについて(5章, 7章)
    • チューリングマシン≠万能チューリングマシン
  • 万能機械の実装 (6章)
    • ほとんど書き写すだけで終わっちゃったので

後で読む用

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です