チューリングマシンの判定可能問題を勉強していたのですが、
「EQ_CFG（文脈自由文法の等価性）は判定不可能」
という証明の仕方が分かりません。
「ALL_CFG（あるCFGの言語がΣ*であること）は判定不可能」
であることを利用すればそこに帰着させれば簡単に解けること、
ALL_CFGは、チューリングマシンのあらゆる計算過程を示す「計算履歴」と呼ばれる概念を用いれば証明可能であること、
あたりはWikipediaの文脈自由文法の欄を読んで理解しました。
しかし、チューリングマシンの計算履歴というのは何か、
そしてそれをどうすればALL_CFGの証明に生かせるのか
さっぱり分かりません。
どなたかご教授ください。
No.1
33
11
100pt
この本に詳細があります．自分の手元にある英語版からかいつまむと（蛇足ですが英語は第二版が出ているはず），
これは文字通り，スタートからある時点までの計算の履歴です．まずwqauのような列（qは状態，w,uはΣ*の元, aはΣの元）をconfigurationと呼びます．これは，チューリングマシンの状態がqで，aを読んでいる状態を表します．configurationの有限列を「計算履歴」と呼びます．特にconfigurationの有限列C_1, C_2,..,C_kで
であるものをwに対する受理履歴と呼びます．
たとえば．q_1を開始状態で入力がabcだったとしたら，q_1abcから始まって，遷移関数がT(q_1,a)=q_2だったら，次はaq_2bcとなります（これが「正しい遷移」の意味です）．最終的に終了状態q'に対してabcq'となっている履歴がabcに対する受理履歴となります．
一言で言うと「計算履歴は適当なアルファベット上の語である」ことを利用する，ということになります．上の例を続けると，上で挙げた履歴は
のような語と見なせます（#は区切りのための文字）．
より具体的にはA_TM={<M,w>| チューリングマシンMは入力wを受理する}（＝決定不能）をALL_CFGに帰着させます．
チューリングマシンMと語wが与えられたときに，「Mのwに対する受理履歴ではない文字列すべて」を生成する文脈自由文法G_{M,w}をつくれることを示します．Mがwを受理しなければG_{M,w}の言語はΣ*となるので，<M,w>がA_TMの元かどうかを判定するには
ことになります．
久しぶりにざっと眺めただけなので穴があるかもしれませんが，だいたいこんなところでしょうか．
14
14
2
1
1
なるほど、計算履歴とはそういうものだったのですか。
「G_{M,w}をつくって」のくだりがどうすればいいのか
よく分かりませんでしたが、回答にあった「計算理論の基礎」を読んで
理解することができました。
詳しい解説本当にありがとうございました。