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

$\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$ 上の有限列全体、$|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$ 上の有限列全体、$|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 }$ を空列を含む $\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$ を含む有限 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$$
が成り立つことを証明せよ。