0

ラムダ計算で二項指数演算子を定義しようとしています。たとえば、演算子CARATです。たとえば、この演算子は、数値 2 のラムダ エンコーディングと数値 4 のラムダ エンコーディングの 2 つの引数を取り、数値 16 のラムダ エンコーディングを計算します。答えが正しいか間違っているかはわかりませんが、1 日かかりましたそうするために。私は教会の数字の定義を使用しました。

これが私の答えです。私の答えが間違っている場合は修正してください。正しい方法で正確に行う方法はわかりません。誰かが知っているなら、短い答えを理解するのを手伝ってください。

1 を加算する後継関数 は、とnextで自然数を定義できます。zeronext

1 = (next 0)    
2 = (next 1)
  = (next (next 0))    
3 = (next 2)
  = (next (next (next 0)))

next上記の結論から、関数を次のように定義できます。

next = λ n. λ f. λ x.(f ((n f) x))
one  = (next zero)
     => (λ n. λ f. λ x.(f ((n f) x)) zero)
     => λ f. λ x.(f ((zero f) x))
     => λ f. λ x.(f ((λ g. λ y.y f) x)) -----> (* alpha conversion avoids clash *)
     => λ f. λ x.(f (λ y.y x))
     => λ f. λ x.(f x)

したがって、安全に証明できます…。

zero = λ f. λ x.x
one = λ f. λ x.(f x)
two = λ f. λ x.(f (f x))
three = λ f. λ x.(f (f (f x)))
four = λ f. λ x.(f (f (f (f x))))
:
:
:
Sixteen = λ f. λ x.(f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f x))))))))))))))))

追加は、後継者の単なる反復です。これで、 の観点から足し算を定義できるようになりましたnext。

m next n => λx.(nextm x) n => nextm n => m+n
add = λ m. λ n. λ f. λ x.((((m next) n) f) x)
four = ((add two) two)
     => ((λ m. λ n. λ f. λ x.((((m next) n) f) x) two) two)
     => (λ n. λ f. λ x.((((two next) n) f) x)two)
     => λ f. λ x.((((two next) two) f x)
     => λ f. λ x.(((( λ g. λ y.(g (g y)) next) two) f x)
     => λ f. λ x.((( λ y.(next (next y)) two) f) x)
     => λ f. λ x.(((next (next two)) f) x)
     => λ f. λ x.(((next (λ n. λ f. λ x.(f ((n f) x)) two)) f) x)

「next」とそれに続く「two」に値を代入した後、上記の形式をさらに次のように縮小できます。

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

つまり4つ。

同様に、掛け算は足し算の繰り返しです。したがって、乗算は次のように定義されます。

mul = λ m. λ n. λ x.(m (add n) x)
six = ((mul two) three)
 => ((λ m. λ n. λ x.(m (add n) x) two) three)
 => (λ n. λ x.(two (add n) x) three)
 => λ x.(two (add three) x
 => ( λf. λx.(f(fx)) add three) 
 =>( λx.(add(add x)) three)
 => (add(add 3))
 => ( λ m. λ n. λ f. λ x.((((m next) n) f) x)add three)
 => ( λ n. λ f. λ x.((( three next)n)f)x)add)
 => ( λ f. λ x.((three next)add)f)x)

「three」、「next」、続いて「add」、さらに「next」の値を代入した後、上記の形式は次のように縮小されます。

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

すなわち6。

最後に、累乗は反復乗算によって定義できます

累乗関数をCARATと呼ぶと仮定

CARAT = λm.λn.(m (mul n) )
sixteen => ((CARAT four) two)
 => (λ m. λ n.(m (mul n) four) two)
 => (λ n.(two (mul n)four
 => (two (mul four))
 => ((λ f. λ x.(f (f x))))mul)four)
 => (λ x. (mul(mul x))four)
 => (mul(mul four))))
 => (((((λ m. λ n. λ x.(m (add n) x)mul)four)
 => ((((λ n. λ x.(mul(add n) x)four)
 => (λ x.(mul(add four) x))
 => (λ x (λ m. λ n. λ x.(m (add n) x add)four) x
 => (λ x (λ n. λ x. (add(add n) x)four)x
 => (λ x (λ x (add (add four) x) x)
 => (λ x (λ x (λ m. λ n. λ f. λ x((((m next) n) f) x)add )four) x) x)
 => (λ x (λ x (λ n. λ f. λ x(((add next)n)f)x)four)x)x)
 => (λ x (λ x (λ f. λ x((add next)four)f)x)x)x) 
 => (λ x (λ x (λ f. λ x((λ m. λ n. λ f. λ x((((m next) n) f) x)next)four)f)x)x)x)
 => (λ x (λ x (λ f. λ x((λ n. λ f. λ x.(((next next)n)f)x)four)f)x)x)x)
 => (λ x (λ x (λ f. λ x((λ f. λ x ((next next)four)f)x)f)x)x)x)
 => (λ x (λ x (λ f. λ x((λ f. λ x(((λ n. λ f. λ x.(f ((n f) x))next)four)f)x)f)x)x)x)

ここで、上記の式を簡約して「next」と「four」を代入し、さらに簡約すると、次の形式が得られます

λ f. λ x.(f (f (f (f (f (f (f (f (f (f (f (f (f (f (f (f x))))))))))))))))

つまり、16 です。

4

1 に答える 1

1

まず、次のように書き直しますnext = λ n. λ f. λ x.(f ((n f) x))。

next = λ num. λ succ. λ zero. succ (num succ zero)

ラムダ計算では、括弧はグループ化のためだけに使用されます。アプリケーションは、用語の並置によって示されます。つまり、ある用語を別の用語の隣に書くだけで、左側に関連付けられます。

上記の読み方は？ラムダ項です。それが他のラムダ項、たとえばNUMに適用されると、ラムダ項に縮小されλ succ. λ zero. succ (NUM succ zero)ます。これは、 で表される特定の数値の次の数値の表現である、即時の結果になりますNUM。それは、 「後継者の計算方法も、ゼロであることの意味もわかりませんが、両方が与えられた場合、それらとNUMそれらの計算手段をに提供しNUM、その結果を私に与えられた後継関数に再度適用することにより、私を作成するために使用されたラムダ項」 .

もちろん、これは がNUM同じ仮定を尊重し、一貫した方法で動作することを前提としていました。特に、がおよびZEROに適用された場合、 を返す必要があります。szz

ZERO = λ s. λ z. z  ; == λ a. λ b. b == ...

他のすべてはこれから続きます。

于 2013-12-09T07:56:55.043 に答える