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

$\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$ の列全体とする。部分計算可能関数 $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$ を含む $\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$ の列全体とする。集合 $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 }^{\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)$$ の最小値を求めよ。