Пример сокращения лямбда-выражения

Question

Как можно уменьшить следующее лямбда-выражение (λs.λq.s q q) (λq.q) q? В первых скобках q q является входом для выражения (λs.λq.s) или является частью выражения (s q q)?

(λs.λq.sqq) (λq.q) q = (λq.qq) (λq.q) q = (λq.q) (λq.q) q = (λq.q) q = q

(λs.λq.s q q) (λq.q) q = (λq. (Λq’.q ’) q q) q = (λq.qq) q = qq

Я получаю два разных ответа в зависимости от того, как я это вижу. Какой из них правильный?

Answer 1

Общее правило - начинать читать выражение слева до Вы прибываете в лямбду. В вашем случае (λs.λq.s q q). Тогда продолжай чтение, пока вы не нашли следующий термин - аргумент. В вашем дело (λq.q). Затем снимите наружный слой лямбды и замените имя переменной с аргументом. В вашем случае s заменяется на (λq.q)

   (λs.λq.s q q) (λq.q) q
-> (λq.(λq.q) q q) q

Затем повторите процесс. Теперь лямбда равна (λq.(λq.q) q q), а аргумент q:

   (λq.(λq.q) q q) q
-> (λq.q) q q

Количество q сбивает с толку, но правила тривиальны. Повторите повторите процесс:

   (λq.q) q q
-> q q

Теперь больше ничего нельзя отделить от выражения, чтобы вы сделанный. Вы можете попробовать это самостоятельно, используя интерактивный переводчик на это страница .

Answer 2

Использование лямбда-исчисления с

 (\s.\q.s q q)(\q.q)q

возвращает

Normal order:

q q
Performed 3 beta-reductions

---

Одна область значений, которую часто упускают из виду люди, использующие StackExchange сайты, такие как StackOverflow, является информационной вкладкой для тега.

В частности, для этого вопроса с тегом lambda-calculus на информационной вкладке отображается

Поскольку многие люди спрашивают, как уменьшить λ-выражения с помощью промежуточных шагов, взгляните на Верстак для сокращения лямбда-исчисления и его интерпретатор .

Итак, с вашим вопросом вводится

и при нажатии Do it

---

Существует также опция трассировки, чтобы увидеть все преобразования