0

この答えは言う

  1. 以下は、ラムダ計算における基本的な y コンビネータです。

    Y f = (\x -> f (x x)) (\x -> f (x x))

つまり、Clojure では次のようなものです。

(defn Y [f]
  ((fn [x] (x x))
   (fn [x]
     (f (fn [& args]
          (apply (x x) args))))))

(def fac
     (fn [f]
       (fn [n]
         (if (zero? n) 1 (* n (f (dec n)))))))

(def fib
     (fn [f]
       (fn [n]
         (condp = n
           0 0
           1 1
           (+ (f (dec n))
              (f (dec (dec n))))))))

  1. y-Combinator の別の式を次に示します (引数のステップ 2)。

  2. チューリング完全言語をエンコードしました (y-Combinator を使用したため) (引数のステップ 3)

私の質問は、y-combinator がチューリング等価性を提供するのはなぜですか? それは議論の単なる仮定だったようです。

4

2 に答える 2

1

完全性をチューリングするには λ だけで十分なので、Y Combinator は単なるライブラリ コードです。簡単な自己再帰を提供します。

私がそれを読んだときの質問は、自己適用を排除することによって、λ計算からチューリングの完全性を取り除くことができるかどうかを尋ねます.計算 (停止問題)。

この議論は、明らかな自己再帰なしで Y を構築する方法を示しているだけであり、Y がパターンのファミリー全体の最も凝縮されたバージョンにすぎないという事実を強調しています。

チューリング完全ではないラムダ計算のサブセットに対する本当の答えは、総関数です。

于 2014-09-30T12:32:32.640 に答える