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

$\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$ の列全体とする。部分計算可能関数 $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$ の長さ、${\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$ の式で求めよ。

$\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)$$ の最小値を求めよ。