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

そのn、のnが二桁になったのはこれがはじめてかも。
体調が再度悪化しているけど、なんとか、こつこつ。

• 「5.5 A[TM]はE[TM]に写像帰着可能でないことを示せ。すなわち、A[TM]をE[TM]に帰着する計算可能な関数が存在しないことを示せ。」
  
  
  
  
  • まずA[TM]とE[TM]について、わかっていることを整理。
    
    
    
    
    • A[TM]は、判定不可能、認識可能。
      
    • E[TM]は、判定不可能。認識可能性は不明。
      
    • E[TM]が判定不可能であることは、帰着を用いて、A[TM]の判定不可能性から導いた。
      
    
    
    
  • とりあえず、この3つめが関係ありそう。これを考えてみる。
    
    
    
    
    • 導くにあたって、E[TM]が判定可能であるとすると、A[TM]が判定可能であるTMを構成できてしまうということで、背理法を使った。
      
    • ということは、帰着としては、A[TM]をE[TM]に帰着させている、ということ。
      
    • するとこの演習がフォーカスしているのは、やはり「写像」帰着が不可能ということ。帰着はできる、と。
      
    • その帰着の様を確認してみる。
      
      
      
      
      • A[TM]を判定するTM Sを構成する。
        
      • E[TM]を判定するTM Rが存在すると仮定する。
        
      • TM Sの入力は、<M,w>である。
        
      • まず、TM M1を、TM Mとwをつかって構成する。
        
      • M1 = 「入力xに対して、x != wなら拒否。x = wならば、wに対してMを動作させ、Mが受理するなら、受理する。」
        
      • つぎに、TM Sを、RとM1を使って構成する。
        
      • S = 「入力<M,w>に対して、1. TM M1を構成して、2. Rを入力<M1>にて動作させ、3. Rが受理するなら拒否し、拒否するなら受理する」
        
      
      
      
    • これは確かに、A[TM]という問題をE[TM]という問題に帰着させている。
      
    • さて、まず、この帰着をA[TM]からE[TM]への写像帰着にできるかどうか。
      
    • ああ、それが、違いますよ、っていうのがP.248の説明だ。
      
    • A[TM]からE[TM]への写像帰着ではなく、A[TM]から「E[TM]への補集合」への写像帰着になっている、と。
      
    • なんで、補集合への写像帰着でいいんだっけ？
      
    • ああ、そうか、集合と補集合の境界を判定できるか、というのが言語の判定可能性であり、それは境界に関することだからだ。それを集合と補集合のどちらの観点から言及しているか、というだけだから。
      
      
    • ああ、だいぶ彼らのことがわかってきた。
      
      
    • すると、A[TM]から「E[TM]の補集合」へは写像帰着可能ということが事実としてわかった。
      
    • とすると、「E[TM]の補集合」が認識不可能だとすると、A[TM]も認識不可能となってしまう。
      
    • A[TM]は認識可能なので、これは矛盾。よって、「E[TM]の補集合」は認識可能である。
      
    • すると、E[TM]は判定不可能だから、E[TM]は認識不可能であることがわかる。
      
      
    • A[TM]からE[TM]への帰着写像が存在するとする。
      
    • すると、E[TM]が認識不可能であるから、A[TM]も認識不可能ということになる。
      
    • これはA[TM]が認識可能という事実に反する。ゆえに仮定が間違っている。■
      
      
    • 正解かな？ と答を見てみる。
      
    • 解答は、はるかに簡単かつスマートに証明しているが、捉えているポイントは同じだ。よかった。
      
    
    
    
  
  
  

早く体調を戻さねば。