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

$n$ を正の整数とし、$n$ 変数のブール関数とは写像 $f:\{0,1{\}}^n\to \{0,1\}$ のこととする。$f$ が第 $i$ 変数に本質的に依存するとは、ある $a_1,\dots ,a_{i-1},a_{i+1},\dots ,a_n\in \{0,1\}$ が存在して
$$f(a_1,\dots ,a_{i-1},0,a_{i+1},\dots ,a_n)\ne f(a_1,\dots ,a_{i-1},1,a_{i+1},\dots ,a_n)$$
となることをいう。

3 変数のブール関数 $f:\{0,1{\}}^3\to \{0,1\}$ のうち、3 つの変数 $x_1,x_2,x_3$ のすべてに本質的に依存するものの個数を求めよ。

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。関数 $g:\mathbb{N}\to \mathbb{N}$ と $j\in \mathbb{N}$ に対し、$g^{(j)}$ を $g$ の $j$ 回合成（$g^{(0)}$ は恒等写像、$g^{(j+1)}=g\circ g^{(j)}$）とする。

関数の列 $f_k:\mathbb{N}\to \mathbb{N}$（$k=0,1,2,\dots$）を次で定める（アッカーマン関数と同じ増大度をもつ階層の一種である）。
$$f_0(n)=n+1,f_{k+1}(n)=f_k^{(n+1)}(n)(k,n\in \mathbb{N}).$$
このとき、$f_3(1)$ の値を求めよ。

$7$ 変数のブール関数とは写像 $f:\{0,1{\}}^7\to \{0,1\}$ のこととする。$7$ 変数のブール関数 $f$ で、次の 2 つの条件をともに満たすものの個数を求めよ。

$(1)$（巡回不変性）すべての $(x_1,\dots ,x_7)\in \{0,1{\}}^7$ に対して $$f(x_1,x_2,\dots ,x_7)=f(x_2,x_3,\dots ,x_7,x_1).$$

$(2)$（自己双対性）すべての $(x_1,\dots ,x_7)\in \{0,1{\}}^7$ に対して $$f(1-x_1,1-x_2,\dots ,1-x_7)=1-f(x_1,x_2,\dots ,x_7).$$

$\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 }$ を空列を含む $\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|$ の最小値を求めよ。