Не может вывести числовое представление (церковное кодирование) лямбда-выражения λx.λy.x(xy)

Question

У меня есть лямбда-выражение: λx.λy.x(xy)и я должен вывести целочисленное представление этого. Я много читал о церковных кодировках и церковных цифрах, но не могу найти, что это за число. Можете ли вы объяснить это мне так, как трехлетний ребенок может понять или направить меня к ресурсу лучше, чем википедия?

Answer 1

Церковная кодировка целых чисел заключается в следующем:

• "0" ≡ (λf.(λx.x)): Думать о (λf.(λx.x)) как значение: дано функцию f и элемент xрезультат x: это похоже на применение функции f ноль раз x,
• "1" ≡ (λf.(λx.(fx))): Думать о (λf.(λx.(fx))) как значение: дано функцию f и элемент xрезультат (fx): что следует считать применимым f в x или, в более стандартных математических обозначениях, таких как f (x).
• "2" ≡ (λf.(λx.(f(fx)))): Думать о (λf.(λx.(f(fx)))) как значение: дано функцию f и элемент xрезультат (f(fx)): что следует считать применимым f в x дважды или, в более стандартных математических обозначениях, например, f (f (x)).
• "3" ≡ (λf.(λx.(f(f(fx))))): Думать о (λf.(λx.(f(f(fx))))) как значение: дано функцию f и элемент xрезультат (f(f(fx))): что следует считать применимым f в x три раза или, в более стандартных математических обозначениях, например, f (f (f (x))).

Я надеюсь, что вы видите образец (и логику позади). В твоем случае, (λx.(λy.(x(xy)))) является церковной кодировкой числа 2 (используя альфа-эквивалентность, конечно).

Статья в википедии на самом деле вполне понятна. Что ты не понимаешь?