「白と黒のとびら」書評

「白と黒のとびら: オートマトンと形式言語をめぐる冒険」を読んだので個人的な備忘録です。

■どんな本か■
魔法使いに弟子入りした少年が試練を乗り越えるお話を読みながら、
オートマトンと形式言語について触れられる本です。
小学生でも読めると思います。

■読み方■
所謂技術書ではなく、間にファインタジー形式の話が挟まっているので、
最初は若干の読みにくさがありました。
まだるっこしい人はファンタジー部を読み飛ばすといいかもしれません。
文章の中から問題のヒントを探しながら解いていく計算問題に似ていると思います。
専門用語がない分読みやすい反面、「塔」の章は頭が爆発しそうになりました。
紙とペンを持って自分でメモしながら読むと良いと思います。

■チューリングマシンと対角線言語■
正直、エピローグから前2章分が何を言ってるのか分からなかったのですが、
解説を読んで自分なりに解釈したものをメモしておきます。

・受理される文字列 -　受理されない文字列 =　対角線言語
・「対角線言語」を受理するチューリングマシンは存在しない
・「対角線言語」を受理するチューリングマシンが存在すると矛盾が生じる

何でわざわざ自明なものを定義しているのかが分からなかったのですが、
「チューリングマシンで解けない問題」
(コンピューターの限界)
を定義するためですね。

<まとめ>
個人的に今取り組んでる内容と一致して面白かったのが12章と13章でした。
あと1冊くらいオートマトンと言語理論の本を読もうと思っています。

おわり