計算の話
- d:id:tri_iroに書いてある話を読んでいた.
- BBは (俺の中で) 計算不可能な関数の例でしかなかったので, 色々と蒙を啓かれた.
DFAを検査
と言ったときには二通りの解釈が出来る- 例の問題は後者で解くのではないでしょうか? > 先生
- 計算論に詳しい方に質問です。
チューリングマシンの判定可能問題を勉強していたのですが、
「EQ_CFG（文脈自由文法の等価性）は判定不可能」
という証明の仕方が分かりません。
「ALL_CFG（あるCFGの言語がΣ*であること）は判定不可能」
であることを利用すればそこに帰着させれば簡単に解けること、
ALL_CFGは、チューリングマシンのあらゆる計算過程を示す「計算履歴」と呼ばれる概念を用いれば証明可能であること、
あたりはWikipediaの文脈自由文法の欄を読んで理解しました。
しかし、チューリングマシンの計算履歴というのは何か、
そしてそれをどうすればALL_CFGの証明に生かせるのか
さっぱり分かりません。
どなたかご教授ください。
- G_{M,w}という文法の作り方がテクニカルですよね. 一部の計算履歴を逆向きに書くとか (丁度その辺りを読み直していた).
