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

$\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$ の列全体とする。部分計算可能関数 $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$ の列全体とする。集合 $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$ の列全体とする。集合 $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$ 上の有限列全体、$|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$ に含まれる圧縮不可能な列の個数の最小値を求めよ。