計算論が難解な圏^H件について

計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)
高橋 正子

以前のエントリに書いたとおり、ちょこちょこ計算論を読んでます。

でも集合論をちゃんと勉強したことのない長月には難解です。

本当にゆっくりゆっくりと理解しながら進むことにします。今まで一度読んでわかった気になって薄っぺらなままきているので、ここで一回ちゃんと数学的な基盤を自分の中に作っておくべきだと思いました。

ので、ちゃんと読んでちゃんと考えて、考えた事はメモして行こうと思います。

とりあえず初メモ。

例1.3.2.に出てくる1変数関数pred(x)＝xー1について。

定義)
pred(0)＝0＝zero(),
pred(x＋1)＝x＝p²₁(x, pred(x))

理解のために手で展開してみる。

pred(0)＝0

pred(1)＝pred(0＋1)
          ＝p²₁(0, pred(0))
          ＝p²₁(0, 0)
          ＝0

pred(2)＝pred(1＋1)
          ＝p²₁(1, pred(1))
          ＝p²₁(1, pred(0＋1))
          ＝p²₁(1, p²₁(0, pred(0)))
          ＝p²₁(1, p²₁(0, 0))
          ＝p²₁(1, 0)
          ＝1

pred(3)＝pred(2＋1)
          ＝p²₁(2, pred(2))
          ＝p²₁(2, pred(1＋1))
          ＝p²₁(2, p²₁(1, pred(1)))
          ＝p²₁(2, p²₁(1, pred(0＋1)))
          ＝p²₁(2, p²₁(1, p²₁(0, 0)))
          ＝p²₁(2, p²₁(1, 0))
          ＝p²₁(2, 1)
          ＝2

超納得いった。手をうごかすの大事ですね。

あとblogとかで数式書くのめんどくせえ。誰かWLW用にTeXプラグインとか作ってくだしあ。