Uma avaliação do cálculo lambda envolvendo números da Igreja

Entendo que um numeral da Igreja parece com (... n vezes ...) . Isso significa nada mais do que "a função aplicada vezes à função ". λ s . λ z . s $c_n$$\lambda s. \lambda z. s$s n $s\;z$$s$$n$$z$

Uma definição possível da função é a seguinte: . Olhando para o corpo, entendo a lógica por trás da função. No entanto, quando começo a avaliar, fico preso. Vou ilustrá-lo com um exemplo:t i m e s = λ m . λ n . λ s . $\mathtt{times}$$\mathtt{times} = \lambda m. \lambda n. \lambda s. m \; (n\; s)$

$$\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*}$$

Agora, nessa situação, se eu aplicar pela primeira vez , chego ao resultado desejado. No entanto, se eu aplicar primeiro, como devo, porque o aplicativo é associativo da esquerda, recebo um resultado errado:( λ z . $(\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$

Não posso mais reduzir isso. O que estou fazendo de errado? O resultado deve ser$\lambda s. \lambda z.s\;s\;s\;s\;s\;s\;z$

Eu acho que sua redução está correta (eu só olhei para ela, no entanto). No final, você não pode aplicar a , isso nunca aparece no termo. é , não . Funções no cálculo lambda usam um único argumento; elas são efetivamente curry : uma função de dois argumentos é implementada como uma função de um argumento que pega o primeiro argumento e retorna uma nova função de um argumento que pega o segundo argumento e retorna o resultado.z λ z . f f z λ z . ( f f ) z λ z . f ( f z $(\lambda z. s s s z)$$z$$\lambda z. f f z$$\lambda z. (f f) z$$\lambda z. f (f z)$

Você cometeu o mesmo erro ao definir os números da Igreja. O numeral da igreja para é baseado na composição de uma função vezes. “A função aplicada vezes à função ” . O que você escreveu é a função aplicadas vezes para a função e, finalmente, para , o que não me parece um termo útil.n s n z λ s . λ z . s ( s ( … $n$$n$$s$$n$$z$s n - 1 s $\lambda s. \lambda z. s (s ( … s \: z) … ))$$s$$n-1$$s$$z$

( λ m n s . M ( n s ) ) ( λ s z . S ( $2 \times 3$ é assim . Vou deixar você verificar se ele se reduz a .λ s z . s ( s ( s ( s ( s ( $(\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)))))$