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

閉じた形を求める. $m$ について順に、$n$ に関する帰納法で示す。

- $A(1,n)=n+2$：$A(1,0)=A(0,1)=2$、$A(1,n+1)=A(0,A(1,n))=A(1,n)+1$。
- $A(2,n)=2n+3$：$A(2,0)=A(1,1)=3$、$A(2,n+1)=A(1,A(2,n))=A(2,n)+2$。
- $A(3,n)=2^{n+3}-3$：$A(3,0)=A(2,1)=5=2^3-3$、$A(3,n+1)=A(2,A(3,n))=2(2^{n+3}-3)+3=2^{n+4}-3$。
- $A(4,n)=T_{n+3}-3$。ここで $T_1=2,T_{k+1}=2^{T_k}$（$2$ の $k$ 段の指数の塔）とする。実際 $A(4,0)=A(3,1)=2^4-3=13=T_3-3$（$T_3=2^{2^2}=16$）、また
$$A(4,n+1)=A(3,A(4,n))=2^{A(4,n)+3}-3=2^{T_{n+3}}-3=T_{n+4}-3.$$

よって
$$A(4,3)=T_6-3,T_5=2^{65536},T_6=2^{2^{65536}}.$$

$T_6\mathrm{mod}1000$ を求める. $1000=8\cdot 125$ として中国剰余定理を使う。

(1) $\mathrm{mod}8$：指数 $T_5\ge 3$ なので $T_6\equiv 0(\mathrm{mod}8)$。

(2) $\mathrm{mod}125$：$\gcd (2,125)=1$、$\phi (125)=100$ なのでオイラーの定理より $2^{100}\equiv 1(\mathrm{mod}125)$。したがって指数 $T_5=2^{65536}$ を $100$ で割った余りが必要である。

• $\mathrm{mod}4$：$2^{65536}\equiv 0$。
• $\mathrm{mod}25$：$\phi (25)=20$、$65536\equiv 16(\mathrm{mod}20)$ より $2^{65536}\equiv 2^{16}=65536\equiv 11(\mathrm{mod}25)$。

$x\equiv 0(\mathrm{mod}4),x\equiv 11(\mathrm{mod}25)$ を満たす $0\le x<100$ は $x=36$。よって $T_5\equiv 36(\mathrm{mod}100)$ で、
$$T_6\equiv 2^{36}(\mathrm{mod}125).$$
$2^{10}=1024\equiv 24$、$2^{20}\equiv 24^2=576\equiv 76$、$2^{30}\equiv 76\cdot 24=1824\equiv 74$、$2^{36}\equiv 74\cdot 64=4736\equiv 4736-4625=111(\mathrm{mod}125)$。

(3) $y\equiv 0(\mathrm{mod}8),y\equiv 111(\mathrm{mod}125)$：$y=111+125k$ とおくと $111+125k\equiv 7+5k\equiv 0(\mathrm{mod}8)$、すなわち $5k\equiv 1$、$k\equiv 5(\mathrm{mod}8)$。よって $y=111+625=736$。

したがって $T_6\equiv 736(\mathrm{mod}1000)$ で、
$$A(4,3)=T_6-3\equiv 733(\mathrm{mod}1000).$$
答えは $733$。

まず閉じた形を求める。$A(1,n)=n+2$、$A(2,n)=2n+3$、$A(3,n)=2^{n+3}-3$ を帰納法で示す。$A(3,0)=A(2,1)=5=2^3-3$、$A(3,n+1)=A(2,A(3,n))=2(2^{n+3}-3)+3=2^{n+4}-3$。
次に $A(4,0)=A(3,1)=13$、$A(4,n+1)=A(3,A(4,n))=2^{A(4,n)+3}-3$。$T_k$ を $T_1=2,T_{k+1}=2^{T_k}$（塔）とおくと、$A(4,n)+3=T_{n+3}$ が成り立つ（$n=0$: $16=T_3$、漸化式 $T_{n+4}=2^{T_{n+3}}$ より）。よって $A(4,3)=T_6-3$、ここで $T_6=2^{T_5}$、$T_5=2^{65536}$。

$T_6\mathrm{mod}1000$ を求める。1000=8・125。
- mod 8: $T_5$ は十分大きいので $2^{T_5}\equiv 0$。
- mod 125: $2$ の位数は $100$ の約数なので $T_5\mathrm{mod}100$ が必要。$T_5=2^{65536}$。mod 4 では $0$。mod 25 では $2$ の位数は $20$、$65536\equiv 16(\mathrm{mod}20)$ なので $2^{16}=65536\equiv 11(\mathrm{mod}25)$。$x\equiv 0(\mathrm{mod}4),x\equiv 11(\mathrm{mod}25)$ より $x\equiv 36(\mathrm{mod}100)$。したがって $T_6\equiv 2^{36}(\mathrm{mod}125)$。$2^7=128\equiv 3$ より $2^{36}=(2^7{)}^5\cdot 2\equiv 3^5\cdot 2=486\equiv 111(\mathrm{mod}125)$。
- 合成: $x\equiv 111(\mathrm{mod}125)$, $x\equiv 0(\mathrm{mod}8)$ より $x=111+125k$、$7+5k\equiv 0(\mathrm{mod}8)$ から $k\equiv 5$、$x\equiv 736(\mathrm{mod}1000)$。

ゆえに $A(4,3)=T_6-3\equiv 733(\mathrm{mod}1000)$。検算: $736\mathrm{mod}8=0$、$736\mathrm{mod}125=111$。また $A(4,1)=65533=T_4-3$ で $T_4=65536$ と一致する。