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

こつこつ。今回は写像帰着可能性。

• 帰着させるという概念の細かな定義は、いくつかの流儀がある。
  
• ここでは写像帰着可能性というのをやる。
  
• おおざっぱにいうと、
  「写像帰着可能性を用いて問題Aを問題Bに帰着できるとは、問題Aへの入力例を問題Bへの入力例に変換する計算可能な関数が存在するということである」
  
  
  
  • なんとなく、わかるけど、ちょっと考えてみる。
    
  • 計算可能な関数が存在する、というのはTMで実施可能、ということ。
    
  • なので、問題Aへの入力例を問題Bへの入力例に変換できるTM hogeを構成できる、ということ。
    
  • 問題Aというのは、言語Aを判定できるかどうかということだとする。Bもしかり。
    
  • それは言語Aを判定するTM piyoを構成できるか、ということ。Bについては、そんなTM poyoを構成できるか、ということ。
    
  • TM hogeとTM poyoが存在するなら、この言明が成立するときは、TM piyoをTM hogeとTM poyoで構成できる。
    
  • よって、問題Bが解けるなら、問題Aも解けることになる。逆に問題Aが解けたって、問題Bが解けるとはいえない。
    
  • すなわち、問題Aより問題Bの方が難しいといえる。
    
  • 理解した。
    
  
  
  
• ついに「計算可能な関数」が出てきた。
  
• ここらへんがラムダ算法との接点なのかな?? ラムダ算法も学習したいなぁ。
  
• 余談だが、この章、ちょこちょこ誤植(誤訳?)があるな。
  
  
• こっから、結構タフな作業。この章のここまでの帰着に関する具体的な議論を、写像帰着性を用いて捉えなおす。こういう作業はタフ。だからこそ力になると考えて、進む。
  
• 定理5.1 HALT[TM]が判定不可能であること。
  
  
  
  • もともとの証明は?
    
    
    
    • TM R がHALT[TM]を判定すると仮定する。そして、A[TM]を判定する TM S を構成してみせた。ところで、A[TM]が判定不可能なのは直接確認済みなので、矛盾が生じている。ゆえにTM Rに関する仮定が間違っている。
      
    • さて、ここで「構成する」ところの詳細は?
      
    • TM Rの入力は、<M,w>であり、wに対してMが停止するなら受理し、しないなら拒否する。
      
    • TM Sの入力は、<M',w'>であり、wに対してM'が受理するなら樹脂し、しないなら拒否する。
      
    • Sの動作：Sは、<M', w'> を受け取る。それをRに入力する(SはRをシミュレートできる)。Rが拒否するなら拒否する。受理するなら、w'をM'に入力する(SはM'をシミュレートできる)。これは必ず停止するので、結果は受理または拒否である。それぞれ受理または拒否する。
      
    
    
  • これはわかる。これのどこが写像帰着なのか?
    
  • もしかしてこれは写像帰着ではないのか?
    
  • ああ、単純には写像帰着ではないようだ。入力の変換について明示していないから。
    
    
  • A[TM]からHALT[TM]への写像帰着を与える帰着(関数)f
    
    
    
    • 入力：<M,w>。
      
    • 出力：<M',w>。ただし「<M',w>∈HALT[TM]のとき、かつそのときに限り、<M,w>属するA[TM]」である。
      
    
    
  • fによって、A[TM] <=m HALT[TM]となる。
    
  • 判定可能な文字列を判定可能な文字列に変換する作業なことを、あらためて認識。
    
  • その変換する作業というか、そのための機構のなかに2つの言語の関係性が表われている。
    
  
  
  
• 定理 5.15 Postの対応問題
  
  
  
  • これはまさに写像帰着にて解いている
    
  
  
  
• 定理 5.4 E[TM]からEQ[TM]への帰着
  
  
  
  • う、この証明がどんなんだったかおもいだせない。
    
  • 見直してみる。
    
    
    
    • TM R はEQ[TM]を判定すると仮定する。E[TM]を判定するTM S を構成する。
      
    • TM S の構成。
      
      
      
      • TM S の入力を<M>とする。
        
      • M1をすべての入力を拒否するTMとする。
        
      • Rに、<M, M1>を入力する。
        
      • ああ、簡単じゃないか。
        
      
      
    • 私は、「E[TM]からEQ[TM]への帰着」が何をいっているかの方がわかっていないのだ。それがわかった上で、それの解法がわからないのではなくて。
      
    • 考える。
      
      
      
      • E[TM]からEQ[TM]への帰着。
        
        
      • まず問題の帰着として考える。
        
      • 問題E[TM]から問題EQ[TM]への帰着。
        
      • これは、ざっくり言って、問題E[TM]を解くことを、問題EQ[TM]を解くことにすりかえられるということ。
        
      • ということは、E[TM]はEQ[TM]より(ざっくりいうと)簡単である。
        
      • よって、EQ[TM]が判定可能なら、E[TM]も判定可能。
        
      • よって、E[TM]が判定不可能なら、EQ[TM]も判定不可能。
        
      • とするとE[TM]が判定不可能なことはここではアプリオリなので、EQ[TM]に帰着できれば、EQ[TM]も判定不可能である。
        
      • E[TM]を解くことを、EQ[TM]を解くことにすりかえられるか?
        
      • ああ、カリー化みたいな感じだ。E[TM](M) = EQ[TM](M1,M) (ただしM1はE[TM]なTM)
        
        
      • 次に言語の帰着として考える。
        
      • 言語E[TM]から言語EQ[TM]への帰着。
        
      • f : <M> -> <M1, M>
        
        
      • 多少、わかった気になれた。
        
      
      
    
    
  
  
• 定理 5.2 E[TM]は判定不可能である。
  
• これの証明もぼやっとしか覚えてない。
  
• 考える。
  
  
  
  • 判定不可能をしめしたいのだから、判定不可能だとわかっているものからE[TM]に帰着させる。
    
  • そこで、問題A[TM]から問題E[TM]に帰着させる。
    
  • これは、問題A[TM]を解くことを問題E[TM]を解くことにすりかえるということ。
    
  • そのためには、A[TM]を解くTM S を E[TM]を使って構成できればよい。
    
  • A[TM]への入力を<M,w>とする。
    
  • A[TM]の受理or拒否が、E[TM]の受理or拒否と一対一対応されていればよい。
    
  • で、E[TM]は空性検査、であると。
    
  • <M,w>にしたがって、<M'>をつくってそれを空性検査にかけるんだろうな。
    
  • で、M'が認識可能な言語は空か非空なのだが、それがA[TM]の受理or拒否に対応している、と。
    
  • なんとなく、受理->非空 (L(M') = {w})、 拒否->空、と算段する。
    
  • M'をつくる。材料は、とあるTM Mと、とある入力 w。そしてE[TM]なTM Rをどうつかうか。
    
    
    
    • M'の入力をw'とする。
      
    • w' != w なら拒否する。
      
    • w' = wならMをwで動作させる。Mが受理するなら、受理する。(ループと拒否は考えない)
      
    
    
  • <M'>でRを動作させればOK。
    
  • 少し、わかった気になった。
    
  
  
• えっとこの証明では、<M,w>から<M'>に写像した。
  
• ここで、
  (Rが<M'>を拒否 = M'の認識する言語が非空) -> (<M,w>を受理)
  (Rが<M'>を受理 = M'の認識する言語が空) -> (<M,w>を拒否)
  である。
  
• なので先の写像は、E[TM]への写像ではなく、E[TM]の補集合への写像である。
  

最後はぐだぐだになったが、帰着可能性をなんとか読んだ。次は演習。
今日はシプサでいっぱいいっぱい。
こつこつ。