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

こつこつ。

• ALL[CFG] = {<G> | GはCFGであり、L(G) = Σ*}
  
• 「ALL[CFG]は判定不可能である」
  
  
  
  • 方針：ALL[CFG]が判定可能と仮定し、その仮定を用いてA[TM]が判定可能であることを示す。
    
  • 方針：証明は計算履歴を介したA[TM]からの帰着である。
    
  
  
• 自分なりに組み立ててみる。
  
  
  
  • TM M と入力 w について、CFG G を構成する。
    
  • GはMがwを受理しないとき、全ての文字列を生成する。
    
  • GはMがwを受理するとき、Gはひとつの文字列を生成しない。それは、Mのwに対する受理計算履歴である。
    
    
  • さて、CFG GのかわりにPDA Dを構成することにする。
    
  • Dは非決定的な分岐をもつ。分岐は次のとおり。
    
    
    
    • 計算状態の列として所定の形式をみたしているか? 満足しないなら受理。
      
    • 先頭の計算状態が開始状態であるか? 開始状態でないなら受理。
      
    • 末端の計算状態が受理状態であるか? 受理状態でないなら受理。
      
    • CiからCi+1が遷移関数による関係になっているか? なっていないなら受理。
      
    
    
  • こうすると、Dは受理計算履歴以外のすべての文字列を受理する。
    
  • よって、
    
  • Mがwを受理するならば、Dは受理しない文字列がひとつだけ存在する言語である。
    
  • Mがwを受理しないならば、Dはあらゆる文字列を受理する。
    
  • あとは自明。
    
  
  

このあたり、あまり面白みがないような気がする。「写像帰着可能性」は面白そうなので、期待する。
次回は「単純な判定不可能問題」。こつこつ。