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

$0$ 以上の整数全体を ${\mathbb{N}}_0$ とする。関数 $B:{\mathbb{N}}_0\times {\mathbb{N}}_0\to {\mathbb{N}}_0$ を、すべての $m,n\in {\mathbb{N}}_0$ に対して
$$B(0,n)=n+2,$$
$$B(m+1,0)=B(m,1),$$
$$B(m+1,n+1)=B(m,B(m+1,n))$$
を満たすものとして（アッカーマン関数と同様の二重帰納法で）定める。$B(3,1)$ の値を求めよ。

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、関数 $A:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$（アッカーマン・ペーター関数）を次の再帰で定める。すべての $m,n\in \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)).$$
このとき、$A(4,3)$ を $1000$ で割った余りを求めよ。

この問題では $\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$ を含む）とする。関数 $g:\mathbb{N}\to \mathbb{N}$ と $h:{\mathbb{N}}^3\to \mathbb{N}$ を
$$g(y)=y+1,h(n,z,y)=z+y+3$$
で定め、関数 $f:{\mathbb{N}}^2\to \mathbb{N}$ を原始再帰
$$f(0,y)=g(y),f(n+1,y)=h(n,f(n,y),y)(n,y\in \mathbb{N})$$
で定める。$f(n,y)$ を $n,y$ の式で表せ。

$\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$ の式で表せ。