clojure - Why does the y-combinator provide Turing equivalence?

Question

This answer says

1. Here is a basic y-combinator in lambda calculus:

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

Ie Something like this in 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))))))))

2. Here is another expression of the y-Combinator (step 2 of the argument)

3. We have encoded a Turing complete language (since we used the y-Combinator) (step 3 of the argument)

My question is: Why does the y-combinator provide Turing equivalence? It seems it was just an assumption of the argument.

Answer 1

First off. To be Turing Equivalent you don't need much. It's enough with +,-,<,> ,[, and ] in BrainF**ck. If you were to remove features from a LISPy language and first take away all looping and recursive calls (Fortran didn't have recursion in the 60) would it still be Turing equivalent?

Yes. It's because you have both upward and downward higher order functions. With that you can make Y and get recursion. With recursion it's will be turing equivalent even if implementation didn't directly provide any looping.

Is it the Y combinator that enables it? Not really. You can make loops with call-with-current-continuation as well so I'd say it was higher order functions that enables it. If you do the exact same thing in a language that don't have higher order functions you cannot create Y and you cannot calculate all computable values.

Answer 2

由于只有 λ 已经足够图灵完备，Y Combinator 仅仅是库代码。它提供了简单的自递归。

我读到的问题是，是否可以通过消除自应用来消除 λ 演算的图灵完整性，问题显然不是，因为没有办法可靠地检测自应用，除非实际运行微积分（停止问题）。

该论点只是展示了如何在没有明显自递归的情况下构建 Y，并强调 Y 只是整个模式家族中最精简的版本。

不是图灵完备的 lambda 演算子集的真正答案是：总函数。