ウォンツテック

そでやまのーと

■

計算論

計算機科学の数学的背景に興味があるので以下の本を購入。

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

近代科学社 1991-08
売り上げランキング : 135427

Amazonで詳しく見る by G-Tools

とりあえず問をちょこちょこやっていく形で進めて行こうかと。
※全部やると全く進まないので気が向いたもののみ

原始帰納的関数

以下(1),(2),(3)で定義される関数を原始帰納的関数とよぶ。

(1) 
零関数： zero:N^{0} \to N ※ zero() = 0
後者関数： suc:N \to N ※suc(x) = x + 1
射影関数： p_{i}^{n}：N^{n} \to N　※p_{i}^{n}(x_{1}, x_{2},\cdots, x{n}) = x_{i}, 1 \leq i \leq n
(2)
g: N^m \to N
と
g_j:N^n \to N (j=1,2,\cdots,m)
が原始的関数のとき
f(\vec{x}) = g(g_1(\vec{x}), g_2(\vec{x}),\cdots,g_m(\vec{x}))
で定義される関数f:N^{n+1} \to Nは原始的関数である。
(3)
g: N^n \to Nh:N^{n+2} \to N
が原始的関数のとき
f(\vec{x}, 0) = g(\vec{x})
f(\vec{x}, y+1) = h(\vec{x}, y, f(\vec{x}, y))
で定義される関数f:N^{n+1} \to Nは原始的関数である

問 1.3.3 - 1

問題
g:N^m \to N
g_j:N^{n_j} \to N (j = 1,2,\cdots,m)
が原始的関数で
\left\{y_{11},y_{12},\cdots,y_{1n_1},\cdots,y_{m1},y_{m2},\cdots,y_{mn_m}\right\} \subseteq \left\{x_1,x_2,\cdots,x_n\right\}
のとき
f(x_1,x_2,\cdots,x_n) = g(g_1(y_{11},y_{12},\cdots,y_{1n_1}), \cdots, g_m(y_{m1}, y_{m2}, \cdots,y_{mn_m}))
で定義される関数f:N^n \to Nは原始的関数である。
証明
\left\{y_{11},y_{12},\cdots,y_{1n_1},\cdots,y_{m1},y_{m2},\cdots,y_{mn_m}\right\} \subseteq \left\{x_1,x_2,\cdots,x_n\right\}
より1 \leq k \leq mを満たす任意のkにて
\left\{ y_{k1},y_{k2},\cdots,y_{kn_k} \right\} \subseteq \left\{x_1,x_2,\cdots,x_n\right\}
が成り立つ. (上記左辺は条件の左辺の部分集合である事は自明）
これより1 \leq \alpha \leq n_kなる\alphaで
y_{\alpha} = p_{\alpha}^{n}(x_1,x_2,\cdots,x_n)
を満たすものが存在する。
すなわち\left\{ y_{k1},y_{k2},\cdots,y_{kn_k}\right\}の各要素は\vec{x}の射影と表せるので原始的関数である。
また、問題の条件と原始的関数の定義(2)より
f(x_1,x_2,\cdots,x_n) = g(g_1(y_{11},y_{12},\cdots,y_{1n_1}), \cdots, g_m(y_{m1}, y_{m2}, \cdots,y_{mn_m}))
は原始的関数である。

問 1.3.3 - 2

問題
g:N^m \to N
と
h:N^{k+1} \to N
が原始的関数で
\left\{ z_1,z_2,\cdots,z_m \right\} \subseteq \left\{ x_1, x_2,\cdots,x_n \right\}かつ\left\{ y_1,y_2,\cdots,y_k \right\} \subseteq \left\{ x_1, x_2,\cdots,x_n,y \right\}
のとき
f(x_1,x_2,\cdots,x_n,0) = g(z_1,z_2,\cdots,z_m)
f(x_1,x_2,\cdots,x_n,y+1) = h(y_1,y_2,\cdots,y_k,f(x_1,x_2,\cdots,x_n,y))
で定義される関数f:N^{n+1} \to Nは原始的である。
証明
\vec{x}の部分集合\vec{z}は問1.3.3-1と同様にp_{\alpha}^n:N^n \to N
を満たす1 \leq \alpha \leq mが存在する。
よって原始的関数の定義(2)によりg(z_1,z_2,\cdots,z_m)は原始的である。
ここで関数g^\primeを先ほどのg(z_1,z_2,\cdots,z_m)とp_{\alpha}^n:N^n \to Nの合成関数として定義すると
g^\prime:N^n \to Nなる原始的関数となる。
同様にh^\primeを
p_{\beta}^n:N^{n+1} \to N,y_{\beta} = p_{\beta}^n(x_1,x_2,\cdots,x_n,y)
h^\prime (x_1, x_2, \cdots,x_n, y, f(x_1, x_2, \cdots, x_n, y)) = h(p_1^{n+1}(x_{\beta_1},x_{\beta_2},\cdots,x_{\beta_{n+1}),\cdots, f(x_1, x_2, \cdots, x_n, y))
※x_{\beta_j}は
x_j = x_{\beta_j}(1 \leq j \leq n)
y = x_{\beta_{n+1}}
を満たすものとする。
hは原始的関数なのでそれにより定義されるh^\prime :N^{n+2} \to Nも原始的関数である。
これにより原始的関数であるg^\prime:N^m \to N h^\prime:N^{n+2} \to Nが存在し
f(x_1,x_2,\cdots,x_n,0) = g^\prime (x_1, x_2,\cdots,x_n,y)
f(x_1,x_2,\cdots,x_n,y+1) = h^\prime (x_1, x_2,\cdots,x_n,y,f(x_1,x_2,\cdots,x_n,y))
で定義される関数f:N^{n+1} \to Nも原始的関数である。

問 1.3.5 - 1

問題
\exp(x,y) = x^y
が原始的関数である事を証明せよ
証明
\exp(x,0) = 1 = suc(zero())
\exp(x,y+1) = x \exp(x,y) = mult(x, \exp(x,y))
mult(乗算)は例題により原始的関数である事が分かっており
\left\{ x \right\} \subseteq \left\{ x, y \right\}
と問1.3.3-2よりh:N^2 \to Nをh(x,y) = mult(x, \exp(x,y))
と定義すれば(3)よりexpは原始的関数である。