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

型なしラムダ計算を考える。適用は左結合（$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$ を求めよ。

型なしラムダ計算を考える。適用は左結合（$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$ を求めよ。

型なしラムダ計算を考える。適用は左結合（$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$ を求めよ。

型なしラムダ計算を考える。適用は左結合（$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$ を求めよ。

型なしラムダ計算を考える。適用は左結合（$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$ 正規形をもたない