教会の数字を含むラムダ計算評価

Question

私はそれを理解しています 教会の数 $ c_n $は$ lambda sのように見えます。 Lambda Z。 s $（... n times ...）$ s ; z $。これは、「関数$ s $が$ n $ $ n $ function $ z $」にすぎないことを意味します。

$ mathtt {times} $関数の可能な定義は次のとおりです。$ mathtt {times} = lambda m。 lambda n。 lambda s。 m ; （n ; s）$。身体を見ると、機能の背後にあるロジックがわかります。しかし、私が評価を始めたとき、私は立ち往生します。例で説明します：

$$ begin {align*}（ lambda m。 lambda n。 lambdas。m;（n ; s））（ lambda s 。 lambda zs ; s ; s ; z） mspace {-4em} to^*＆ lambda s。 （ lambda s。 lambda zs ; s ; z）; （（ lambda s。 lambda zs ; s ; s ; z）; s） to^*＆ lambda s。 （ lambda s。 lambda zs ; s ; z）; （ lambda zs ; s ; s ; z） to^*＆ lambda s。 lambda z。（ lambda zs ; s ; s ; z）;（ lambda zs ; s ; s ; z）

この状況で、最初に$（ lambda zs ; s ; s ; z）; z $を適用した場合、目的の結果になります。ただし、$（ lambda zs ; s ; s ; z）私は間違った結果を得る：

$ lambda s。 lambda z。（ lambda zs ; s ; s ; z）;（ lambda zs ; s ; s ; z）; z to lambda lambda z。（s ; s ; s ;（ lambda zs ; s ; s ; z）; ; z $

私はもはやこれを減らすことができません。私は何が間違っているのですか？結果は$ lambda sになります。 lambda zs ; s ; s ; s ; s ; z $

Answer 1

あなたの削減は正しいと思います（しかし、私はそれを目で覚めただけです）。最後に、$（ lambdaz。SSSZ）$を$ z $に適用することはできません。これは用語には決して表示されません。 $ lambda z。 ffz $は$ lambda zです。 （ff）z $、$ lambda zではなく。 f（fz）$。 Lambda-Calculusの関数は、単一の引数を取ります。それらは効果的です カレー: ：2 argument関数は、最初の引数を取り、2番目の引数を取り、結果を返す新しい1つのargument関数を返す1つのargument関数として実装されます。

教会の数字を定義するとき、あなたは同じ間違いを犯しました。 $ n $の教会数字は、関数$ n $時間を作成することに基づいています。 「関数$ s $は、$ n $をfunction $ z $ z $ lambda sに適用しました。 Lambda Z。 s（s（…s ：z）…））$。あなたが書いたのは、関数$ s $ applied $ n-1 $ function $ s $に、そして最後に$ z $までです。

$ 2 times 3 $は$（ lambda mns。m（ns））（ lambda sz。s（s ：z））（ lambda sz。s（s ：z）））です。 $。 $ lambda s zに削減されることを確認させます。 s（s（s（s（s ：z）））））$。