Michael Sipser：計算理論の基礎

概要

「まえがき」から引用する。ここで「理論」というのは「計算の理論」のことである。

この教科書を読み進むなかで，理論が何回でもないし退屈なものでもないことに気づいてくれると思います． よく理解できるし，それどころかおもしろいものだと分かってくれるでしょう．

章末に演習と問題がある。解答はない。なお、現在（2023-03-20）では、原著第 3 版に対する翻訳本が出ている。

感想

p.167 にある問題 3.19 は次のとおりである。

`A` を

`s = {(0, 神が存在しない場合),(1, 神が存在する場合):}`

であるような， ただ一つの文字列 `s` のみを含む言語とする．`A` は判定可能か？なぜそうなのか，またはなぜそうでないのか？ （答えは読者の宗教的信念に依存しない．）

ここで、ある言語が判定可能とは、その言語を判定するチューリング機械が存在するときをいう。 私には答がわからないが、読者の宗教的信念に依存しない答というのがひっかかる。というのは、 宗教の定義がわからないのだ。宗教とは、神の存在を肯定することなのだろうか。

この問題はともかく、読んだ限りはしっかりと作られていて、計算の理論をしっかり学ぶ上ではいい本なのではないだろうか。

書誌情報

まりんきょ学問所 ＞ コンピュータの部屋 ＞ コンピュータの本 ＞ Michael Sipser：計算理論の基礎