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

$\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$ を含む）とし、関数 $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$ を含む）とし、関数 $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$ の式で表せ。

この問題では $\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$ を含む）とし、関数 $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(m,n)$ を計算する。すなわち、手続き $A(m,n)$ が呼ばれると、$m=0$ なら再帰呼び出しをせずに $n+1$ を返し、$m\ge 1,n=0$ なら $A(m-1,1)$ を $1$ 回呼んでその値を返し、$m\ge 1,n\ge 1$ ならまず $A(m,n-1)$ を呼んでその値 $r$ を得たのち $A(m-1,r)$ を呼んでその値を返す。最初の呼び出しも含めて、$A(m,n)$ の計算で手続き $A$ が呼ばれる回数の合計を $C(m,n)$ とする（たとえば $C(0,n)=1$、$C(1,0)=2$）。

$n\in \mathbb{N}$ に対し、$C(3,n)$ を $n$ の式で表せ。