計算理論（参考書紹介）

計算理論とは、その名の通り計算に関する理論です。具体的には、コンピュータが問題を解くという状況を考えてその問題が計算可能か、またどの程度複雑か（時間がどれぐらいかかるかなど）を考えるというものだと考えられます。

 

 

まず1冊目として、計算理論の基礎の第一巻を読みました。この本では、計算とは何かを厳密に定義するということが大きなテーマです。まず有限オートマトンという計算モデルを定義して、その有限オートマトンが認識できる言語（正規言語）の性質について学んだり、有限オートマトンの性質について学びます。また、有限オートマトンの限界を知るために、これが認識できない非正規言語について学びます（ポンピング補題）。

後半では、正規言語より更に広い概念、文脈自由言語について、有限オートマトンと同じような手順で学んでいきます。薄くて簡単なので一週間程度で一周することができました。具体例が多く初学者でも楽に理解することができる親切仕様になっていました。ただ、これだけを読んでも一体計算理論が何に役立つのかはあまりわかりませんでした。「なるほど、計算というのはこのように厳密な定義を与えられるのだなあ」とだけ思いました。第二巻、第三巻を早く読みたいです。

 

自己紹介

初めまして。

このブログを始めたのは、ただ匿名で思考を垂れ流したり、勉強の記録を残したりしたいからです。圧倒的自己満ですが、そもそもブログってそういうものだと思うので。

内容は、とりあえず普段考えているしょうもないことを呟くか、勉強の記録をつけるか、日向坂の話をたまにするかぐらいを考えています。日向坂は、ひらがな推しが始まった時に、番組の面白さに惹かれて好きになりました。その頃からの推しは丹生ちゃんで、最近は髙橋未来虹ちゃんも推しています。

まあ、知り合いに知られることなく匿名で思考を垂れ流したいから始めたブログで自己紹介しすぎるのは本末転倒なのでこの辺で終わりにします。

ブログのフォローとかしてくれるととても嬉しいです。よろしくお願いします。