【シプサ】5 帰着可能性 (その7)

今日から演習開始。

• 「5.1 EQ[CFG]が判定不可能であることを示せ」
  
  
  
  • 調査：A[CFG]とE[CFG]は判定可能。ALL[CFG]は判定不可能。計算履歴を用いた帰着で確認している。
    
  • 方針：EQ[CFG]とALL[CFG]との帰着にて示す。EQ[CFG]を判定可能であると仮定して、ALL[CFG]が判定可能になってしまうことを示す。
    
  • 証明：
    
    
    
    • ALL[CFG] = {<G> | GはCFGであり、L(G)=Σ*}
      
    • EQ[CFG] = {<G1,G2> | G1とC2はCFGであり、L(G1) = L(G2)}
      
    • そっか、Gを与えられたときそのPDAのΣに対して、Σ*を受理するCFG(or PDA)を構成できればいいんだ。
      
    • Σ自体は有限集合であり、正規言語。正規言語のクラスはスター演算に関して閉じているからΣ*も正規言語。
      
    • Σを生成するCFGは、一定の手順で構成できる。そのCFGからΣ*を認識するCFGも一定の手順で構成できる(演習2.16)。
      
      
    • さて、TMを記述してみる。
      
      
      
      • EQ[CFG]を判定するTM Mがあると仮定する。
        
      • TM Sを構成する。
        
      • Sの入力は<G>とする。
        
      • 動作を構成する。
        
        
        
        • <G>から等価なPDAを計算してΣを明確にする。(終端記号のピックアップで事足りるかも?)
          
        • Σを生成するCFGを構成し、それをもとにΣ*を構成するCFG G'を構成する。
          
        • Mに<G', G>を入力する。
          
        • Mが受理すれば受理し、拒否すれば拒否する。
          
        
        
      
      
    • これはALL[CFG]を判定するTMである。
      
    • ALL[CFG]は判定不可能だから矛盾が生じている。ゆえに仮定が間違っており、EQ[CFG]は判定不可能である。■
      
    
    
  
  
  
• 「5.2 EQ[CFG]が補Turing認識可能であることを示せ」
  
  
  
  • 調査：
    
    
    
    • 補Turing認識可能って何だっけ? 調べる。「Turing認識可能な言語の補集合」だ。
      
    • うお。そうすると、EQ[CFG]の補集合はTuring認識可能、ということか。ちなみにそうすると、EQ[CFG]はTuring認識可能ですらないんだ。。。
      
    • 系5.29によると「A <=m Bのとき、AがTuring認識不可能ならBもTuring認識不可能」である。写像帰着の定義によると「A <=m B ならば、Aの補集合 <=m Bの補集合」なので、「Aの補集合 <=m Bの補集合のとき、Aの補集合がTuring認識不可能ならBの補集合もTuring認識不可能」となる。ここで、AをA[TM]、BをEQ[CFG]とすると、「A[TM]の補集合 <=m EQ[CFG]の補集合のとき、A[TM]の補集合がTuring認識不可能ならEQ[CFG]の補集合もTuring認識不可能」となる。あれ? これじゃだめじゃん。
      
    • 単純に、 EQ[CFG]の補集合 <=m A[TM] を示せばいいんだ。EQ[CFG] <=m A[TM]の補集合 という手もある。どちらにするか。 前者の方が簡単そうだ。
      
    
    
  • 方針：EQ[CFG]の補集合 <=m A[TM] を示す。
    
  • 証明：
    
    
    
    • EQ[CFG]の補集合の受理入力：<G1,G2> G1とG2は受理する言語が違う。
      
    • A[TM]の受理入力：<M,w>で、TM M は 入力wを受理する。
      
    • む、wの扱いが難しい。
      
    • あと、CFGとTM、というように言語クラスが違うところをどうするか。。。
      
      
    • EQ[CFG]が認識不可能であることは示せそうなんだけど。これだと逆にできる。やってみる。
      
    • すなわち、A[TM]の補集合 <=m EQ[CFG] を示せばよい。
      
      
    • A[TM]の補集合の受理入力：<M,w&tで、TM M は 入力wを受理しない。
      
    • EQ[CFG]の受理入力：<G1,G2> G1とG2は受理する言語が同じ。
      
    • M,wからG1,G2を構成できるか?
      
    • 二つのPDA D1とD2を構成する。
      
    • D1は全ての入力を拒否する。
      
    • D2は全ての入力に対して、wでMを動作させる。拒否したら拒否、受理したら受理する。
      
    • <D1,D2>を出力。
      
    • 帰着関数ができた。
      
      
    • よって、EQ[CFG]は認識不可能。帰着関係は、A[TM]の補集合 <=m EQ[CFG]。
      
    • あ、この帰着関係は使える? 補集合は、A[TM] <=m EQ[CFG]の補集合。だめだやはり使えない。
      
    • 。。。
      
    
    
  
  

ダメダメ。一旦頭を冷やす。