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

$M=|{\Sigma }^{\le n}|=1+2+\cdots +2^n=2^{n+1}-1$ とおく。$n\ge 1$ より $M\ge 3$ で、$2^n\le M<2^{n+1}$ である。

長さの組への言い換え. 各 $x\in {\Sigma }^{\le n}$ について $V(p_x)=x,|p_x|=K_V(x)$ となる $p_x\in \mathrm{dom}(V)$ を 1 つ選ぶ。$V$ は関数なので、$x\ne y$ なら $p_x\ne p_y$ である。$\{p_x\}$ は接頭語なし集合 $\mathrm{dom}(V)$ の部分集合なので接頭語なしであり、クラフトの不等式より
$$\sum _x{2}^{-{\ell }_x}\le 1({\ell }_x=K_V(x))$$
が成り立つ。逆に、非負整数の組 $({\ell }_x)$ がこの不等式を満たせば、長さ ${\ell }_x$ の列からなる接頭語なし集合 $\{q_x\}$ がとれ（クラフトの不等式の逆）、有限表 $V(q_x)=x$（それ以外では未定義）は接頭語なし復号器で、$K_V(x)\le {\ell }_x$ となる。よって求める最小値は
$$\min \{\sum _x{\ell }_x:{\ell }_x\in {\mathbb{Z}}_{\ge 0},\sum _x{2}^{-{\ell }_x}\le 1\}$$
である（$M$ 個の非負整数についての最小化）。

長さの差を 1 以下にしてよい. ある $i,j$ で ${\ell }_i\ge {\ell }_j+2$ のとき、${\ell }_i$ を $1$ 減らし ${\ell }_j$ を $1$ 増やすと、和 $\sum {\ell }_x$ は変わらず、クラフト和の変化は
$$2^{-{\ell }_i}(2-1)+2^{-{\ell }_j}(\frac{1}{2}-1)=2^{-{\ell }_i}-2^{-{\ell }_j-1}\le 2^{-{\ell }_j-2}-2^{-{\ell }_j-1}<0$$
なので不等式は保たれる。この操作を繰り返すと（$\sum {\ell }_x^2$ が真に減るので有限回で止まる）、最小値を与える組で、すべての長さが $m$ か $m+1$ であるもの（長さ $m$ が $a\ge 1$ 個、$m+1$ が $b$ 個、$a+b=M$）があるとしてよい。クラフトの条件は $a{2}^{-m}+b{2}^{-m-1}\le 1$、すなわち $2a+b\le 2^{m+1}$ である。

$m$ の決定. $k=n$（$2^k\le M<2^{k+1}$ をみたす整数）とする。
- $m\le k-1$ なら $M=a+b\le 2a+b\le 2^{m+1}\le 2^k\le M$ となり、等号から $a=0$ となって $a\ge 1$ に反する。
- $m\ge k+1$ なら和は $\ge (k+1)M$。
- $m=k$ なら、和は $kM+b$ で、$b=M-a$ と $2a+b\le 2^{k+1}$ から $a\le 2^{k+1}-M$、よって $b\ge 2M-2^{k+1}$。$a=2^{k+1}-M,b=2M-2^{k+1}$ はクラフト和がちょうど $1$ となり実現できるので、このときの最小は $kM+2M-2^{k+1}=(k+2)M-2^{k+1}$。

$M<2^{k+1}$ より $(k+2)M-2^{k+1}<(k+1)M$ なので、全体の最小値は $(k+2)M-2^{k+1}$ である。

計算. $k=n,M=2^{n+1}-1$ を代入して
$$(n+2)(2^{n+1}-1)-2^{n+1}=(n+1)2^{n+1}-n-2.$$
（このとき長さ $n$ の記述が $a=1$ 個、長さ $n+1$ の記述が $b=2^{n+1}-2$ 個。たとえば $n=1$ なら $M=3$ で長さ $1,2,2$、和 $5=2\cdot 4-3$。）

よって最小値は $(n+1)2^{n+1}-n-2$ である。

$|{\Sigma }^{\le n}|=2^{n+1}-1=:N$。$K_V(x)<\infty$ より各 $x$ に符号語 $p_x\in \mathrm{dom}(V)$（$V(p_x)=x$）が選べ、$V$ は関数なので異なる $x$ に対する $p_x$ は相異なる。$\mathrm{dom}(V)$ は接頭語なしだから、$\{p_x\}$ は接頭語なしな $N$ 個の語の集合で、$S(V)={\sum }_x|p_x|$ である。

逆に、接頭語なしな有限集合 $P$ ($|P|=N$) と全単射 ${\Sigma }^{\le n}\to P$ を任意に与えれば、有限の表なので $V$ は計算可能で、定義域 $P$ は接頭語なしであり、$K_V(x)\le |p_x|$ かつ接頭語なしで他の $p$ は $x$ に写らないので $K_V(x)=|p_x|$。よって最小値は「$N$ 葉の二分木の外部路長（葉の深さの総和）の最小値」に等しい。

$N$ 葉の二分木の外部路長の最小は、深さが $m=\lfloor {\log }_{2}N\rfloor$ と $m+1$ の葉だけからなる完全な木（Huffman 符号、重み均等）で達成される。$N=2^{n+1}-1$ なので $m=n$。深さ $n+1$ の葉の数を $u$、深さ $n$ の葉の数を $v$ とすると、$u+v=N$、$2^{-(n+1)}u+2^{-n}v=1$ すなわち $u+2v=2^{n+1}$。よって $v=1$、$u=2^{n+1}-2$。

$S_{\min }=n\cdot 1+(n+1)(2^{n+1}-2)=(n+1)2^{n+1}-n-2$。

検算: $n=1$ のとき ${\Sigma }^{\le 1}=\{\epsilon ,0,1\}$、$N=3$。符号語長は $1,2,2$ で合計 5。式は $2\cdot 4-1-2=5$ で一致。$n=2$ のとき $N=7$、長さ $2,3,3,3,3,3,3$ で合計 20、式は $3\cdot 8-4=20$ で一致。