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

昨日は漢字変換がおかしくなって難儀した。例えば、「癒着」とかも変換してくれなくて、だけど全部が全部変換してくれないわけではなくて、おかしな状態だった。AquaSKKが原因なのかなと、OSXを再起動したら、ましになった。でも、なんだかまだ変な感じ。辞書が壊れているのかな?
さて、こつこつ。

• 「5.6 <=m がすいい関係をみたすことを示せ」
  
  
  
  • ああ、すいいが変換できなくなっている。。。とりあえず、しゅうりは後まわしにして進む。ああ、しゅうり、が変換できない。なんだかアルジャーノンのように、使える漢字がじょじょに動的にげんしょうしているような気がする。
    
    
    
    • だめだ。SKKがまともにうごかないと、書きながら思考、というのができない。。。
      
    • 調べる。。。。
      
    • 判った。なんと主辞書ファイルが途中でぶったぎれてた。こんなこともあるんだな。
      
    • SKK-JISYO.Lをダウンロードしなおして、skkを再起動。直った。
      
    • これでキリアン先生に愛してもらえる。
      
    
    
  
  
  
  
  • 推移関係とは、「あらゆるx,y,zについて、xRyかつyRzならばxRz」ということであった。
    
  • 写像帰着の正式な定義は、
    「計算可能な関数f:Σ*->Σ*が、任意のwに対して、
    w∈A <=> f(w)∈B
    をみたす」
    であった。
    
  • いま、言語A,B,Cがあり、A <=m BかつB <= Cであるとする。
    
  • ここで計算可能な関数f,gがあり、任意のwに対して、
    w∈A <=> f(w)∈B かつ w∈B <=> g(w)∈C
    である。
    
  • すると
    w∈A <=> g(f(w))∈C
    である。
    
  • ここでg・fは計算可能である。なぜならgのTMとfのTMを連結すれば構成できるから。■
    
  
  
  
• 「5.7 AがTuring認識可能であり A <=m 「Aの補集合」ならば、Aが判定可能であることを示せ」
  
  
  
  • ある言語が、自分の補集合に写像帰着可能ってどういう感じなんだろ?
    
  • 写像帰着関係(の定義)は補集合演算に関して透過的だから、これは同時に、「Aの補集合」 <=m A でもある。
    
  • そうか、その写像によって、Aのものは必ずAの補集合に写されるし、逆もなりたつのだ。総入れ替え、みたいな状況なんだな。
    
    
  • さて、証明自体は簡単で、「Aの補集合」 <=m A から「Aの補集合」もTuring認識可能ということがわかる。自身と補集合が認識可能だから、Aは判定可能である。■
    
  
  
  
• 「5.8 定理 5.15の証明で、Turing機械を変形してヘッドが左端からはみ出さないようにした。この変形をMに対して行わなかったとする。このケースを扱うために、PCPの構成を変更せよ」
  
  
  
  • う、PCPのところ、ぐだぐだになっていたので、問題文が何を言っているのかすらわからない。
    
  • 気分転換に例解UNIXをやってからにしよう。