計算論をすこしずつ読んでるよ

計算論

やっとゲーデル関数のところまできたよ。

一昨日くらいに証明した演習問題を紹介。問題文はわかりやすいように改変してある。

Q1

G(x,y) = (1+2+\cdots+(x+y)) + y という関数があるとき、G(x,y)=G(s,t) \Leftrightarrow x=s \cap y=tを証明せよ。

Q2

G^m(x_1,x_2,\cdots ,x_{m-1})=G(G(\cdots G( G(x_1,x_2), x_3), \cdots x_{m-1}) と関数を定義したとき、[tex:G(G(\cdots G( G(x_1,x_2), x_3), \cdots x_{m-1})=G(G(\cdots G( G(y_1,y_2), y_3), \cdots y_{m-1}) \Leftrightarrow \forall i

このG^mが、長さmの数列のゲーデル関数になってる。