【シプサ】6 計算可能性の理論における先進的な話題 (その5)

もう一歩、進めるだろうか。

• 6.3 TURING REDUCIBILITY
  
  
• connote: ...を暗示する。...を伴う。...を内包する。
  
• この、oracleの超越機械的な考え方、めちゃくちゃおもしろい。
  
  
• EXAMPLE 6.19を丁寧に理解する。
  
  
  
  • A[TM]のoracleがあるとする。
    
  • それを内包したoracle Turing machineをM^(A[TM])と呼ぶ。
    
  • このM^(A[TM])は通常のTMとくらべると、はるかに強力な判定能力をもっている。
    
  • 例として、E[TM]を判定できることを示す。
    
  • M^(A[TM])を使って、E[TM]を判定する手順を構成する。
    
  • その手順。
    
    
    
    • 入力はTMの表現<M>とする。
      
    • 1. 次のようなTM Nを構築する。
      
      
      
      • 入力は無視する。
        
      • 1. TM M を 全てのw∈Σ* について並列動作させる。(いいのか、こんな設計???)
        
      • 2. 1がいずれかについて受理になるならば、受理する。
        
      
      
    • 2. M^(A[TM])に<N,0>を入力する。すなわち、<N,0>∈A[TM]かどうかを調べる。
      
    • 3. 2の結果が拒否なら、受理する。受理なら、拒否する。
      
    
    
  • さて、この手順にでてくるTM Mが認識する言語が空集合でないならば、Nは<M>を受理する。ゆえに、Nはどんな入力でも受理となるのでもちろん0も受理する。ゆえに、<N,0>∈A[TM]であるから、この手順自体の結果は拒否となる。空集合であるケースも同様の分析で受理となることがわかる。
    
  • よって、この手順は、E[TM]を判定する手順である。
    
  
  
  
• THEOREM 6.21
  A <=T B かつ Bが判定可能ならば、Aも判定可能である。
  
  
  
  • A <=T B ということは、「Aは、Bに相対的には判定可能」ということである。
    
  • すなわち、Bのoracleを用いてAのoracle TMが作れるということだ。
    
  • Bが判定可能ということは、BのoracleはたかだかTMで実現できるものであるということ。
    
  • Aのoracle TMが内包するoracleもたかだかTMであり、すなわちAを判定する通常のTMが存在することになる。■
    
  
  
  
• Turing帰着性は写像帰着性を一般化したものである。
  
  
  
  • 写像帰着性では、計算可能な関数によって、言語間の要素を写像した。
    
  • A <=m B のとき、写像帰着関数は、Aの要素をBの要素に写像し、Aの要素でないものをBの要素でないものに写像した。
    
  • これによって、Aの要素を判定するということが、Bの要素を判定するということの部分問題になるというのが本質であった。
    
  • これはBが判定可能であるならば、Turing帰着性におけるoracleをBが担っているということである。
    
  • 写像帰着関数は、Aからそのoracleを利用するための手順を示していることになる。
    
  
  

進めた。よかった。