【シプサ】5 帰着可能性

毎日、ちょこちょこ読んで慣れを進めてきた。そろそろいけるかな???

• 「Turing機械で解決可能な問題のいくつかの例を示して」
  
  
  
  • これ、なんだっけ?
    
  • おそらく、「問題を言語で表現できて、その言語を判定するためのTuring機械を構成できる」ということだろう。
    
  • そして、「判定可能なアルゴリズムが存在する」ということだろう。
    
  
  
• 「計算的に解決不可能な問題の一例としてA[TM]を与えた」
  
  
  
  • これ、なんだっけ、、、
    
  • A[TM]って何だっけ。
    
  • A[TM]は、言語だ。
    
  • A[TM]={<M,w>|MはTMであり、Mはwを受理する}
    
  • ああ、ここでは「問題の一例としてA[TM]を与えた」と略記しているが、よりくわしくは、「問題の一例として"A[TM]が判定可能かどうか"というものを与えた」ということかな。
    
  • で、これは対角線論法をつかって、判定不可能であることを確認したのだった。
    
  • 結果、ある入力wについて、すべてのTuring機械において受理か拒否かを判定するようなスーパーなアルゴリズムは原理的に存在しない、ということがわかったのだった。
    
  • その肝は、停止するかどうかの判定が不可能なことにあった。
    
  
  
• 辞書をひくと、帰着の訳にreduceは無いし、reduce (reduction)の訳に帰着は無い。reduceには、減る|小さくなるというニュアンスがあるが、帰着にはないようだ。まあ、いいや。
  
• ここで言う帰着(reduce)というのは、おそらく、判定可能性の観点にて、複数の問題を関連づけられる、ということかな。
  
• で、「AをBに帰着できる」とは「Bが判定可能なら、Aも判定可能」ということ。よってAがBより難しいということはないから、「Aが判定不可能なら、Bも判定不可能」となる。
  
• 「問題が判定不可能であることを証明するために我々がとる方法は、すでに判定不可能であることが知られている他のある問題を、その問題に帰着できることを示すことである。」
  
  
  
  • これっていわゆる証明問題をとくというときにやってることだよね。
    
  • あと、数学の中での論理の展開ってすべてこういうことではないか。
    
  
  
  
• 5.1 言語理論における判定不可能問題
  
• ある「言語」のことを、「その言語が判定可能かどうかという問題」と同一視する記述が散見される。そういう慣習なのかな。
  
• 停止問題：HALT[TM] = {<M, w> | MはTMであり、Mは入力wに対して停止する}
  
• とか。
  
• 「HALT[TM]は判定不可能である」
  
  
  
  • HALT[TM]を判定するTM Rが存在する、とする。
    
  • すると、A[TM]を判定するTM Sを、TM Rを用いて構成できる。
    
  • これは、「A[TM]がHALT[TM]に帰着できる」ということだろう。
    
  • すなわち、HALT[TM]が判定可能ならA[TM]も判定可能ということ。別の言葉でいうと、A[TM]がHALT[TM]よりも難しいということはなく、「A[TM]が判定不可能なら、HALT[TM]も判定不可能」ということ。
    
  • ところで、A[TM]は判定不可能であった。よってHALT[TM]も判定不可能。
    
  • これは、いままでの証明の言い方では「背理法」を使ったということである。
    
  • そうか、逆に言うと、背理法を整備したのが帰着可能性ということかも。
    
  
  
  
• E[TM] = {<M>|MはTMであり、L(M)=空集合}
  
• 「E[TM]は判定不可能である」
  
  
  
  • E[TM]って何だ? そうか、「どんな入力文字列であっても拒否するTMの表現の集合」だ。
    
  • で、E[TM]とA[TM]は関係している。E[TM]用のTM RをつかってA[TM]用のTM Sを構成できるからだ。このことはちょっと工夫するだけ。割愛。
    
  • 帰着の論理からE[TM]は判定不可能となる。
    
  
  
  
• REGULAR[TM] = {<M>|MはTMであり、L(M)は正規言語}
  
• 「REGULAR[TM]は判定不可能である」
  
  
  
  • M,wに対して、Mがwを受理するときのみ正規言語を認識するTM M2をMをつかってつくれればよい。
    
  • M2にて、Σ={0,1}とする。
    
  • M2は入力文字列が(0^n)(1^n)のときは受理する。
    
  • M2は入力文字列が前項の形式以外のときは、"Mを入力wに対して動かして、Mがwを受理する"ならば、全部受理する。
    
  • すると、Mがwを受理するときは、(0^n)(1^n)含めて、M2はなんでもかんでも受理する。すなわちΣ*を受理する。これは正規言語である。
    
  • そして、Mがwを受理しないときは、(0^n)(1^n)しかM2が受理しないので、非正規言語に落ち込んでしまう。
    
  • この<M2>をRにかければ、M2が正規か非正規が判定できる。
    
  • それはMがwに受理するかが判定できるということ。
    
  
  
  
• Riceの定理： Turing機械によって認識される言語の任意の性質の検査は判定不可能である。
  
• なるほど。直感的には分かる。
  
  
• EQ[TM] = {<M1, M2>|M1とM2はTMであり、L(M1)=L(M2)}
  
• 「EQ[TM]は判定不可能である。」
  
  
  
  • これは簡単。
    
  
  

あせらず、とりあえずここまで。次回は、計算履歴を用いた帰着から。こつこつ。