【シプサ】4 判定可能性 (その3)

シプサを勉強しようとすると、実は恐怖心を感じる。疲れていて頭がうごかないんじゃないか、とか。疲れた頭でやっても無意味なんじゃないか、とか。でもちょっとずつでも進まなければ、終わらないというジレンマがある。もう少しおおらかにとりくむにはどうしたらいいか。

疲れているなぁ、というときは、前回勉強したところの本文を復唱する、というのはどうか。一度やったところだから、恐怖心はない。そして、その部分は記憶に残る度合いが大きくなる。そうすれば、新しいところに入る敷居は少しづつ低くなっていくかもしれない。そうすると新しいところに入れるチャンスは増える。今後はこの方式でいってみよう。

• 前回の本文と自分のメモを見返してから「文脈自由言語に関連する判定可能問題」を開始。
  
• 定理4.7で、CFGが特定の文字列を生成するかどうかが判定可能であることがわかった。
  
• CFGについては、PDAとからめつつ、以前すでに調べている。
  
• ここであらためてTMでとりあつかって、判定可能とわかったというのはどういうことか。なぜそんな確認をするのか。
  
• というのは、C言語とかでCFGを取り扱おうと思ったら、CFGやPDAをやったところの知識だけでもできるはずだ。
  
• おそらく、C言語で取り扱うかわりに、TMで取り扱っているのだ。
  
• というは、TMはアルゴリズムの定義にでてくる人だからだ。
  
• よって、文脈自由言語を扱うアルゴリズムの特徴をしらべたい、というときには、C言語よりもTMのほうがいい、ということなのだ。
  
• で、実際にTMで扱ってみて、それが判定可能という事実がわかったということだ。
  
• おそらく、TM以外にもいくつかこういうものがあるのだろう。λ算法とか。
  
  
• 4.2 停止問題
  
• そうか、万能Turing機械は、プログラム格納型(内蔵型)計算機のモデルというかなんというか、なんだ。
  
• おお！Cantorだ。これで集合への30講を事前にやっといたことが役に立つ！
  
• なんとなくの直感なのだが、重要な性質というか内在する特質というのはメタな状況から生まれる、ような気がする。
  
• 停止問題、おもしろそうなのだが、メタ度が高い。。。
  
• 雰囲気だけおさえた。次回気合をいれて読み解く。
  

こつこつ。