Una evaluación lambda cálculo que implica números Iglesia

Question

Yo entiendo que un Iglesia numeral $ $ C_n se parece a $ \ lambda s. \ Lambda z. S $ (... n veces ...) $ s \; z $. Esto no significa nada más que "la función $ s $ $ n $ aplicada a veces la función $ z $".

Una posible definición de la $ \ {mathtt veces} $ función es la siguiente: $ \ {mathtt veces} = \ lambda m. \ Lambda n. \ Lambda s. m \; (N \; s) $. En cuanto a la carne, lo entiendo la lógica detrás de la función. Sin embargo, cuando empiece a evaluar, se queda bloqueado. Voy a ilustrar con un ejemplo:

$$ \ begin {align *} (\ Lambda lambda m \ n \ lambda s m \;... (N \; s)) (\ lambda s \ lambda zs \;. S \; z) (\ lambda s \ lambda zs \;. S \ ; s \; z) \ mspace {} \\ -4em \ A ^ * & \ lambda s. (\ Lambda s \ lambda z.s \;. S \; z) \; ((\ Lambda s \ lambda z.s \;. S \; s \; z) \; s)) \\ \ A ^ * & \ lambda s. (\ Lambda s \ lambda z.s \;. S \; z) \; (\ Lambda z.s \; s \; s \; z) \\ \ A ^ * & \ lambda s. \ Z lambda. (\ Lambda z.s \; s \; s \; z) \; (\ lambda z.s \; s \; s \; z) \; z \ End {align *} $$

Ahora, en esta situación, si primero se aplica $ (\ lambda z.s \; s \; s \; z) \; z $, llego al resultado deseado. Sin embargo, si aplico $ (\ lambda ZS \; s \; s \; z) \; (\ lambda ZS \; s \; s \; z) $ en primer lugar, como debería porque la aplicación es asociativo por la izquierda, consigo un mal resultado:

$ s \ lambda. \ Lambda z. (\ Lambda z.s \; s \; s \; z) \; (\ lambda z.s \; s \; s \; z) \; z \ para \ lambda s. \ Lambda z. (S \; s \; s \; (\ lambda z.s \; s \; s \; z)) \; \; z $

Ya no se puede reducir este. ¿Qué estoy haciendo mal? El resultado debe ser \ lambda $ s. \ Lambda z.s \; s \; s \; s \; s \; s \; z $

Answer 1

Creo que su reducción es correcta (sólo he eyeballed que, sin embargo). Al final, no se puede aplicar $ (\ lambda z. S s s z) $ hasta $ z $, esto nunca aparece en el término. $ \ Lambda z. f f z $ es $ \ lambda z. (F f) z $, no $ \ lambda z. f (f z) $. Funciones en el lambda-cálculo toman un único argumento; son efectivamente curry : una función de dos argumentos se implementa como una función de un argumento que lleva el primer argumento y devuelve una nueva función de un argumento que lleva el segundo argumento y devuelve el resultado.

Se hizo el mismo error al definir los números de la Iglesia. El numeral Iglesia por $ n $ se basa en componer una función $ n $ veces. “La función $ s $ $ n $ aplica veces a la función $ z $” $ \ lambda s. \ Lambda z. s (s (s ... \: z) ...)) $. Lo que ha escrito es la función $ s $ $ aplicó n-1 multiplicado por $ a la función $ s $ y finalmente a $ z $, lo cual no me parece que sea un término útil.

$ un 2 \ veces 3 $ es por lo tanto $ (\ lambda mn s m (ns).) (\ Lambda s z s (s \:. Z)). (\ Lambda s z s (s (s \: z PS Voy a dejar de comprobar que no se reducen a $ \ lambda s z. s (s (s (s (s (s \: z))))). $