【シプサ】3 CHURCH-TURINGの提唱 (その4)

なんとなく、わかったような気がするのでまとめてみる。

• まず、Turing機械は、生成機構かつ認識機構であるということだ。これが有限オートマトンやプッシュダウンオートマトンとは違う。それらの生成機構は、正規表現や文脈自由文法という別のものだった。
  
• Turing機械が生成機構である、というのはTuring機械そのまんまで成立している、というのではなくて、Turing機械のrobustnessを経てのことではある。具体的には列挙装置(Enumerator)がそれにあたる。列挙装置はTuring機械と等価である。
  
• 列挙装置というものが、私がどうもしっくりこなかった部分にこたえてくれた。
  
• 例えば乗算を判定するTuring機械があれば、正しい乗算式を全て出力する列挙装置もつくれる。これは九九の表を出力するようなものである。
  
• また、i * jを入力として答のkを出力するような装置も考えられる。これはTuring機械と列挙装置を組み合わせて新しい装置をつくれば構成可能なことはかんたんにわかる。また、それらの組合せではなく新しい装置も考案できるが、それがTuring機械と能力として等価であるということは想像にかたくない。
  
• なので、計算について動的なイメージをもつか静的なイメージをもつかというのは計算の本質ではなくて、それは装置のあり様によってどちらにでも変換できるものであるということだろう。
  
• また、
  
  
  
  • 無限のメモリをもち
    
  • メモリの任意の位置の読み書きができて
    
  • 一つのステップで有限の作業量のみを実行する能力をもつ
    
  
  
• という条件をみたした機構(または装置)が判定できること、というのは、どうやら人間が自然言語で手順化して判定できることと等価であるようだ、いや、これと等価であると考えることは悪い選択肢じゃないのでそうしちゃわないか、というのがChurch-Turingの提唱なのだ。そもそも「人間が自然言語で手順化して判定できること」の定義なんて存在しなくて、直感的な理解だったんだから、定義しようとしたら、マシそうなものを選ぶしかないじゃないか、ということだろう。
  
• 生成機構としてのTuring機械の記述は、形式的記述、実装記述、高レベル記述がある。ここで高レベル記述は、Turing機械の詳細には触れず、その動作の本質と呼べるようなものを自然言語を使って記述する方式である。これが、日常的直感的なアルゴリズムに該当する。
  
• Cでアルゴリズムを勉強しているが、そこで何をしているかというと、高レベル記述のアルゴリズムを、(Turing機械ではなく)C言語での実装記述を実施するということだ。だからやはり、アルゴリズムの高レベル記述を理解する、ということは、それを理解した上で特定の機構(Turing機械やC言語など)で実装できる能力とは関係はしているが別ものなのだ。
  
• これらがなんとなくわかったこと。
  
  
• まだしっくりこないことは、
  
  
  
  • Turing機械のパワーは、生成機構かつ認識機構であるという、二面を集約した点にあると思う。しかし、それが様相としてどうなのかがわからない。
    
  • Turing機械の高レベル記述での「オブジェクトとその符号化」というところが、Common Lispのreaderとかと関係があるのかないのかがよくわからない。
    
  
  
• などなど。
  

こつこつ。