記述複雑性とカウンティング論法

$\Sigma =\{0,1\}$ とし、${\Sigma }^{\ast }$ を空列 $\epsilon$ を含む $\Sigma$ 上の有限列全体、$|p|$ を列 $p$ の長さ、${\Sigma }^6$ を長さ $6$ の列全体とする。

部分関数 $V:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$（定義されない入力があってもよい）を記述方式とよび、$x\in {\Sigma }^{\ast }$ に対して
$$C_V(x)=\min \{|p|:V(p)=x\}$$
と定める（$V(p)=x$ となる $p$ がなければ $C_V(x)=\infty$ とする）。

記述方式 $V$ をいろいろに選ぶとき、$C_V(x)\le 3$ をみたす $x\in {\Sigma }^6$ の個数のとりうる最大値を求めよ。

$\Sigma =\{0,1\}$ とし、${\Sigma }^{\ast }$ を空列を含む $\Sigma$ 上の有限列全体、$|p|$ を列 $p$ の長さ、${\Sigma }^n$ を長さ $n$ の列全体とする。部分計算可能関数 $V:{\Sigma }^{\ast }\rightharpoonup {\Sigma }^{\ast }$ に対して、$x\in {\Sigma }^{\ast }$ の $V$ に関する記述複雑性を
$$C_V(x)=\min \{|p|:p\in {\Sigma }^{\ast },V(p)\text{ が定義されて }V(p)=x\}$$
で定める（そのような $p$ がなければ $C_V(x)=\infty$ とする）。

部分計算可能関数 $V$ を一つ定めるごとに、集合
$$R_V=\{x\in {\Sigma }^{10}:C_V(x)\ge 7\}$$
の要素の個数 $|R_V|$ が決まる。$V$ がすべての部分計算可能関数を動くときの $|R_V|$ の最小値を求めよ。

$\Sigma =\{0,1\}$ とし、${\Sigma }^{\ast }$ を空列 $\epsilon$ を含む $\Sigma$ 上の有限列全体、$|p|$ を列 $p$ の長さ、${\Sigma }^n$ を長さ $n$ の列全体とする。集合 $S\subseteq {\Sigma }^{\ast }$ が接頭語なしであるとは、$S$ のどの元も $S$ の別の元の真の接頭語（先頭部分）になっていないことをいう。

部分関数 $D:{\Sigma }^{\ast }\rightharpoonup {\Sigma }^{\ast }$ で、定義域 $\mathrm{dom}(D)$ が接頭語なしであるものを接頭語なし復号器とよぶ（$D$ が計算可能であることは要求しない）。接頭語なし復号器 $D$ と $x\in {\Sigma }^{\ast }$ に対し、
$$K_D(x)=\min \{|p|:p\in \mathrm{dom}(D),D(p)=x\}$$
と定める（そのような $p$ がなければ $K_D(x)=\infty$ とする）。

接頭語なし復号器 $D$ に対し、$N(D)$ を $K_D(x)\ge 8$ を満たす $x\in {\Sigma }^{10}$ の個数とする。$D$ がすべての接頭語なし復号器を動くときの $N(D)$ の最小値を求めよ。

$\Sigma =\{0,1\}$ とし、${\Sigma }^{\ast }$ を空列 $\epsilon$ を含む $\Sigma$ 上の有限列全体、$|p|$ を列 $p$ の長さ、${\Sigma }^n$ を長さ $n$ の列全体とする。部分計算可能関数 $U:{\Sigma }^{\ast }\rightharpoonup {\Sigma }^{\ast }$ に対し、$x\in {\Sigma }^{\ast }$ の $U$ に関する（プレーンな）記述複雑性を
$$C_U(x)=\min \{|p|:p\in {\Sigma }^{\ast },U(p)=x\}$$
で定める。ただし $U(p)=x$ となる $p$ が存在しないときは $C_U(x)=\infty$ とする。$U$ の定義域が接頭語自由であることは仮定しない。

すべての部分計算可能関数 $U$ を考えたときの
$$S(U)=\sum _{x\in {\Sigma }^{10}}{C}_U(x)$$
の最小値を求めよ。

$\Sigma =\{0,1\}$ とし、${\Sigma }^{\ast }$ を空列 $\epsilon$ を含む $\Sigma$ 上の有限列全体、$|x|$ を列 $x$ の長さとする。

部分関数 $U:{\Sigma }^{\ast }\rightharpoonup {\Sigma }^{\ast }$（「記述方式」と呼ぶ。$U$ は計算可能でなくてもよい）に対し、$x\in {\Sigma }^{\ast }$ の複雑性を
$$C_U(x)=\min \{|p|:p\in {\Sigma }^{\ast },U(p)=x\}$$
で定める。ただし $U(p)=x$ となる $p$ が存在しないときは $C_U(x)=\infty$ とする。$C_U(x)\ge |x|$ を満たす $x$ を（$U$ に関して）圧縮不可能という。

長さが $12$ 以下の列（空列を含む）全体の集合を $S=\{x\in {\Sigma }^{\ast }:|x|\le 12\}$ とする。記述方式 $U$ をあらゆる部分関数にわたって動かすとき、$S$ に含まれる圧縮不可能な列の個数の最小値を求めよ。

$\Sigma =\{0,1\}$ とし、${\Sigma }^{\ast }$ を空列 $\epsilon$ を含む $\Sigma$ 上の有限列全体、$|p|$ を列 $p$ の長さ、${\Sigma }^n$ を長さ $n$ の列全体とする。部分計算可能関数 $V:{\Sigma }^{\ast }\rightharpoonup {\Sigma }^{\ast }$（定義域が ${\Sigma }^{\ast }$ の部分集合である計算可能な部分関数。定義域が接頭語自由である必要はない）に対し、$x\in {\Sigma }^{\ast }$ の $V$ に関する記述量を
$$C_V(x)=\min \{|p|\mid p\in {\Sigma }^{\ast },V(p)\text{ が定義されて }V(p)=x\}$$
で定める（そのような $p$ がなければ $C_V(x)=\infty$）。

$n$ を正の整数とする。$V$ が部分計算可能関数全体を動くとき、
$$S_V(n)=\sum _{x\in {\Sigma }^n}{C}_V(x)$$
の最小値を $n$ の式で表せ。

$\Sigma =\{0,1\}$ とし、${\Sigma }^{\ast }$ を空列 $\epsilon$ を含む有限 2 進列全体、$|x|$ を列 $x$ の長さ、${\Sigma }^n$ を長さ $n$ の列全体とする。万能チューリング機械 $U$ を 1 つ固定し、$U$ が計算する部分関数 $U:{\Sigma }^{\ast }\rightharpoonup {\Sigma }^{\ast }$ は、任意の $x\in {\Sigma }^{\ast }$ に対して $U(p)=x$ となる $p\in {\Sigma }^{\ast }$ が存在するものとする。$x\in {\Sigma }^{\ast }$ のコルモゴロフ複雑性を
$$C(x)=\min \{|p|:p\in {\Sigma }^{\ast },U(p)=x\}$$
で定める（$U(p)=x$ は、入力 $p$ で $U$ が停止して $x$ を出力することを表す）。

任意の正の整数 $n$ に対して
$$\frac{1}{2^n}\sum _{x\in {\Sigma }^n}C(x)>n-2$$
が成り立つことを証明せよ。

$\Sigma =\{0,1\}$ とし、${\Sigma }^{\ast }$ を空列 $\epsilon$ を含む $\Sigma$ 上の有限列全体、$|p|$ を列 $p$ の長さ、${\Sigma }^n$ を長さ $n$ の列全体とする。集合 $D\subseteq {\Sigma }^{\ast }$ が接頭語自由であるとは、$D$ のどの元も $D$ の別の元の真の接頭語になっていないことをいう。

部分計算可能関数 $V:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ で、定義域 $\mathrm{dom}(V)$ が接頭語自由であるものを考える。$x\in {\Sigma }^{\ast }$ に対し
$$K_V(x)=\min \{|p|:p\in \mathrm{dom}(V),V(p)=x\}$$
と定める（そのような $p$ がなければ $K_V(x)=\infty$ とする）。

$V$ は次の条件を満たすとする。

（条件）長さ $4$ 以下のすべての列 $y$（$y=\epsilon$ も含む）に対して $K_V(y)\le 2|y|+2$ である。

この条件を満たすような $V$ すべてを考えるとき、$K_V(x)\ge 9$ を満たす $x\in {\Sigma }^{10}$ の個数としてありうる最小値を求めよ。

$\Sigma =\{0,1\}$ とし、${\Sigma }^{\ast }$ を空列 $\epsilon$ を含む $\Sigma$ 上の有限列全体、$|p|$ を列 $p$ の長さとする。${\Sigma }^{\le 8}$ を長さ $8$ 以下の列全体（空列を含む）とする。列の集合 $D\subseteq {\Sigma }^{\ast }$ が接頭語なしであるとは、$D$ の相異なる 2 つの元の一方が他方の接頭語（先頭部分）になることがないことをいう。

部分計算可能関数 $V:{\Sigma }^{\ast }\rightharpoonup {\Sigma }^{\ast }$ で、その定義域が接頭語なしであるものを考える。このような $V$ と $x\in {\Sigma }^{\ast }$ に対して $$K_V(x)=\min \{|p|:p\in {\Sigma }^{\ast },V(p)=x\}$$ と定める（そのような $p$ がなければ $K_V(x)=\infty$ とする）。

定義域が接頭語なしである部分計算可能関数 $V$ で、すべての $x\in {\Sigma }^{\le 8}$ に対して $K_V(x)<\infty$ となるものすべてにわたる $$S(V)=\sum _{x\in {\Sigma }^{\le 8}}{K}_V(x)$$ の最小値を求めよ。

$\Sigma =\{0,1\}$ とし、${\Sigma }^{\ast }$ を空列 $\epsilon$ を含む $\Sigma$ 上の有限列全体、$|x|$ を列 $x$ の長さ、${\Sigma }^{\le n}$ を長さ $n$ 以下の列全体とする。集合 $D\subseteq {\Sigma }^{\ast }$ が接頭語なしであるとは、$D$ の相異なる 2 元の一方が他方の接頭語になることがないことをいう。

部分計算可能関数 $V:{\Sigma }^{\ast }\rightharpoonup {\Sigma }^{\ast }$ で、定義域 $\mathrm{dom}(V)$ が接頭語なしであるものを接頭語なし復号器とよぶ。接頭語なし復号器 $V$ と $x\in {\Sigma }^{\ast }$ に対し
$$K_V(x)=\min \{|p|:p\in \mathrm{dom}(V),V(p)=x\}$$
と定める（そのような $p$ がなければ $K_V(x)=\infty$）。

$n$ を正の整数とする。接頭語なし復号器 $V$ で、すべての $x\in {\Sigma }^{\le n}$ に対して $K_V(x)<\infty$ となるもの全体を考えるとき、
$$S(V)=\sum _{x\in {\Sigma }^{\le n}}{K}_V(x)$$
の最小値を $n$ の式で求めよ。