Оценка лямбда-исчисления с использованием церковных цифр

Я понимаю, что церковная цифра выглядит как (... n раз ...) . Это означает не что иное, как «функция примененная раз к функции ». $c_n$ $\lambda s. \lambda z. s$ $s\;z$ $s$ $n$ $z$

Возможное определение функции следующее: . Глядя на тело, я понимаю логику функции. Однако, когда я начинаю оценивать, я застреваю. Я проиллюстрирую это на примере: $\mathtt{times}$ $\mathtt{times} = \lambda m. \lambda n. \lambda s. m \; (n\; s)$

\begin{aligned} (λ m . λ n . λ s . m (n s)) (λ s . λ z . s s z) (λ s . λ z . s s s z) \\ \to^{*} & λ s . (λ s . λ z . s s z) ((λ s . λ z . s s s z) s)) \\ \to^{*} & λ s . (λ s . λ z . s s z) (λ z . s s s z) \\ \to^{*} & λ s . λ z . (λ z . s s s z) (λ z . s s s z) z \end{aligned}

$\begin{align*} (\lambda m. \lambda n. \lambda s. m \; (n\; s))(\lambda s.\lambda z.s\;s\;z)(\lambda s.\lambda z.s\;s\;s\;z) \mspace{-4em} \\ \to^*& \lambda s. (\lambda s.\lambda z.s\;s\;z) \; ((\lambda s.\lambda z.s\;s\;s\;z)\; s)) \\ \to^*& \lambda s. (\lambda s.\lambda z.s\;s\;z) \; (\lambda z.s\;s\;s\;z) \\ \to^*& \lambda s. \lambda z.(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)\;z \end{align*}$

Теперь в этой ситуации, если я сначала применю , я получу желаемый результат. Однако, если я , как я должен, потому что приложение ассоциативно слева, я получаю неправильный результат: $(\lambda z.s\;s\;s\;z)\;z$ $(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)$

$\lambda s. \lambda z.(\lambda z.s\;s\;s\;z)\;(\lambda z.s\;s\;s\;z)\;z \to \lambda s. \lambda z.(s\;s\;s\;(\lambda z.s\;s\;s\;z))\;\;z$

Я больше не могу уменьшить это. Что я делаю неправильно? Результат должен быть $\lambda s. \lambda z.s\;s\;s\;s\;s\;s\;z$

lambda-calculus church-numerals Кодда
источник

Церковные цифры в вашем начальном сроке неверны. 2 представлен , а не .

λ s . λ z . s (s z)

$\lambda s. \lambda z. s (s z)$

λ s . λ z . s s z

$\lambda s. \lambda z. s s z$

Uday Reddy

Ответы:

Я думаю, что ваше сокращение является правильным (я только оценил это, хотя). В конце концов, вы не можете подать заявку к , это никогда не появляется в термине. является , а не . Функции в лямбда-исчислении принимают один аргумент; они эффективнокарри $(\lambda z. s s s z)$ $z$ $\lambda z. f f z$ $\lambda z. (f f) z$ $\lambda z. f (f z)$ : функция с двумя аргументами реализована как функция с одним аргументом, которая принимает первый аргумент и возвращает новую функцию с одним аргументом, которая принимает второй аргумент и возвращает результат.

Вы сделали ту же ошибку при определении церковных цифр. Церковная цифра для основана на составлении функции раз. «Функция применяется раз к функции » $n$ $n$ $s$ $n$ $z$ . Вы написали, что функция применяется раз к функции и, наконец, к , что не кажется мне полезным термином. $\lambda s. \lambda z. s (s ( … s \: z) … ))$ $s$ $n-1$ $s$ $z$

, таким образом $2 \times 3$ . Я позволю вам проверить, что оно сводится к $(\lambda m n s. m (n s)) (\lambda s z. s (s \: z)) (\lambda s z. s (s (s \: z)))$ . $\lambda s z. s (s (s (s (s (s \: z)))))$

Жиль "ТАК - перестань быть злым"
источник

Что касается вашего абзаца, вы правы, и я знал об этом. Меня просто поразило, что применение правильно ассоциативного действительно дает правильный результат. Что касается второго абзаца: вы правы. Использование без скобок было ошибочным с моей стороны, опять же из-за левой ассоциативности приложения. Теперь я снова уменьшу все это и посмотрю, действительно ли мое отсутствие скобок привело к моей ошибке!

codd

Это сделал. Вы заметили, что мои обозначения подразумевают неправильный порядок подачи заявки, что решило проблему! Принимая ваш ответ.

codd