Michael Sipser：計算理論の基礎

概要

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

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

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

感想

第 0 章があるのが面白い。

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

`A` を

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

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

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

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

p.29 の演習は次のとおりである。

0.9 以下のグラフの形式的な記述を書け．

ところが、この一文の下にあるのは、問題であり、このページにグラフが見当たらない。次のページを見ると次のグラフがあるのでこのことなのだろう。

この答は、たぶん次のようなものだと考えられる。

`({1,2,3,4,5,6}, {(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)})`

pp.29-30 の問題は次のとおりである。

0.10 以下に示す `2 = 1` の証明の誤りを指摘せよ．

等式 `a = b` を考える．両辺に `a` をかけて `a^2 = ab` を得る．両辺から `b^2` を引いて `a^2 - b^2 = ab - b^2` を得る． 両辺を因数分解すると `(a + b)(a - b) = b(a - b)` となり，両辺を `(a - b)` で割ると `a + b = b` を得る．最後に `a` と `b` = `1` に代入すると，`2 = 1` が得られた．

この答は、たぶん次のようなものだと考えられる。両辺を因数分解したあと、両辺を `(a - b)` で割っているが、もともと等式 `a = b` を考えているのだから、`(a - b) = 0` であり、 両辺を `0` で割ることはできないのに割っているという誤った式変形をしている。従って誤った結論が得られるのは当然である。

数式

数式は ASCIIMath を使っている。またグラフは SVG で描いている。

書誌情報

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