Una valutazione lambda calcolo che coinvolgono numeri Chiesa

Question

Capisco che un Chiesa numerale $ c_n $ assomiglia a $ \ lambda s. \ Lambda z. s $ (... n volte ...) $ s \; z $. Questo non significa altro che "la funzione $ s $ applicata $ n $ volte alla funzione $ Z $".

Una possibile definizione del $ \ mathtt {} volte la funzione $ è il seguente: $ \ {mathtt volte} = \ lambda m. \ Lambda n. \ Lambda s. m \; (N \; s) $. Guardando il corpo, ho capito la logica dietro la funzione. Tuttavia, quando inizio la valutazione, mi si blocca. Illustrerò con un esempio:

$$ \ begin {* align} (\ Lambda m \ lambda 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. \ Lambda z. (\ Lambda z.s \; s \; s \; z) \; (\ lambda z.s \; s \; s \; z) \; z \ End {align *} $$

Ora, in questa situazione, se ho applicare $ (\ lambda z.s \; s \; s \; z) \; z $, ottengo al risultato desiderato. Tuttavia, se applico $ (\ lambda zs \; s \; s \; z) \; (\ lambda zs \; s \; s \; z) $ prima, come avrei dovuto perché l'applicazione è associativa da sinistra, ottengo un risultato sbagliato:

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

I non può più ridurre questo. Che cosa sto facendo di sbagliato? Il risultato dovrebbe essere $ \ lambda s. \ Lambda z.s \; s \; s \; s \; s \; s \; z $

Answer 1

I think your reduction is correct (I've only eyeballed it, though). At the end, you can't apply $(\lambda z. s s s z)$ to $z$, this never appears in the term. $\lambda z. f f z$ is $\lambda z. (f f) z$, not $\lambda z. f (f z)$. Functions in the lambda-calculus take a single argument; they are effectively curried: a two-argument function is implemented as a one-argument function that takes the first argument and returns a new one-argument function that takes the second argument and returns the result.

You made the same mistake when defining Church numerals. The Church numeral for $n$ is based on composing a function $n$ times. “The function $s$ applied $n$ times to the function $z$” $\lambda s. \lambda z. s (s ( … s \: z) … ))$. What you wrote is the function $s$ applied $n-1$ times to the function $s$ and finally to $z$, which doesn't strike me as a useful term.

$2 \times 3$ is thus $(\lambda m n s. m (n s)) (\lambda s z. s (s \: z)) (\lambda s z. s (s (s \: z)))$. I'll let you check that it does reduce to $\lambda s z. s (s (s (s (s (s \: z)))))$.