令和5年度 III-4

解説

この問題で問われていること

チャーチ数の加算をβ簡約して、結果の自然数を求める問題。

解き方

① チャーチ数n=fをn回適用するもの。λpqfx.pf(qfx)は「fをq回適用した後、さらにp回適用」=p+q
② p=3、q=1 → fを4回適用
③ 4(④)

正解が正しい理由

チャーチ数nは、λfx.f^n(x)(関数fをx にn回適用する)を表す。λpqfx.pf(qfx)は、pとqのチャーチ数を受け取り、qfxを計算した結果に、さらにpf(f をp回適用)を作用させるもので、チャーチ数の加算(p+q)を表す。p=3、q=1を代入すると、λfx.3f(1fx)となる。1fx=f(x)、3f(y)=f(f(f(y)))なので、3f(f(x))=f(f(f(f(x))))となる。これはfを4回適用するチャーチ数の4である。したがって④が正しい。

この問題で必要な基礎

■ ラムダ式の読み方
「λx.本体」は「xを受け取って本体を返す関数」です。λpqfx.本体 は、p, q, f, x の4つを順に受け取る関数を表します。

■ 関数に値を渡す(β簡約)
ラムダ式に値を渡すことは、本体の中の変数をその値で置き換えることです。λpqfx.pf(qfx) に 3 と 1 を渡すと、pを3、qを1に置き換えて λfx.3f(1fx) になります。

■ チャーチ数の意味
問題文の定義から、チャーチ数nは「関数fを受け取り、xにfをn回適用する」ものです。つまり 1fx=f(x)、3f(y)=f(f(f(y))) です。

各選択肢について

• ① 1は、fを1回適用するチャーチ数で、3+1の結果ではない。
• ② 2は、fを2回適用するチャーチ数で、3+1の結果ではない。
• ③ 3は、加算する前のpの値である。
• ④ 3+1=4で、fを4回適用する形になり、これが正答。
• ⑤ 5は、fを5回適用するチャーチ数で、3+1の結果ではない。

覚えるべきポイント

チャーチ数n=λfx.f^n(x)。加算はλpqfx.pf(qfx)、乗算はλpqf.p(qf)で定義される。β簡約で、fの適用回数を数えて値を読み取る。