追加のための教会数

StackOverflow https://stackoverflow.com/questions/3077908

  •  28-09-2019
  •  | 
  •  

質問

私は次のステップで立ち往生しています。誰かが私を助けてくれるなら、それは素晴らしいことです：

2 = λfx.f(f x)
3 = λfx.f(f(f x))
ADD = λm n f x. m f (n f x)

私のステップは次のとおりです。

   (λm n f x. m f (n f x)) (λf x.f(f(f x))) (λf x.f(f x))
-> ((λn f x. (λf x.f(f(f x))) f (n f x))) (λf x.f(f x))
-> ((λf x. (λf' x'.f'(f'(f' x'))) f ((λf" x".f"(f" x")) f x)

括弧は大丈夫ですか？私は本当に代替と括弧で自分自身を混乱させます。そのような問題に対処するための正式で簡単なテクニックはありますか？

役に立ちましたか？

解決

試す ワニの卵！

これが私のステップです。ワニの卵の助けを借りて派生しました。

ADD 2 3
-> (λm n f x. m f (n f x)) (λf x.f(f(f x))) (λf x.f(f x))
->   (λn f x. (λf x.f(f(f x))) f (n f x))   (λf x.f(f x))
->     (λf x. (λf x.f(f(f x))) f ((λf x.f(f x)) f x)) 
->     (λf x.   (λx.f(f(f x)))   ((λf x.f(f x)) f x)) 
->     (λf x.       f(f(f(λf x.f(f x)) f x)))))
->     (λf x.       f(f(f  (λx.f(f x)) x)))))
->     (λf x.       f(f(f     (f(f x))  )))))

他のヒント

私自身の限られたが最近の経験からの私のアドバイス：

  1. 行う 1 一度に物：アルファ変換、ベータ削減、またはETA変換を実行します。次の行に到達するために取ったステップに取り組んでいるページのマージンに注意してください。それらの言葉があなたに馴染みがないなら、彼らがすることはどうなるでしょう - ただ見てください ウィキペディア.

これらの削減手順の簡単な概要：

アルファとは、コンテキストで変数の名前を一貫して変更することを意味します。

λfx. f (f x) => λgx. g (g x)

ベータは、ラムダを適用することを意味します 1 口論

(λf x. f x) b => λx. b x

ETAは、その意味を変えない不必要に包まれた機能を単に「アンラッピング」しています。

λx.f x => f

それで

  1. 使用する たくさん アルファ変換の変数の名前を変更して、物事をより明確にします。それらすべて fS、それは常に混乱しているでしょう。あなたはと同様のことをしました " 2行目

  2. あなたがコンピューターのふりをしてください！式を評価しているときは、前に飛び降りたり、ステップをスキップしたりしないでください。次のことをしてください（そして1つだけ）。ゆっくりと移動すると確信したら、より速く移動してください。

  3. いくつかの表現に名前を付けることを検討し、それらを評価する必要がある場合にのみ、それらをラムダ式に置き換えることを検討してください。私は通常、ページの縁の置換に注意してください by def それは実際には削減ステップではないので。何かのようなもの：

    add two three 
(λm n f x. m f (n f x)) two three | by def

したがって、上記のルールに従って、ここに私の作業例があります：

two   = λfx. f (f x)
three = λfx. f (f (f x))
add   = λmnfx. m f (n f x)

0  | add two three 
1  | (λm n f x. m f (n f x)) two three           | by def
2  | (λn f x. two f (n f x)) three               | beta
3  | (λf x. two f (three f x))                   | beta
4  | (λf x. two f ((λfx. f (f (f x))) f x))      | by def
5  | (λf x. two f ((λgy. g (g (g y))) f x))      | alpha
6  | (λf x. two f ((λy. f (f (f y))) x))         | beta
7  | (λf x. two f (f (f (f x))))                 | beta
8  | (λf x. (λfx. f (f x)) f (f (f (f x))))      | by def
9  | (λf x. (λgy. g (g y)) f (f (f (f x))))      | alpha
10 | (λf x. (λy. f (f y)) (f (f (f x))))         | beta
11 | (λf x. (λy. f (f (f (f (f x))))))           | beta

そのような問題に対処するための正式で簡単なテクニックはありますか？

そうです 多くの Lambda用語の還元剤とPrettyPrinterを手作業で削減するよりも簡単に書き込みます。だが plt redex 削減で足を上げることができます。通常の注文削減のルールを定義してみてください、そしてあなたがしなければならないことは心配することだけです 冗長な括弧なしで結果をかなり印刷します.

あなたもおそらくもっと多くを学ぶでしょう。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top