Защо y-комбинаторът осигурява еквивалентност на Тюринг?

Този отговор казва

  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-комбинатора (стъпка 2 от аргумента)

  2. Ние кодирахме пълен език на Тюринг (тъй като използвахме y-Combinator) (стъпка 3 от аргумента)

Въпросът ми е: Защо y-комбинаторът осигурява еквивалентност на Тюринг? Изглежда, че това е само предположение на аргумента.


clojure lambda-calculus turing-complete y-combinator
person hawkeye    schedule 30.09.2014    source източник

Отговори (2)


arrow_upward
1
arrow_downward

Тъй като наличието само на λ вече е достатъчно за пълнота на Тюринг, Y Combinator е просто библиотечен код. Осигурява лесна саморекурсия.

Въпросът, както го чета, пита дали човек може да отнеме пълнотата на Тюринг от λ смятането, като елиминира самоприлагането, към което въпросът очевидно е отрицателен, тъй като няма начин за надеждно откриване на самоприлагане, освен действителното изпълнение на смятане (проблемът със спирането).

Аргументът просто показва как да се изгради Y без очевидна саморекурсия и подчертава факта, че Y е просто най-съкратената версия на цяло семейство модели.

Истинският отговор на подмножеството на ламбда смятането, което не е пълно по Тюринг, е: общи функции.

person Bendlas    schedule 30.09.2014

arrow_upward
1
arrow_downward

Първо. За да бъдете еквивалент на Тюринг, не ви трябва много. Стига с +,-,<,> ,[ и ] в BrainF**ck. Ако трябваше да премахнете функции от език LISPy и първо да премахнете всички циклични и рекурсивни повиквания (Fortran нямаше рекурсия в 60), пак ли щеше да е еквивалент на Turing?

да Това е така, защото имате както възходящи, така и низходящи функции от по-висок ред. С това можете да направите Y и да получите рекурсия. С рекурсия това ще бъде еквивалентно на Turing, дори ако изпълнението не е осигурило пряко зацикляне.

Y комбинаторът ли го позволява? Не точно. Можете да правите цикли и с call-with-current-continuation, така че бих казал, че функциите от по-висок ред го позволяват. Ако правите абсолютно същото нещо на език, който няма функции от по-висок ред, не можете да създадете Y и не можете да изчислите всички изчислими стойности.

person Sylwester    schedule 30.09.2014