計算理論・ラムダ計算の問題

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。関数 $g:\mathbb{N}\to \mathbb{N}$ と $j\in \mathbb{N}$ に対し、$g^{(j)}$ を $g$ の $j$ 回合成（$g^{(0)}$ は恒等写像、$g^{(j+1)}=g\circ g^{(j)}$）とする。

関数の列 $f_k:\mathbb{N}\to \mathbb{N}$（$k=0,1,2,\dots$）を次で定める（アッカーマン関数と同じ増大度をもつ階層の一種である）。
$$f_0(n)=n+1,f_{k+1}(n)=f_k^{(n+1)}(n)(k,n\in \mathbb{N}).$$
このとき、$f_3(1)$ の値を求めよ。

この問題では $\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。関数 $A:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ を次の再帰式で定める（アッカーマン・ペーター関数）。
$$A(0,n)=n+1,A(m+1,0)=A(m,1),A(m+1,n+1)=A(m,A(m+1,n))(m,n\in \mathbb{N}).$$
この再帰式によって $A$ がすべての $(m,n)\in \mathbb{N}\times \mathbb{N}$ で一意に定まる全域関数であることは用いてよい。

すべての $n\in \mathbb{N}$ に対して
$$A(3,n)=2^{n+3}-3$$
が成り立つことを証明せよ。

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、関数 $B:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ を、すべての $m,n\in \mathbb{N}$ について次の式で定める。
$$B(0,n)=n+2,$$
$$B(m+1,0)=B(m,1),$$
$$B(m+1,n+1)=B(m,B(m+1,n)).$$
$B(2,3)$ の値を求めよ。

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、関数 $G:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ を次の再帰で定める（アッカーマン関数の変形である）。すべての $m,n\in \mathbb{N}$ に対して
$$G(0,n)=n+1,$$
$$G(m+1,0)=G(m,2),$$
$$G(m+1,n+1)=G(m,G(m+1,n)).$$
この再帰は $(m,n)$ の辞書式順序に関する整礎帰納法によりすべての $(m,n)$ で値が定まる。$n$ を $0$ 以上の整数とするとき、$G(3,n)$ を $n$ の式で表せ。

型なしラムダ計算を考える。適用は左結合（$MNL=(MN)L$）、抽象は右に最大限のびるものとし、$\alpha$ 同値な項は同一視する。簡約は $\beta$ 簡約のみを考える。$0$ 以上の整数 $n$ に対してチャーチ数を
$$c_n=\lambda f.\lambda x.f^{n}x(f^{0}x=x,f^{n+1}x=f(f^{n}x))$$
と定め、対と射影を
$$P=\lambda a.\lambda b.\lambda z.zab,{\pi }_1=\lambda a.\lambda b.a,{\pi }_2=\lambda a.\lambda b.b$$
と定める。さらに
$$G=\lambda p.P(p{\pi }_2)(c_2(p{\pi }_1))$$
とおき、項
$$M=c_{3}G(P{c}_2{c}_3){\pi }_2$$
を考える。$M$ の $\beta$ 正規形はあるチャーチ数 $c_k$ である。$k$ を求めよ。