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

${\Sigma }^{\le 8}$ の元の個数は $N=1+2+\cdots +2^8=2^9-1=511$ である。

接頭語なし符号への言い換え. $V$ を条件を満たす関数とし、各 $x\in {\Sigma }^{\le 8}$ について $V(p_x)=x$, $|p_x|=K_V(x)$ となる $p_x$ を 1 つ選ぶ。$V$ は関数なので $x\ne y$ なら $p_x\ne p_y$ であり、$\{p_x\}$ は定義域の部分集合だから接頭語なしである。よって $S(V)={\sum }_x|p_x|$ は「$511$ 個の相異なる列からなる接頭語なし集合の長さの総和」である。逆に、$511$ 個の列からなる接頭語なし集合 $\{q_x\}$ があれば、$V(q_x)=x$（それ以外は未定義）とおくと、これは有限個の値の表なので計算可能で、定義域は接頭語なしであり、$S(V)\le {\sum }_x|q_x|$ となる。したがって求める最小値は、$511$ 個の列からなる接頭語なし集合の長さの総和の最小値に等しい。

クラフトの不等式. 接頭語なし集合 $\{p_1,\dots ,p_N\}$ の長さを $l_i=|p_i|$ とする。$L=\max l_i$ とすると、$p_i$ を接頭語にもつ長さ $L$ の列は $2^{L-l_i}$ 個あり、接頭語なしなのでこれらの集合は互いに交わらない。長さ $L$ の列は $2^L$ 個なので ${\sum }_i{2}^{L-l_i}\le 2^L$、すなわち $$\sum _{i=1}^N{2}^{-l_i}\le 1.$$

下界. 関数 $g(l)=2^{-l}$ は凸であり、$l=8,9$ での値 $\frac{1}{256},\frac{1}{512}$ を結ぶ直線は $h(l)=\frac{10-l}{512}$ である。凸関数はこの 2 点を結ぶ弦の外側（$l\le 8$ または $l\ge 9$）で弦より上にあるので、すべての整数 $l\ge 0$ について $2^{-l}\ge \frac{10-l}{512}$ が成り立つ（等号は $l=8,9$ のときのみ）。よって $$1\ge \sum _{i=1}^{511}{2}^{-l_i}\ge \sum _{i=1}^{511}\frac{10-l_i}{512}=\frac{5110-{\sum }_i{l}_i}{512}$$ となり、$$\sum _{i=1}^{511}{l}_i\ge 5110-512=4598.$$

達成. 等号が成り立つのは、すべての $l_i$ が $8$ か $9$ で、$\sum 2^{-l_i}=1$ のときである。長さ $8$ のものを $a$ 個とすると $\frac{a}{256}+\frac{511-a}{512}=1$ より $a=1$。実際、$q=00000000$（長さ $8$）と、$q$ で始まらない長さ $9$ の列 $512-2=510$ 個を合わせた $511$ 個の列は接頭語なし集合であり、長さの総和は $8+9\cdot 510=4598$ である。これを ${\Sigma }^{\le 8}$ の $511$ 個の元に 1 対 1 に割り当てた $V$ で $S(V)=4598$ となる。

以上より、最小値は $4598$ である。

${\Sigma }^{\le 8}$ の元は ${\sum }_{k=0}^8{2}^k=511$ 個。各 $x$ に対し $K_V(x)$ を達成する最短の入力 $p_x$ をとる。$V$ は関数なので $x\ne x^{\prime }$ なら $p_x\ne p_{x^{\prime }}$、さらに定義域は接頭語なしなので $\{p_x\}$ は 511 個の相異なる語からなる接頭語なし集合（符号）である。したがって Kraft の不等式 ${\sum }_x{2}^{-|p_x|}\le 1$ が成り立つ。

逆に、Kraft の不等式を満たす長さの列があれば、それらの長さをもつ接頭語なし集合が構成でき、${\Sigma }^{\le 8}$ の元に割り当てる有限表で $V$ を定めれば、$V$ は計算可能で定義域は接頭語なしである。よって、問題は「511 個の語の接頭語なし符号の総語長の最小化」と一致する。

最適な符号は完全 2 分木の葉に対応し、等重みなので葉の深さは 2 種類（連続する値）になる。深さ 8 の葉が $a$ 個、深さ 9 の葉が $b$ 個とすると、$a+b=511$、Kraft 等号 $a/2^8+b/2^9=1$（すなわち $2a+b=512$）より $a=1,b=510$。総語長は $8\cdot 1+9\cdot 510=4598$。

最小性の確認: 深さ 8 以下のみでは葉は高々 $2^8=256<511$ 個しか作れないので、少なくとも一部は深さ 9 以上が必要。一般に総語長を最小化する符号は、Kraft の和が 1 の完全木で、かつ葉の深さの差が 1 以下（差が 2 以上なら、深い葉を浅い葉の位置で分岐させ直すことで総和が減る）となる。上の $(a,b)=(1,510)$ はこれを満たす。

検算: $1/256+510/512=2/512+510/512=1$。したがって最小値は $4598$。