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

方針. 接頭語自由な集合に対するクラフトの不等式を使って、$K_V(x)\le 8$ となる $x\in {\Sigma }^{10}$ の個数の上限を求める。そのうえで、上限が実際に達成されることを示す。

クラフトの不等式. $P\subseteq {\Sigma }^{\ast }$ が接頭語自由な有限集合なら ${\sum }_{p\in P}{2}^{-|p|}\le 1$ が成り立つ。

証明：$L={\max }_{p\in P}|p|$ とする。各 $p$ に、$p$ で始まる長さ $L$ の列全体（$2^{L-|p|}$ 個）を対応させる。$P$ は接頭語自由なので、異なる $p$ に対応するこれらの集合は互いに交わらない。どれも ${\Sigma }^L$ に含まれるから ${\sum }_p{2}^{L-|p|}\le 2^L$ となる。

上限. 長さ $4$ 以下の各 $y$ について、$V(p_y)=y$ かつ $|p_y|=K_V(y)\le 2|y|+2$ となる $p_y$ を $1$ つ選ぶ。また、$K_V(x)\le 8$ を満たす各 $x\in {\Sigma }^{10}$ について、$V(q_x)=x$ かつ $|q_x|\le 8$ となる $q_x$ を $1$ つ選ぶ。そのような $x$ の個数を $N$ とする。

$V$ は関数なので、出力が異なれば選んだ入力も異なる。出力となる列 $y$ と $x$ も長さが違うので互いに異なる。したがって選んだ入力はすべて互いに異なり、それらの集合 $P$ は $\mathrm{dom}(V)$ の有限部分集合なので接頭語自由である。クラフトの不等式より
$$\sum _{|y|\le 4}{2}^{-|p_y|}+\sum _x{2}^{-|q_x|}\le 1.$$

長さ $l$ の列は $2^l$ 個あるので、第 $1$ 項は
$$\sum _{l=0}^4{2}^l\cdot 2^{-(2l+2)}=\frac{1}{4}\left(1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}\right)=\frac{1}{4}\cdot \frac{31}{16}=\frac{31}{64}$$
以上である。第 $2$ 項は $N\cdot 2^{-8}$ 以上である。よって
$$\frac{N}{256}\le 1-\frac{31}{64}=\frac{33}{64}$$
となり、$N\le 132$ を得る。

達成. 次の長さの符号語を考える。
- 長さ $2$ を $1$ 個、長さ $4$ を $2$ 個、長さ $6$ を $4$ 個、長さ $8$ を $8$ 個、長さ $10$ を $16$ 個（短い列 $y$ 用）
- 長さ $8$ をさらに $132$ 個（${\Sigma }^{10}$ の列用）

クラフト和は
$$\frac{31}{64}+\frac{132}{256}=\frac{124+132}{256}=1\le 1$$
である。クラフトの不等式の逆（長さの短い順に、辞書式で最小の使える列を割り当てていく構成）により、これらの長さをもつ接頭語自由な符号語の集合が存在する。

各 $y$（$|y|\le 4$）に長さ $2|y|+2$ の符号語を、$132$ 個の $x\in {\Sigma }^{10}$ に長さ $8$ の符号語を割り当てて $V$ を定義し、ほかの入力では未定義とする。定義域は有限なので $V$ は計算可能であり、条件も満たす。このとき $K_V(x)\le 8$ となる $x\in {\Sigma }^{10}$ はちょうど $132$ 個である。

結論. $K_V(x)\ge 9$（$K_V(x)=\infty$ を含む）となる $x\in {\Sigma }^{10}$ の個数の最小値は
$$2^{10}-132=1024-132=892$$
である。

定義域 $\mathrm{dom}(V)$ は接頭語自由なので Kraft の不等式 ${\sum }_{p\in \mathrm{dom}(V)}{2}^{-|p|}\le 1$ が成り立つ。

1. 長さ $n\le 4$ の各列 $y$ には、$V(p)=y$ となる $p$ で $|p|\le 2n+2$ を満たすものが必要である。異なる $y$ には異なる $p$ が対応する。$y$ 1 個あたりの Kraft 和への寄与は、$|p|=2n+2$ のとき最小で $2^{-(2n+2)}$ である。
2. これらの $y$ 全体の寄与の最小値は ${\sum }_{n=0}^4{2}^n\cdot 2^{-(2n+2)}={\sum }_{n=0}^4{2}^{-n-2}=31/64$ である。
3. 残りの Kraft 和は $33/64$ である。$x\in {\Sigma }^{10}$ は長さ 4 以下の列ではないので、$K_V(x)\le 8$ とするには $x$ ごとに別の符号語が必要で、その長さは 8 以下である。1 個あたりの寄与は $2^{-8}$ 以上である。したがって $K_V(x)\le 8$ となる $x$ の個数は高々 $\frac{33}{64}\cdot 256=132$ である。
4. 達成可能性を確かめる。符号語の長さを、長さ 2 が 1 個、4 が 2 個、6 が 4 個、8 が $8+132$ 個、10 が 16 個とする。Kraft 和は $124/256+132/256=1$ なので、この長さをもつ接頭語自由な有限集合が存在する。定義域が有限なので $V$ は計算可能である。これらを $y$（長さ 4 以下の 31 個）と、${\Sigma }^{10}$ の 132 個の $x$ に割り当てる。
5. よって $K_V(x)\le 8$ となる $x\in {\Sigma }^{10}$ の最大個数は 132 であり、$K_V(x)\ge 9$ となる個数の最小値は $1024-132=892$ である。