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

こつこつ。演習5.8。

• ちょっと手を動かして考えたら、なんもかんもわかった。
  
• そもそもPCPのお題を理解していなかったのだ。
  
• PCPのお題は、ドミノのある意味クラスがあたえられて、それから任意個のオブジェクトとしてのドミノを使ってマッチがつくれますか、ということだったのだ。クラスは全部使わなくてもよいし、ひとつのクラスからたくさんオブジェクトを作ってもよい。どう誤解していたかというと、与えらているのがクラスではなく複製不能なオブジェクトであると思っていたのだ。
  
  
• まず、これでPCPの判定不可能性を理解しようとしたときにもやもやしてたことが解消した。
  
• 次に、演習5.3 のマッチを探す問題の意図がわかった。私のような阿呆がこのように誤解することに対するセーフティネットだったのだ。見事に突き破ってしまったが。。。
  
  
• で、演習5.8。PCPがわかってしまえば造作もない。
  
• Part 2.で追加するドミノに、それが左端だった場合のものを足せばいいのだ。
  
• すなわち、Part 2.の条件化において、ドミノ[qa/rb]を足せばよい。もしそれが本当に左端だった場合は、マッチにこのドミノを使えばよい。
  
  
• 演習5.6〜5.8の解答を見てみる。証明の記述において違いはあるが、まあ正解だった。
  
• ただ、5.8の解答に「右」という単語があるが、どう考えてもこれは全部「左」の誤植/誤訳だろう。
  
• 念のため原著を確認した。"leftmost"、"move left"だった。
  
  
• 演習5.3 再度
  
• マッチあり。{[aa/a], [aa/a], [b/a],[ab/abab]}でいける。
  

おお、これにて帰着可能性が終わった。
えらい時間がかかった。次の6章は、

• 先進的な話題への入口
  
• 第三巻を読むのに必須ではない。
  

とのことなので、内容次第で、楽しめるところは深掘りして、現在興味がないところは軽く流そうと思う。
ああ、シプサが進むと嬉しい。