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

$\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$ で割った余りを求めよ。

$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}$ を次の再帰式で定める（アッカーマン・ペーター関数）。
$$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}$ と $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}$ をすべての $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$ の式で表せ。