Una evaluación de cálculo lambda con números de la Iglesia

Entiendo que un número de Iglesia parece a (... n veces ...) . Esto no significa nada más que "la función aplicados veces a la función ". λ s . λ z . s $c_n$$\lambda s. \lambda z. s$s n $s\;z$$s$$n$$z$

Una posible definición de la función es la siguiente: . Mirando el cuerpo, entiendo la lógica detrás de la función. Sin embargo, cuando comienzo a evaluar, me atoro. Lo ilustraré con un ejemplo: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*}$$

Ahora, en esta situación, si primero aplico , obtengo el resultado deseado. Sin embargo, si aplico primero, como debería porque la aplicación es asociativa desde la izquierda, obtengo un resultado incorrecto:( λ 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$

Ya no puedo reducir esto. ¿Qué estoy haciendo mal? El resultado debería ser$\lambda s. \lambda z.s\;s\;s\;s\;s\;s\;z$

Creo que su reducción es correcta (sin embargo, solo la he analizado). Al final, no puede aplicar a , esto nunca aparece en el término. es , no . Las funciones en el cálculo lambda toman un solo argumento; se curry efectivamente : una función de dos argumentos se implementa como una función de un argumento que toma el primer argumento y devuelve una nueva función de un argumento que toma el segundo argumento y devuelve el 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)$

Cometiste el mismo error al definir los números de la Iglesia. El número de la Iglesia para se basa en componer una función veces. “La función aplicó veces a la función ” . Lo que escribiste es la función aplicada veces a la función finalmente a , lo que no me parece un término ú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$ es así . Te dejaré comprobar que se reduce 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)))))$