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

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

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

$4$ 変数のブール関数とは写像 $f:\{0,1{\}}^4\to \{0,1\}$ のこととし、$\{0,1\}$ を 2 元体 ${\mathbb{F}}_2$ と同一視する。各 $4$ 変数のブール関数 $f$ は、${\mathbb{F}}_2$ 上の多項式として
$$f(x_1,x_2,x_3,x_4)=\sum _{S\subseteq \{1,2,3,4\}}{a}_S\prod _{i\in S}{x}_i(a_S\in {\mathbb{F}}_2)$$
の形にただ 1 通りに表される（代数的標準形。$S=\varnothing$ のときの積は $1$ とする）。$a_S=1$ となる $S$ の要素の個数 $|S|$ の最大値を $f$ の次数とよぶ（恒等的に $0$ の関数の次数は $-\infty$ とする）。

次数がちょうど $2$ である $4$ 変数のブール関数の個数を求めよ。