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

こつこつ。

• 正規言語に関する判定可能問題、をみていく。
  
• 前回、導入部を丁寧に確認しておいたので、とくにひっかかりなく読み進められる。
  
• ここにきて、一巻でオートマトンの各種性質を証明するときに、構成してみせる方法をとっていたことの価値がよくわかる。シプサ先生ありがとう！
  
• 構成してみせる、ということは、構成する手順をしめすということであり、それはアルゴリズム的であり、現にそれはTMで構成可能なアルゴリズムなのだ。だから、それらの言語について見てきたことが、ここですべてTM上のアルゴリズムの話に透過的に(自動的に?)写しかえられるのだ。で、それがTMからみて判定可能な言語をなすかどうか(それが判定可能な計算問題かどうか)が議論できる、と。
  

次回は、文脈自由言語に関連する判定可能問題。