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

こつこつ。今日はPCP Post corespondence problem。これも字面をおっているだけではさっぱりわからない。メモをとりながら。

• PCPを定義する。
  
• PCP = {<P> | PはマッチをもつPost対応問題の入力例}
  
  
• 証明したいこと。
  
• PCPは判定不可能である。
  
  
• 証明の方針。
  
• 受理計算履歴を介したA[TM]からの帰着。
  
• 任意のTM Mと入力 w を用いて、マッチがMのwに対する受理計算履歴となるように、入力例Pを構成する。
  
• マッチがMとwに対する受理計算履歴となるようなP、というのが何を言っているのかわからないが、先に進む。
  
  
• 技術的な事前手当を3つ。これは今は理解できなくてもよいとのこと。
  
  
  
  • Mの変更。Mにはヘッドをテープの左端からはみ出させる動作はないようにする。
    
  • w = ε の場合、wの場所を空白文字にする。
    
  • マッチが最初のドミノ[t1/b1]から開始するように、PCPの定義を変更する。これをMPCPと呼ぶ。
    MPCP = {<P> | P は最初のドミノから始まる PCP ドミノの集り }
    
  
  
  
• 証明。
  
  
  
  • TM R がPCPを判定するとして、A[TM]を判定するSを、Rを使って構成する。構成できてしまったら、帰着により、Rは判定不可能と言える。
    
  • Sが入力対象とするMを定義する。
    M = (Q,Σ,Γ,δ,q[0],q[accept], q[reject])
    
  • Mがwを受理するとき、かつそのときに限り、SはマッチをもつようなPCPのドミノの集合Pを構成する。
    
  • 集合 Pの構成。
    
  • まず、MPCPの入力例 P' を構成する。
    
    
    
    
    • Part 1. 構成の開始方法。
      [#/#q0w1w2...wn#]
      を最初のドミノ[t1/b1]としてP'に加える。
      
    • ここで、q0w1w2...wnは受理計算状態履歴の開始状態C1である。
      
    • これはマッチしていない。上段をなんとかしないといけない。
      
    • そのために、ドミノを追加する。
      
      
    • Part 2.
      
    • 任意のa,b∈Γと任意のq,r∈Q、ただしq != qrejectにたいして、
      δ(q, a) = (r, b, R) ならば、[qa/br]をP'に加える。
      
      
    • Part 3.
      
    • 任意のa,b,c∈Γと任意のq,r∈Q、ただしq != qrejectにたいして、
      δ(q, a) = (r, b, L) ならば、[cqa/rbr]をP'に加える。
      
      
    • Part 4.
      
    • 任意のa∈Γに対して、
      [a/a] をP'に加える。
      
      
    • Part 5.
      [#/#]と[#/_#]をP'に追加する。( _ は空白文字)
      
      
      
    • Part 6.
      [a qaccept/qaccept] と [qaccept a/qaccept]をP'に追加する。
      
      
    • Part 7.
      [qaccept##/#]を追加して、マッチを完成させる。
      
      
    
    
  • ちょっとやってみる。
    

    
    step 1: part 1
    [ # / # q0 0 1 0 0 # ] 
    
    step 2: part 2
    δ(q0, 0) = (q7, 2, R)とする。
    [ # / # q0 0 1 0 0 # ] 
    [ q0 0 / 2 q7]
    
    結合して上下比較
    # q0 0
    # q0 0 1 0 0 #  2 q7
    
    step 3: part 4
    [ # / # q0 0 1 0 0 # ] 
    [ q0 0 / 2 q7]
    [ 1 / 1 ], [ 0 / 0 ], [ 0 / 0 ]
    
    結合して上下比較
    # q0 0 1 0 0
    # q0 0 1 0 0 # 2 q7 1 0 0
    
    step 4: part 5
    [ # / # q0 0 1 0 0 # ] 
    [ q0 0 / 2 q7]
    [ 1 / 1 ], [ 0 / 0 ], [ 0 / 0 ]
    [ # / # ], [ # / _ # ]
    
    結合して上下比較
    # q0 0 1 0 0 # #
    # q0 0 1 0 0 # 2 q7 1 0 0 # _ #
    
    step 5: part 2
    δ(q7, 1) = (q5, 0, R)とする。
    [ # / # q0 0 1 0 0 # ] 
    [ q0 0 / 2 q7]
    [ 1 / 1 ], [ 0 / 0 ], [ 0 / 0 ]
    [ # / # ], [ # / _ # ]
    [ q7 1 / 0 q5]
    
    結合して上下比較
    # q0 0 1 0 0 # q7 1 #
    # q0 0 1 0 0 # 2 q7 1 0 0 # 0 q5 _ #
    
    step 6: part 4
    [ # / # q0 0 1 0 0 # ] 
    [ q0 0 / 2 q7]
    [ 1 / 1 ], [ 0 / 0 ], [ 0 / 0 ]
    [ # / # ], [ # / _ # ]
    [ q7 1 / 0 q5]
    [ 2 / 2 ], [ 0 / 0 ], [ 0 / 0]
    
    結合して上下比較
    # q0 0 1 0 0 # 2 q7 1 0 0 #
    # q0 0 1 0 0 # 2 q7 1 0 0 # 2 0 q5 0 0 _ #
    
    step 7: part 5
    [ # / # q0 0 1 0 0 # ] 
    [ q0 0 / 2 q7]
    [ 1 / 1 ], [ 0 / 0 ], [ 0 / 0 ]
    [ # / # ], [ # / _ # ]
    [ q7 1 / 0 q5]
    [ 2 / 2 ], [ 0 / 0 ], [ 0 / 0]
    [ # / # ], [ # / _ # ]
    
    結合して上下比較
    # q0 0 1 0 0 # 2 q7 1 0 0 # # #
    # q0 0 1 0 0 # 2 q7 1 0 0 # 2 0 q5 0 0 _ # # _ #
    
    
    step 8: part 3
    δ(q5, 0) = (q9, 2, L)とする。
    [ # / # q0 0 1 0 0 # ] 
    [ q0 0 / 2 q7]
    [ 1 / 1 ], [ 0 / 0 ], [ 0 / 0 ]
    [ # / # ], [ # / _ # ]
    [ q7 1 / 0 q5]
    [ 2 / 2 ], [ 0 / 0 ], [ 0 / 0]
    [ # / # ], [ # / _ # ]
    [ 0 q5 0 / q9 0 2 ], [ 1 q5 0 / q9 1 2 ], [ 2 q5 0 / q9 2 2 ], [ _ q5 0 / q9 _ 2 ]
    
    
    結合して上下比較
    # q0 0 1 0 0 # 2 q7 1 0 0 # 0 q5 0# #
    # q0 0 1 0 0 # 2 q7 1 0 0 # 2 0 q5 0 0 # q9 0 2 _ # _ #
    
    保留：[ 1 q5 0 / q9 1 2 ], [ 2 q5 0 / q9 2 2 ], [ _ q5 0 / q9 _ 2 ]
    

    
    感じはつかめた。
    
  
  

こちらも最後ぐだぐだになったが、なんとなくわかった。
後日振りかえるとして先に進もう。次回は写像帰着性。