計算理論・ラムダ計算

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。関数 $g:\mathbb{N}\to \mathbb{N}$ と $h:{\mathbb{N}}^3\to \mathbb{N}$ を
$$g(y)=y+1,h(n,z,y)=z+y+3$$
で定め、関数 $f:{\mathbb{N}}^2\to \mathbb{N}$ を原始再帰
$$f(0,y)=g(y),f(n+1,y)=h(n,f(n,y),y)(n,y\in \mathbb{N})$$
で定める。$f(n,y)$ を $n,y$ の式で表せ。

型なしラムダ計算を考える。適用は左結合（$MNL=(MN)L$）、抽象は右に最大限のびるものとし、$\alpha$ 同値な項は同一視する。簡約は $\beta$ 簡約のみを考える（$\eta$ 簡約は考えない）。$y,z,w$ は変数とする。

項
$$M=(\lambda x.\lambda y.xy)(\lambda z.zy)$$
の $\beta$ 正規形として正しいものを、次のア〜オから 1 つ選べ。

ア　$\lambda y.yy$

イ　$\lambda w.wy$

ウ　$\lambda w.yw$

エ　$y$

オ　$M$ は $\beta$ 正規形をもたない

$\Sigma =\{0,1\}$ とし、言語とは ${\Sigma }^{\ast }$ の部分集合のこととする。言語 $L$ の補集合を $\overline{L}={\Sigma }^{\ast }\setminus L$ と書く。言語 $X,Y$ について、$X{\le }_{p}Y$ とは、多項式時間で計算できる全域関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ で、すべての $x\in {\Sigma }^{\ast }$ について $x\in X⟺f(x)\in Y$ となるものが存在することとする。

いま、言語 $A,B$ について $A\in \mathrm{P}$、$B\in \mathrm{NP}$ であることだけがわかっている。次のア〜オの言語のうち、それぞれに書かれた条件だけから「$\mathrm{NP}$ に属する」と必ず結論できるものをすべて選べ。

ア　ある言語 $H$ について $C{\le }_{p}H$ かつ $H{\le }_{p}A$ をみたす言語 $C$

イ　$D{\le }_{p}B$ をみたす言語 $D$

ウ　$A{\le }_{p}E$ をみたす言語 $E$

エ　$\overline{F}{\le }_{p}A$ をみたす言語 $F$

オ　$B{\le }_{p}G$ をみたす言語 $G$

$4$ 変数のブール関数とは写像 $f:\{0,1{\}}^4\to \{0,1\}$ のこととする。$a\in \{0,1\}$ に対して $\overline{a}=1-a$ とし、$x=(x_1,x_2,x_3,x_4)\in \{0,1{\}}^4$ に対して $\overline{x}=(\overline{x_1},\overline{x_2},\overline{x_3},\overline{x_4})$ とする。

$4$ 変数のブール関数 $f$ が自己双対であるとは、すべての $x\in \{0,1{\}}^4$ について
$$f(\overline{x})=\overline{f(x)}$$
が成り立つことをいう。自己双対な $4$ 変数のブール関数の個数を求めよ。

$\Sigma =\{0,1\}$ とし、${\Sigma }^{\ast }$ を空列 $\epsilon$ を含む $\Sigma$ 上の有限列全体、$|p|$ を列 $p$ の長さ、${\Sigma }^6$ を長さ $6$ の列全体とする。

部分関数 $V:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$（定義されない入力があってもよい）を記述方式とよび、$x\in {\Sigma }^{\ast }$ に対して
$$C_V(x)=\min \{|p|:V(p)=x\}$$
と定める（$V(p)=x$ となる $p$ がなければ $C_V(x)=\infty$ とする）。

記述方式 $V$ をいろいろに選ぶとき、$C_V(x)\le 3$ をみたす $x\in {\Sigma }^6$ の個数のとりうる最大値を求めよ。

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、関数 $B:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ を、すべての $m,n\in \mathbb{N}$ について次の式で定める。
$$B(0,n)=n+2,$$
$$B(m+1,0)=B(m,1),$$
$$B(m+1,n+1)=B(m,B(m+1,n)).$$
$B(2,3)$ の値を求めよ。

型なしラムダ計算を考える。適用は左結合（$MNL=(MN)L$）、抽象は右に最大限のびるものとし、$\alpha$ 同値な項は同一視する。簡約は $\beta$ 簡約のみを考える。$0$ 以上の整数 $n$ に対してチャーチ数を
$$c_n=\lambda f.\lambda x.f^{n}x(f^{0}x=x,f^{n+1}x=f(f^{n}x))$$
と定め、対と射影を
$$P=\lambda a.\lambda b.\lambda z.zab,{\pi }_1=\lambda a.\lambda b.a,{\pi }_2=\lambda a.\lambda b.b$$
と定める。さらに
$$G=\lambda p.P(p{\pi }_2)(c_2(p{\pi }_1))$$
とおき、項
$$M=c_{3}G(P{c}_2{c}_3){\pi }_2$$
を考える。$M$ の $\beta$ 正規形はあるチャーチ数 $c_k$ である。$k$ を求めよ。

互いに異なる $3$ つの原子型 $p,q,r$ をもち、定数をもたない単純型付きラムダ計算（チャーチ流）を考える。型は
$$\tau ::=p\mid q\mid r\mid (\tau \to \tau )$$
で生成される式とし、括弧の付け方（木としての形）が異なる型や、原子型の並びが異なる型は異なる型とみなす（たとえば $((p\to q)\to r)$ と $(p\to (q\to r))$ は異なる型であり、$(p\to q)$ と $(q\to p)$ も異なる型である）。

記号 $\to$ をちょうど $3$ 個含む型の個数を求めよ。

$\Sigma =\{0,1\}$ とし、言語とは ${\Sigma }^{\ast }$ の部分集合のこととする。チューリング機械 $M$ と入力 $w\in {\Sigma }^{\ast }$ の組の符号化を $⟨M,w⟩\in {\Sigma }^{\ast }$ と書き、停止問題を
$$\mathrm{HALT}=\{⟨M,w⟩\mid M\text{ は入力 }w\text{ に対して停止する}\}$$
と定める（正しい符号化になっていない列は $\mathrm{HALT}$ に属さないものとする）。$\overline{\mathrm{HALT}}={\Sigma }^{\ast }\setminus \mathrm{HALT}$ とする。

言語 $A,B$ について、$A{\le }_{m}B$ とは、計算可能な全域関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ で、すべての $x\in {\Sigma }^{\ast }$ について $x\in A⟺f(x)\in B$ となるものが存在することとする。また、言語 $L$ が帰納的可算であるとは、$L$ のちょうどすべての元に対して停止して受理するチューリング機械（$L$ に属さない入力に対しては受理しない）が存在することとする。

次のア〜カのうち、正しいものをすべて選べ。

ア　$\mathrm{HALT}$ は帰納的可算である。

イ　$\overline{\mathrm{HALT}}$ は帰納的可算である。

ウ　$\mathrm{HALT}$ は決定可能である。

エ　任意の決定可能な言語 $A$ について $A{\le }_m\mathrm{HALT}$ が成り立つ。

オ　ある決定可能な言語 $A$ について $\mathrm{HALT}{\le }_{m}A$ が成り立つ。

カ　$\overline{\mathrm{HALT}}{\le }_m\mathrm{HALT}$ が成り立つ。

関数 $f(n)$ に対し、$\mathrm{SPACE}(f(n))$ は決定性チューリング機械で領域 $O(f(n))$ で判定できる言語のクラス、$\mathrm{NSPACE}(f(n))$ は非決定性チューリング機械で領域 $O(f(n))$ で判定できる言語のクラス、$\mathrm{coNSPACE}(f(n))=\{\overline{A}\mid A\in \mathrm{NSPACE}(f(n))\}$ とする。また $\mathrm{NL}=\mathrm{NSPACE}(\log n)$、$\mathrm{coNL}=\mathrm{coNSPACE}(\log n)$ とし、$\mathrm{P},\mathrm{PSPACE},\mathrm{NPSPACE},\mathrm{EXP}$ は標準的な定義（多項式時間・多項式領域・非決定性多項式領域・決定性指数時間 $2^{n^{O(1)}}$）に従うものとする。$⊊$ は真の包含を表す。

次のア〜カの主張は、いずれもサヴィッチの定理・イマーマン–セレプチェニの定理・領域階層定理・時間階層定理によって、正しいか誤りかが確定する。このうち正しいものをすべて選べ。

ア　$\mathrm{NL}⊊\mathrm{PSPACE}$

イ　$\mathrm{NPSPACE}\subseteq \mathrm{PSPACE}$

ウ　$\mathrm{P}=\mathrm{EXP}$

エ　$\mathrm{NL}=\mathrm{coNL}$

オ　$\mathrm{SPACE}(n)=\mathrm{SPACE}(n^2)$

カ　$\mathrm{NSPACE}(n)=\mathrm{coNSPACE}(n)$

$4$ 変数のブール関数とは写像 $f:\{0,1{\}}^4\to \{0,1\}$ のこととする。入力 $x_1,x_2,x_3,x_4$ をもつブール回路を次のように定める。
- 回路は有向非巡回グラフで、$4$ つの入力ノード $x_1,x_2,x_3,x_4$ と、いくつかのゲートからなる。
- 各ゲートは $2$ 入力で、$16$ 個ある $2$ 変数ブール関数 $\{0,1{\}}^2\to \{0,1\}$ のどれを割り当ててもよい（定数関数や片方の入力だけによる関数も含む）。ゲートの $2$ つの入力は、入力ノードまたはそれより前のゲートであり、同じノードを $2$ つの入力に使ってもよい。
- ノードのうち $1$ つ（入力ノードでもゲートでもよい）を出力として指定し、その値を回路が計算する関数とする。
- 回路の大きさとは、ゲートの個数のことである。

大きさ $1$ 以下の回路で計算できる $4$ 変数のブール関数の個数を求めよ。

型なしラムダ計算で、$0$ 以上の整数 $n$ のチャーチ数を
$$\underline{n}=\lambda f.\lambda x.\underset{n\text{ 個}}{\underbrace{f(f(\cdots (f}}x)\cdots ))$$
と定める。関数適用は左結合とし、$MNP$ は $(MN)P$ を表す。

ラムダ項 $\underline{7}\underline{7}\underline{7}$ は $\beta$ 簡約によって、あるチャーチ数 $\underline{N}$ を正規形にもつ。この $N$ を $100$ で割った余りを求めよ。

互いに異なる $2$ つの原子型 $a,b$ をもち、定数をもたない単純型付きラムダ計算（チャーチ流）を考える。矢印型は右結合（$A\to B\to C=A\to (B\to C)$）とし、$\alpha$ 同値な項は同一視する。型
$$T=(a\to a\to b)\to (a\to b)\to a\to a\to b$$
をもつ閉じた項で、η 長 β 正規形であるものの個数を求めよ。

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

$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$ のすべてに本質的に依存するものの個数を求めよ。

$\Sigma =\{0,1\}$ とし、言語とは ${\Sigma }^{\ast }$（空列を含む $\Sigma$ 上の有限列全体）の部分集合のこととする。言語 $A$ の補集合を $\overline{A}={\Sigma }^{\ast }\setminus A$ と書く。言語 $A,B$ に対し、多項式時間で計算できる全域関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ であって、すべての $x\in {\Sigma }^{\ast }$ について
$$x\in A⟺f(x)\in B$$
をみたすものが存在するとき、$A{\le }_{p}B$（多項式時間多対一帰着可能）と書く。$\mathrm{P}$ は決定性チューリング機械で多項式時間で判定できる言語のクラス、$\mathrm{EXP}$ はある $k$ について時間 $2^{O(n^k)}$ で判定できる言語のクラスとする。

次のア〜カのうち、正しい（証明できる）ものをすべて選べ。ただし、ア〜オでは $A,B,C$ は任意の言語とする。

ア. $A{\le }_{p}B$ かつ $B\in \mathrm{P}$ ならば $A\in \mathrm{P}$ である。

イ. $A{\le }_{p}B$ かつ $A\in \mathrm{P}$ ならば $B\in \mathrm{P}$ である。

ウ. $A{\le }_{p}B$ かつ $B{\le }_{p}C$ ならば $A{\le }_{p}C$ である。

エ. $A{\le }_{p}B$ ならば $\overline{A}{\le }_p\overline{B}$ である。

オ. $A\in \mathrm{P}$ ならば、任意の言語 $B$ について $A{\le }_{p}B$ である。

カ. $\mathrm{P}⊊\mathrm{EXP}$ である。

$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).$$

型なしラムダ計算を考える。適用は左結合（$MNL=(MN)L$）、抽象は右に最大限のびるものとし、$\alpha$ 同値な項は同一視する。簡約は $\beta$ 簡約のみを考える（$\eta$ 簡約は考えない）。$0$ 以上の整数 $n$ に対してチャーチ数を $$c_n=\lambda f.\lambda x.\underset{n\text{ 個}}{\underbrace{f(f(\cdots (f}}x)\cdots ))$$ と定め（$c_0=\lambda f.\lambda x.x$）、項 $P$ を $$P=\lambda m.\lambda n.\lambda f.\lambda x.m(nf)(mfx)$$ と定める。項 $$N=P(c_2{c}_3)c_2$$ は $\beta$ 正規形をもち、それはあるチャーチ数 $c_k$ に一致する。$k$ を求めよ。

原子型として $o$ ただ 1 つをもち、定数をもたない単純型付きラムダ計算（チャーチ流）を考える。型は $$\tau ::=o\mid (\tau \to \tau )$$ で生成される式とし、括弧の付け方（木としての形）が異なる型は異なる型とみなす。型 $\tau$ が住人をもつとは、型 $\tau$ の閉じた項（自由変数をもたない項）が存在することをいう。

矢印 $\to$ をちょうど $5$ 個含む型（したがって $o$ をちょうど $6$ 個含む型）のうち、住人をもつものの個数を求めよ。

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

$4$ 変数のブール関数とは写像 $f:\{0,1{\}}^4\to \{0,1\}$ のこととし、$\{0,1\}$ を 2 元体 ${\mathbb{F}}_2$ と同一視する。各 $4$ 変数のブール関数 $f$ は、${\mathbb{F}}_2$ 上の多項式として
$$f(x_1,x_2,x_3,x_4)=\sum _{S\subseteq \{1,2,3,4\}}{a}_S\prod _{i\in S}{x}_i(a_S\in {\mathbb{F}}_2)$$
の形にただ 1 通りに表される（代数的標準形。$S=\varnothing$ のときの積は $1$ とする）。$a_S=1$ となる $S$ の要素の個数 $|S|$ の最大値を $f$ の次数とよぶ（恒等的に $0$ の関数の次数は $-\infty$ とする）。

次数がちょうど $2$ である $4$ 変数のブール関数の個数を求めよ。

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

型なしラムダ計算を考える。適用は左結合（$MNL=(MN)L$）、抽象は右に最大限のびるものとし、$\alpha$ 同値な項は同一視する。簡約は $\beta$ 簡約のみを考える。$0$ 以上の整数 $n$ に対してチャーチ数を
$$c_n=\lambda f.\lambda x.\underset{n\text{個}}{\underbrace{f(f(\cdots (f}}x)\cdots ))$$
と定め、右辺の本体を $f^{n}x$ と書く（$f^{0}x=x$）。

項
$$M=(c_3{c}_2)(c_2{c}_3)$$
は $\beta$ 正規形をもち、その正規形は、ある $0$ 以上の整数 $k$ に対して $\lambda f.\lambda x.f^{k}x$ と $\alpha$ 同値になる。この $k$ を求めよ。

$\Sigma =\{0,1\}$ とし、言語とは ${\Sigma }^{\ast }$ の部分集合のこととする。言語 $A,B$ に対し、$A{\le }_{p}B$ は $A$ が $B$ に多項式時間多対一帰着（カープ帰着）可能であること、すなわち多項式時間で計算できる全域関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ で、すべての $x\in {\Sigma }^{\ast }$ について $x\in A⟺f(x)\in B$ となるものが存在することを表す。$\mathrm{NP}$ 完全性はこの ${\le }_p$ に関するものとする。$\mathrm{L}$, $\mathrm{P}$, $\mathrm{NP}$, $\mathrm{PSPACE}$, $\mathrm{NPSPACE}$ は標準的な計算量クラスとする。

次の主張のうち、（未解決問題の答えによらず）正しいと証明されているものをすべて選べ。

• ア　すべての言語 $A,B$ について、$A{\le }_{p}B$ かつ $B\in \mathrm{P}$ ならば $A\in \mathrm{P}$ である。
• イ　すべての言語 $A,B$ について、$A{\le }_{p}B$ かつ $A\in \mathrm{P}$ ならば $B\in \mathrm{P}$ である。
• ウ　すべての言語 $A,B$ について、$A$ が $\mathrm{NP}$ 完全で、$B\in \mathrm{NP}$ かつ $A{\le }_{p}B$ ならば、$B$ は $\mathrm{NP}$ 完全である。
• エ　$\mathrm{L}=\mathrm{PSPACE}$ である。
• オ　$\mathrm{NPSPACE}=\mathrm{PSPACE}$ である。
• カ　すべての言語 $A,B$ について、$A{\le }_{p}B$ ならば $B{\le }_{p}A$ である。

この問題では $\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とする。関数 $A:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ を次の再帰式で定める（アッカーマン・ペーター関数）。
$$A(0,n)=n+1,A(m+1,0)=A(m,1),A(m+1,n+1)=A(m,A(m+1,n))(m,n\in \mathbb{N}).$$
この再帰式によって $A$ がすべての $(m,n)\in \mathbb{N}\times \mathbb{N}$ で一意に定まる全域関数であることは用いてよい。

すべての $n\in \mathbb{N}$ に対して
$$A(3,n)=2^{n+3}-3$$
が成り立つことを証明せよ。

$n$ を正の整数とし、変数 $x_1,\dots ,x_n$ のブール回路を次のように定める。大きさ $s$（$s\ge 1$）の回路とは、ゲートの列 $g_1,g_2,\dots ,g_s$ であって、各ゲート $g_i$ が
- 種類 $\mathrm{AND}$, $\mathrm{OR}$, $\mathrm{NOT}$ のいずれか 1 つと、
- 入力として、$\mathrm{AND}$, $\mathrm{OR}$ のときは $x_1,\dots ,x_n,g_1,\dots ,g_{i-1}$ の中から選んだ順序付きの 2 つ組 $(u_i,v_i)$（$u_i=v_i$ も許す）、$\mathrm{NOT}$ のときは同じ候補の中から選んだ 1 つの $u_i$

をもつものとする。入力 $a\in \{0,1{\}}^n$ に対し、$x_j$ の値を $a_j$ とし、$g_1,g_2,\dots$ の順に、$g_i$ の値を $u_i,v_i$ の値の論理積・論理和、または $u_i$ の値の否定として定める。回路が計算する関数とは、$a$ に最後のゲート $g_s$ の値を対応させる関数 $\{0,1{\}}^n\to \{0,1\}$ のことである。

関数 $f:\{0,1{\}}^n\to \{0,1\}$ が変数 $x_j$ に依存するとは、第 $j$ 成分だけが異なる $a,a^{\prime }\in \{0,1{\}}^n$ で $f(a)\ne f(a^{\prime })$ となるものが存在することをいう。

$f$ がすべての変数 $x_1,\dots ,x_n$ に依存するとき、$f$ を計算するどの回路においても、種類が $\mathrm{AND}$ または $\mathrm{OR}$ であるゲートの個数は $n-1$ 以上であることを証明せよ。

型なしラムダ計算を考え、項は $\alpha$ 同値なものを同一視する。適用 $MN$ は $M$ を関数、$N$ を引数とする適用を表し、適用は左結合とする（$MNP=(MN)P$）。代入 $M[z:=N]$ は変数の捕獲を起こさない代入（必要なら束縛変数を付け替える）とする。${\to }_{\beta }$ を 1 ステップの $\beta$ 簡約（任意の部分項で行ってよい）、${\twoheadrightarrow }_{\beta }$ をその反射推移閉包とする。$\beta$ 基（$(\lambda z.P)Q$ の形の部分項）を含まない項を $\beta$ 正規形といい、$M{\twoheadrightarrow }_{\beta }N$ となる $\beta$ 正規形 $N$ を $M$ の $\beta$ 正規形という。

項 $F,X$ と $0$ 以上の整数 $k$ に対して $F^{0}X=X$, $F^{k+1}X=F(F^{k}X)$ と定め、$0$ 以上の整数 $k$ のチャーチ数を
$$c_k=\lambda f.\lambda x.f^{k}x$$
とする（$f$, $x$ は異なる変数）。さらに、互いに異なる変数 $a,f,x$ を用いて
$$S=\lambda a.\lambda f.\lambda x.af(af(fx))$$
と定める。

チャーチ・ロッサーの定理（したがって、ある項が $\beta$ 正規形をもつならそれは一意であること）は用いてよい。

$n$ を $0$ 以上の整数とするとき、項 $c_{n}S{c}_0$ の $\beta$ 正規形が $c_{2^n-1}$ であることを証明せよ。

$3$ 変数のブール関数とは写像 $f:\{0,1{\}}^3\to \{0,1\}$ のこととする。入力 $x_1,x_2,x_3$ をもつ基底 $B_2$ 上のブール回路を次のように定める。

• 回路は有向非巡回グラフで、入力ノード $x_1,x_2,x_3$ と、いくつかのゲートからなる（定数の入力ノードはもたない）。
• 各ゲートは $2$ 入力の任意のブール関数 $\{0,1{\}}^2\to \{0,1\}$（全 $16$ 個のどれでもよい）を計算し、その $2$ つの入力はそれより前にある入力ノードまたはゲートの出力である（$2$ つの入力が同じノードでもよい）。
• 回路のノード（入力ノードでもゲートでもよい）を $1$ つ選んで出力とし、そのノードが計算する関数を回路が計算する関数とする。
• 回路の大きさはゲートの個数とする。

$3$ 変数のブール関数 $f$ に対し、$f$ を計算する回路の大きさの最小値を $C(f)$ とする。$C(f)\le 2$ を満たす $3$ 変数のブール関数 $f$ の個数を求めよ。

型なしラムダ計算を考える。適用は左結合（$MNL=(MN)L$）、抽象は右に最大限のびるものとし、$\alpha$ 同値な項は同一視する。簡約は $\beta$ 簡約のみを考える（$\eta$ 簡約は考えない）。$0$ 以上の整数 $n$ に対してチャーチ数を
$$c_n=\lambda f.\lambda x.\underset{n\text{個}}{\underbrace{f(f(\cdots (f}}x)\cdots ))$$
で定める。

正規順序戦略とは、各ステップで、項に含まれる $\beta$ 基（$(\lambda v.P)Q$ の形の部分項）のうち最も左外側にあるもの（項を文字列として書いたときに、その $\beta$ 基の先頭が最も左にあるもの）を 1 回だけ縮約する戦略である。

項 $c_3{c}_2$ から出発して正規順序戦略で $\beta$ 簡約を繰り返すと、有限回で $\beta$ 正規形に到達する。正規形に到達するまでに行われる $\beta$ 簡約の回数（ステップ数）を求めよ。

互いに異なる $2$ つの原子型 $a,b$ をもち、定数をもたない単純型付きラムダ計算（チャーチ流）を考える。型は
$$\tau ::=a\mid b\mid (\tau \to \tau )$$
で生成される式とする。括弧の付け方（木としての形）または原子型の配置が異なる型は、異なる型とみなす。$\to$ は右結合とし、型に現れる $\to$ の個数をその型の矢印数とよぶ。

型 $\tau$ の住人とは、型 $\tau$ をもつ閉項であって、$\beta$ 正規形かつ $\eta$ 長形（long normal form）であるもののこととする。住人は $\alpha$ 同値なものを同一視して数える。

矢印数がちょうど $3$ である型のうち、住人をちょうど $1$ つだけもつ型の個数を求めよ。

$\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$ の長さとする。

部分関数 $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$ に含まれる圧縮不可能な列の個数の最小値を求めよ。

$0$ 以上の整数全体を ${\mathbb{N}}_0$ とする。関数 $B:{\mathbb{N}}_0\times {\mathbb{N}}_0\to {\mathbb{N}}_0$ を、すべての $m,n\in {\mathbb{N}}_0$ に対して
$$B(0,n)=n+2,$$
$$B(m+1,0)=B(m,1),$$
$$B(m+1,n+1)=B(m,B(m+1,n))$$
を満たすものとして（アッカーマン関数と同様の二重帰納法で）定める。$B(3,1)$ の値を求めよ。

アルファベットを $\Sigma =\{0,1\}$ とし、言語とは ${\Sigma }^{\ast }$ の部分集合のこととする。言語 $A,B$ について、多項式時間で計算できる関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ で、すべての $x\in {\Sigma }^{\ast }$ に対して $x\in A⟺f(x)\in B$ をみたすものが存在するとき $A{\le }_{p}B$ と書く（多項式時間多対一帰着）。NP 完全性はこの ${\le }_p$ に関するものとする。また、$\mathrm{SAT}$ は CNF 論理式の充足可能性問題、$\mathrm{HALT}=\{⟨M,x⟩\mid \text{チューリング機械 }M\text{ は入力 }x\text{ で停止する}\}$ は停止問題（$\Sigma$ 上の適当な符号化によるもの）とする。

次のア〜カのうち、（未解決問題の仮定を一切用いずに）正しいと証明されている命題をすべて選べ。

ア. $A{\le }_{p}B$ かつ $B\in \mathrm{NP}$ ならば $A\in \mathrm{NP}$ である。

イ. $A{\le }_{p}B$ かつ $A\in \mathrm{P}$ ならば $B\in \mathrm{P}$ である。

ウ. $\mathrm{P}⊊\mathrm{EXP}$ である。

エ. $\mathrm{HALT}{\le }_p\mathrm{SAT}$ である。

オ. ある NP 完全な言語 $L$ が $\mathrm{coNP}$ に属するならば、$\mathrm{NP}=\mathrm{coNP}$ である。

カ. $A\in \mathrm{P}$ であり、$B$ が $B\ne \varnothing$ かつ $B\ne {\Sigma }^{\ast }$ をみたす任意の言語（決定可能でなくてもよい）ならば、$A{\le }_{p}B$ である。

入力変数を $x_1,x_2,x_3$ とするブール回路を考える。ゲートとしては 2 入力のブール関数 $\{0,1{\}}^2\to \{0,1\}$ をすべて（16 個。定数関数や片方の入力だけによる関数も含む）使ってよく、各ゲートの 2 つの入力には入力変数 $x_1,x_2,x_3$ またはそれより前のゲートの出力を（同じものを 2 回使うことも含めて）つなぐ。定数は入力として与えられない。回路の出力は、入力変数またはゲートのどれか 1 つの値とし、回路の大きさはゲートの個数とする。

ブール関数 $f:\{0,1{\}}^3\to \{0,1\}$ のうち、大きさ $2$ 以下の回路で計算できるものの個数を求めよ。

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、関数 $G:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ を次の再帰で定める（アッカーマン関数の変形である）。すべての $m,n\in \mathbb{N}$ に対して
$$G(0,n)=n+1,$$
$$G(m+1,0)=G(m,2),$$
$$G(m+1,n+1)=G(m,G(m+1,n)).$$
この再帰は $(m,n)$ の辞書式順序に関する整礎帰納法によりすべての $(m,n)$ で値が定まる。$n$ を $0$ 以上の整数とするとき、$G(3,n)$ を $n$ の式で表せ。

言語はすべてアルファベット $\Sigma =\{0,1\}$ 上の言語（${\Sigma }^{\ast }$ の部分集合）とする。言語 $A,B$ に対し、$A{\le }_{p}B$ は多項式時間多対一帰着（カープ帰着）が存在すること、すなわち多項式時間で計算できる関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ で、すべての $x\in {\Sigma }^{\ast }$ について $x\in A⟺f(x)\in B$ となるものが存在することを表す。NP 完全性はこの ${\le }_p$ に関して定める（$\mathrm{NP}$ に属し、$\mathrm{NP}$ のすべての言語が ${\le }_p$ で帰着されること）。また $\mathrm{EXP}={\bigcup }_{k\ge 1}\mathrm{DTIME}(2^{n^k})$、$\mathrm{NL}$ は非決定性対数領域で判定できる言語のクラス、$\mathrm{PSPACE}$ は決定性多項式領域で判定できる言語のクラスとし、$\mathrm{HALT}$ はチューリング機械の停止問題（決定不能である）を表す言語とする。

次のア〜キのうち、正しい（現在知られている結果から真であることが証明されている）ものをすべて選べ。

ア. 任意の言語 $A,B$ について、$A{\le }_{p}B$ かつ $B\in \mathrm{P}$ ならば $A\in \mathrm{P}$ である。

イ. 任意の言語 $A,B$ について、$A{\le }_{p}B$ かつ $A\in \mathrm{NP}$ ならば $B\in \mathrm{NP}$ である。

ウ. 任意の言語 $B,C$ について、$B$ が NP 完全で、$B{\le }_{p}C$ かつ $C\in \mathrm{NP}$ ならば、$C$ は NP 完全である。

エ. $\mathrm{P}⊊\mathrm{EXP}$ である。

オ. 任意の言語 $A,B$ について、$A{\le }_{p}B$ ならば $B{\le }_{p}A$ である。

カ. $\mathrm{NL}⊊\mathrm{PSPACE}$ である。

キ. $\mathrm{P}$ に属するすべての言語は NP 完全である。

型なしラムダ計算を考える。適用は左結合（$MNL=(MN)L$）、抽象は右に最大限のびるものとし、$\alpha$ 同値な項は同一視する。簡約は $\beta$ 簡約のみを考える（$\eta$ 簡約は考えない）。$0$ 以上の整数 $n$ に対してチャーチ数を
$$c_n=\lambda f.\lambda x.\underset{n\text{個}}{\underbrace{f(f(\cdots (f}}x)\cdots ))$$
と定める（$c_0=\lambda f.\lambda x.x$）。さらに次の項を定める。
$$S=\lambda n.\lambda f.\lambda x.f(nfx),M=\lambda m.\lambda n.\lambda f.m(nf),$$
$$P=\lambda a.\lambda b.\lambda s.sab,K=\lambda a.\lambda b.a,K^{\prime }=\lambda a.\lambda b.b,$$
$$T=\lambda p.P(p{K}^{\prime })(S(M(pK)(p{K}^{\prime }))).$$
このとき項
$$N=c_2{c}_{2}T(P{c}_1{c}_1)K^{\prime }$$
は $\beta$ 正規形をもち、それはあるチャーチ数 $c_k$ に一致する。整数 $k$ を求めよ。

$\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$ を含む有限 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$$
が成り立つことを証明せよ。

原子型を $o$ ただ 1 つだけもつ単純型付きラムダ計算（チャーチ流、定数なし）を考える。矢印型は右結合（$A\to B\to C=A\to (B\to C)$）とし、$\alpha$ 同値な項は同一視する。型
$$\tau =(o\to o\to o)\to ((o\to o)\to o)\to o$$
の閉じた項で、$\beta$ 正規形かつ $\eta$ 長形（$\beta$-normal $\eta$-long form）であるものは、ある項 $M$ を用いて $\lambda f^{o\to o\to o}.\lambda G^{(o\to o)\to o}.M$ の形に書ける。このような項のうち、$M$ の中に変数 $f$ と $G$ が合わせてちょうど $4$ 回出現するもの（$f$ の出現回数と $G$ の出現回数の和が $4$）の個数を求めよ。

$\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$ 上の有限列全体）の部分集合のこととする。言語 $A,B$ について、$A{\le }_{p}B$ とは、多項式時間で計算できる全域関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ であって、すべての $x\in {\Sigma }^{\ast }$ に対して $x\in A⟺f(x)\in B$ を満たすものが存在することとする。クラス $\mathcal{C}$ に対して、言語 $A$ が $\mathcal{C}$ 困難であるとは、すべての $L\in \mathcal{C}$ について $L{\le }_{p}A$ が成り立つことをいう。$A$ が $\mathcal{C}$ 困難であり、かつ $A\in \mathcal{C}$ であるとき、$A$ は $\mathcal{C}$ 完全であるという。計算モデルは多テープの決定性・非決定性チューリング機械とし、$\mathrm{P},\mathrm{NP},\mathrm{EXP}={\bigcup }_{k\ge 1}\mathrm{DTIME}(2^{n^k}),\mathrm{NL},\mathrm{PSPACE},\mathrm{NPSPACE}$ は通常の意味の計算量クラスとする。また、停止問題を $\mathrm{HALT}=\{⟨M,w⟩:\text{決定性チューリング機械 }M\text{ は入力 }w\text{ で停止する}\}$ とする。ここで $⟨\cdot ,\cdot ⟩$ は機械と入力の組の標準的な符号化（符号化と記述の相互変換が多項式時間でできるもの）であり、正しい符号化になっていない列は $\mathrm{HALT}$ に属さないものとする。

次のア〜カのうち、（未解決問題の仮定なしに）正しいと証明されている主張をすべて選べ。

ア. $\varnothing$ でも ${\Sigma }^{\ast }$ でもない任意の言語 $A\in \mathrm{P}$ は $\mathrm{P}$ 完全である。

イ. 空集合 $\varnothing$ は $\mathrm{NP}$ 困難である。

ウ. $\mathrm{HALT}$ は $\mathrm{NP}$ 困難である。

エ. $\mathrm{PSPACE}⊊\mathrm{NPSPACE}$ である。

オ. $\mathrm{EXP}$ 完全な言語であって $\mathrm{P}$ に属するものが存在する。

カ. $\mathrm{NL}⊊\mathrm{PSPACE}$ である。

変数 $x_1,x_2,x_3,x_4$ を用いる論理式を、次の規則で帰納的に定める。

• 各 $x_i$ $(1\le i\le 4)$ は論理式である。
• $\phi ,\psi$ が論理式ならば、$\neg \phi$、$(\phi \wedge \psi )$、$(\phi \vee \psi )$ も論理式である。

定数記号 $0,1$ は用いない。論理式に $x_1,x_2,x_3,x_4$ を代入すると、写像 $\{0,1{\}}^4\to \{0,1\}$ が定まる。現れない変数には依存しない関数とみなす。

各変数 $x_i$ の出現回数がどれも高々 $1$ 回である論理式を、リードワンス論理式とよぶ。写像 $f:\{0,1{\}}^4\to \{0,1\}$ のうち、あるリードワンス論理式で表されるものの個数を求めよ。

アルファベットを $\Sigma =\{0,1\}$ とし、言語は ${\Sigma }^{\ast }$ の部分集合とする。$A{\le }_{p}B$ は多項式時間多対一帰着が存在することを表す（多項式時間で計算できる全域関数 $f$ で、すべての $x$ について $x\in A⟺f(x)\in B$ となるものがある）。$\mathrm{P},\mathrm{NP},\mathrm{NL},\mathrm{coNL},\mathrm{PSPACE},\mathrm{NPSPACE},\mathrm{EXP}$ は通常の多テープチューリング機械による計算量クラスとする。$\mathrm{HALT}$ はチューリング機械 $M$ と入力 $w$ の符号 $⟨M,w⟩$ のうち $M$ が $w$ で停止するもの全体（符号になっていない列は含まない）、$\mathrm{TQBF}$ は真である閉じた量化ブール式（冠頭形）の符号全体とする。

次のア〜キのうち、正しいと証明されている主張をすべて選べ。

ア. 任意の言語 $A,B$ について、$A{\le }_{p}B$ かつ $B\in \mathrm{NP}$ ならば $A\in \mathrm{NP}$ である。

イ. 任意の言語 $A,B$ について、$A{\le }_{p}B$ かつ $A\in \mathrm{P}$ ならば $B\in \mathrm{P}$ である。

ウ. $\mathrm{NL}=\mathrm{coNL}$ である。

エ. $\mathrm{TQBF}\in \mathrm{NL}$ である。

オ. $\mathrm{HALT}$ は ${\le }_p$ に関して $\mathrm{NP}$ 困難である（すなわち、すべての $L\in \mathrm{NP}$ について $L{\le }_p\mathrm{HALT}$）。

カ. $\mathrm{PSPACE}\ne \mathrm{NPSPACE}$ である。

キ. $\mathrm{P}⊊\mathrm{EXP}$ である。

型なしラムダ計算を考える。適用は左結合（$MNL=(MN)L$）とし、$\alpha$ 同値な項は同一視する。$0$ 以上の整数 $n$ に対してチャーチ数を
$$c_n=\lambda f.\lambda x.\underset{n\text{ 個}}{\underbrace{f(f(\cdots (f}}x)\cdots ))$$
で定める。さらに
$$P=\lambda a.\lambda b.\lambda z.zab,{\pi }_2=\lambda p.p(\lambda a.\lambda b.b),$$
$$F=\lambda p.p(\lambda a.\lambda b.Pb(ab))$$
とおき、
$$M={\pi }_2(c_{3}F(P{c}_2{c}_2))$$
とする。$M$ は $\beta$ 正規形をもち、それはあるチャーチ数 $c_k$ に一致する。$k$ を求めよ。

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、関数 $A:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$（アッカーマン・ペーター関数）を次の再帰で定める。すべての $m,n\in \mathbb{N}$ に対して
$$A(0,n)=n+1,A(m+1,0)=A(m,1),A(m+1,n+1)=A(m,A(m+1,n)).$$
このとき、$A(4,3)$ を $1000$ で割った余りを求めよ。

互いに異なる 3 つの原子型 $a,b,c$ をもつ単純型付きラムダ計算（チャーチ流、定数なし）を考える。矢印型は右結合（$A\to B\to C=A\to (B\to C)$）とし、$\alpha$ 同値な項は同一視する。型 $A$ の閉じた項のうち、$\beta$ 正規形かつ $\eta$ 長形（$\eta$-long form）であるものを $A$ の住人とよぶ。（住人は、型 $A$ の閉じた項の $\beta \eta$ 同値類と 1 対 1 に対応する。）

型
$$T=((a\to b)\to (a\to b)\to c)\to (a\to a\to b)\to (b\to c)\to a\to a\to c$$
の住人の個数を求めよ。

原子型を $o$ ただ 1 つだけもつ単純型付きラムダ計算（チャーチ流、定数なし）を考える。型は
$$\tau ::=o\mid (\tau \to \tau )$$
で生成されるものとし、括弧の付け方が異なる型は異なる型とみなす（たとえば $(o\to o)\to o$ と $o\to (o\to o)$ は異なる型である）。型 $\tau$ に含まれる記号 $\to$ の個数を $\tau$ の矢印の個数という。

型 $\tau$ をもつ閉じた項（自由変数をもたない項）が少なくとも 1 つ存在するとき、$\tau$ は住人をもつという。矢印の個数がちょうど $6$ である型のうち、住人をもつものの個数を求めよ。

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、関数 $A:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ をすべての $m,n\in \mathbb{N}$ について
$$A(0,n)=n+1,A(m+1,0)=A(m,1),A(m+1,n+1)=A(m,A(m+1,n))$$
で定める。

この定義をそのまま再帰手続きとして実行して $A(m,n)$ を計算する。すなわち、手続き $A(m,n)$ が呼ばれると、$m=0$ なら再帰呼び出しをせずに $n+1$ を返し、$m\ge 1,n=0$ なら $A(m-1,1)$ を $1$ 回呼んでその値を返し、$m\ge 1,n\ge 1$ ならまず $A(m,n-1)$ を呼んでその値 $r$ を得たのち $A(m-1,r)$ を呼んでその値を返す。最初の呼び出しも含めて、$A(m,n)$ の計算で手続き $A$ が呼ばれる回数の合計を $C(m,n)$ とする（たとえば $C(0,n)=1$、$C(1,0)=2$）。

$n\in \mathbb{N}$ に対し、$C(3,n)$ を $n$ の式で表せ。

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

$\Sigma =\{0,1\}$ とし、言語とは ${\Sigma }^{\ast }$ の部分集合のこととする。言語 $A,B$ について、$A{\le }_{p}B$ は $A$ が $B$ に多項式時間多対一帰着可能であること（多項式時間で計算できる全域関数 $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ で、すべての $x$ について $x\in A⟺f(x)\in B$ となるものが存在すること）を表す。言語 $B$ が クラス $\mathcal{C}$ に対して困難であるとは、すべての $A\in \mathcal{C}$ について $A{\le }_{p}B$ となることをいい、困難かつ $B\in \mathcal{C}$ のとき $\mathcal{C}$ 完全という。$\mathrm{HALT}$ を、チューリング機械 $M$ と入力 $w$ の組の（標準的な）符号 $⟨M,w⟩$ のうち、$M$ が $w$ 上で停止するもの全体からなる言語とする。$\mathrm{SAT}$ は充足可能な命題論理式（の符号）全体である。

次の命題のうち、正しいことが証明されているものをすべて選べ（ほかの命題はいずれも偽であることが証明されている）。

ア．任意の言語 $A,B$ について、$A{\le }_{p}B$ かつ $B\in \mathrm{NP}$ ならば $A\in \mathrm{NP}$ である。

イ．任意の言語 $A,B$ について、$A{\le }_{p}B$ かつ $A\in \mathrm{P}$ ならば $B\in \mathrm{P}$ である。

ウ．$L\in \mathrm{P}$ が $L\ne \varnothing$ かつ $L\ne {\Sigma }^{\ast }$ を満たすならば、$L$ は ${\le }_p$ に関して $\mathrm{P}$ 完全である。

エ．言語 ${\Sigma }^{\ast }$ は $\mathrm{NP}$ 困難である。

オ．$\mathrm{NL}⊊\mathrm{PSPACE}$ である。

カ．$\mathrm{HALT}$ は $\mathrm{NP}$ 困難である。

キ．${\le }_p$ に関して $\mathrm{EXP}$ 完全である言語のうち、$\mathrm{P}$ に属するものが存在する。

$\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$ の式で求めよ。