自然数のチャーチ数エンコードは不必要に複雑ですか?
-
28-10-2019 - |
質問
私が読んでいるコンピュータプログラムの構造と解釈の本は、ゼロとインクリメント関数を定義することによってチャーチ数を示しています ジェネラコディセタグプレ
これは私にはかなり複雑に思えたので、それを理解して1つ(λf.λx. f x
)と2つ(λf.λx. f (f x)
)を導き出すのに非常に長い時間がかかりました。
代わりに、ゼロを空のラムダとして、この方法で数値をエンコードする方がはるかに簡単ではないでしょうか? ジェネラコディセタグプレ
これで、1つ(λ. λ
)と2つ(λ. λ. λ
)などを導出するのは簡単です。
これは、ラムダで数値を表すためのはるかに明白で直感的な方法のようです。このアプローチに問題があり、チャーチ数がそのように機能する正当な理由はありますか?このアプローチはすでに証明されていますか?
解決
エンコーディング(ゼロ:λx.x
、1:λx.λx.x
、2:λx.λx.λx.x
など)を使用すると、インクリメントとデクリメントを簡単に定義できますが、それを超えると、エンコーディング用のコンビネータを開発するのがかなり難しくなります。たとえば、isZero
をどのように定義しますか?
チャーチ符号化について直感的に考える方法は、数字のジェネラコディセタグコードがジェネラコディセタグコードの時間を繰り返すアクションによって表されるということです。これにより、数値にエンコードされた反復を使用するだけで、n
のようなコンビネータを簡単に開発できます。再帰のための派手なコンビネータは必要ありません。
チャーチ数化では、各数値は同じインターフェースを持ちます。2つの引数を取ります。エンコーディングでは、各数値は必要な引数の数によって定義されるため、均一に操作するのは非常に困難です。
数字をエンコードする別の方法は、数字をn= 0と考えることです。S nであり、ユニオンにはバニラエンコーディングを使用します。
他のヒント
提案された数値の構文はラムダ計算では無効ですが、チャーチ数はラムダ計算では実際に有効な構文です。したがって、チャーチ数がそのままである理由として考えられるのは、数値のエンコードがラムダ計算に準拠している必要があることです。定義は、ラムダ計算でも定義されている追加の操作(たとえば、増分)がエンコードされた数値に対して操作できるようにします。