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

難易度 1大学院の講義の例題レベル大学院数学計算理論・ラムダ計算

型なしラムダ計算で、 $0$ 以上の整数 $n$ のチャーチ数を
$n = λ f . λ x . n 個 f (f (\dots (f x) \dots))$
と定める。関数適用は左結合とし、 $M N P$ は $(M N) P$ を表す。

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

この問題で使うもの

べきの塔の剰余（説明と入口の問題）

この問題を解けるようになるまで（35 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

まずチャーチ数どうしの適用 $m n$ がどのチャーチ数に簡約されるかを調べ、左結合に注意して項全体を一つのチャーチ数にしよう。

ヒント 2

$m n \to_{β} n^{m}$ である。すると $N$ はべきの塔になるので、オイラーの定理（ $φ (100) = 40$ ）で指数を $40$ を法として下げる。

ヒント 3

$(77) 7 \to_{β} 7^{7^{7}}$ で、 $7^{7} \equiv 23 (mod 40)$ である。あとは $7^{23} mod 100$ を $7^{4} \equiv 1 (mod 100)$ を使って計算する。

答えと解説

答えを見る

43

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

手順 1: チャーチ数どうしの適用を計算する。
$f^{k} x$ で $f (f (\dots (f x) \dots))$ （ $f$ が $k$ 個）を表すと、 $n g \to_{β} λ x . g^{n} x$ である。

まず $n h$ と $n (n h)$ を比べる。 $n h = λ y . h^{n} y$ なので、これを $n$ 回合成すると $h^{n}$ が $n$ 回重なって $h^{n^{2}}$ になる。一般に、 $n$ を $h$ に $m$ 回繰り返し適用したものは $λ y . h^{n^{m}} y$ である。

したがって
$m n \to_{β} λh . n^{m} h \to_{β} λh . λ y . h^{n^{m}} y = n^{m}$
となる（ $n^{m} h$ は $n$ を $h$ に $m$ 回繰り返し適用したもの）。

手順 2: 与えられた項を簡約する。
左結合なので $777 = (77) 7$ である。手順 1 より
$77 \to_{β} 7^{7}, 7^{7} 7 \to_{β} 7^{(7^{7})}$
よって $N = 7^{7^{7}} = 7^{(7^{7})}$ である。正規形は合流性（チャーチ–ロッサーの定理）により一意なので、 $N$ も一意に決まる。

手順 3: 指数を $φ (100)$ で下げる。
$g cd (7, 100) = 1$ 、 $φ (100) = 100 (1 - \frac{1}{2}) (1 - \frac{1}{5}) = 40$ なので、オイラーの定理より $7^{40} \equiv 1 (mod 100)$ 。よって $7^{7}$ を $40$ で割った余り $r$ が分かれば $N \equiv 7^{r} (mod 100)$ である。

$40$ を法として
$7^{2} = 49 \equiv 9, 7^{3} \equiv 63 \equiv 23, 7^{4} \equiv 23 \cdot 7 = 161 \equiv 1 (mod 40)$
なので $7^{7} = 7^{4} \cdot 7^{3} \equiv 23 (mod 40)$ 、すなわち $r = 23$ 。

手順 4: $7^{23} mod 100$ を求める。
$7^{4} = 2401 \equiv 1 (mod 100)$ なので
$7^{23} = (7^{4})^{5} \cdot 7^{3} \equiv 343 \equiv 43 (mod 100)$

したがって、求める余りは $43$ である。

別解

チャーチ数 $m n$ は $λ x . n (n (\dots n x))$ （ $n$ を $m$ 個）に簡約される。 $n$ は $f$ を $n$ 回適用する操作なので、これを $m$ 回繰り返すと $f$ を $n^{m}$ 回適用する。よって $m n \to_{β} n^{m}$ （指数）。

左結合より $777 = (77) 7$ 。内側は $77 \to 7^{7} = 823543$ 。さらに $8235437 \to 7^{823543}$ 。したがって $N = 7^{823543}$ 。

$7^{2} = 49$ 、 $7^{3} = 343 \equiv 43$ 、 $7^{4} = 2401 \equiv 1 (mod 100)$ より、 $7$ の冪は周期 $4$ 。 $823543 \equiv 43 \equiv 3 (mod 4)$ （下 2 桁 $43 = 4 \cdot 10 + 3$ ）なので $N \equiv 7^{3} \equiv 43 (mod 100)$ 。

検算: $7^{7} = 823543$ は $7^{2} = 49, 7^{3} = 343, 7^{4} = 2401, 7^{5} = 16807, 7^{6} = 117649, 7^{7} = 823543$ で確認。 $7^{3} = 343$ の下 2 桁は 43。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる