Riduzione dell'espressione della Lambda.

Question

Non riesco a risolvere la seguente espressione lambda utilizzando sia l'ordine normale (call-by-nome) che l'ordine applicativo (call-by-value) riduzione.Continuo a ottenere risposte diverse per entrambi.Questa è l'espressione lambda che deve essere ridotta usando entrambe le tecniche:

$ (\ Lambda f \ x \ ldotp f \ (f \ x)) \ (\ lambda f \ x \ ldotp f \ (f \ x)) \ f \x $

Answer 1

.

Continuo a ottenere risposte diverse per entrambi.

Dovresti ottenere lo stesso risultato per entrambi gli ordini. Si prega di mostrare il tuo lavoro in modo che la comunità possa aiutarti a trovare il tuo errore.

La mia ipotesi è stata sostituita per errore $ f $ invece di $ x $ verso la fine, Quando $ f $ è infatti gratis.

La procedura di riduzione corretta è mostrata di seguito.

---

.

$ (\ Lambda f \ x \ ldotp f \ (f \ x)) \ (\ lambda f \ x \ ldotp f \ (f \ x)) \ f \ x $

Non c'è differenza tra ordine normale e ordine applicativo al primo passo.

$ (\ lambda f \ x \ ldotp f \ (f \ x)) \ (\ lambda f \ x \ ldotp f \ (f \ x)) \ f ) \ x $

---

.

A questo passaggio c'è una differenza, perché il valore viene applicato a, $ (\ Lambda f \ x \ ldotp f \ (f \ x)) \ f) $ non è in forma normale normale. Ignoriamoci e usa prima ordine normale.

ordine normale

$ (\ Lambda f \ x \ ldotp f \ (f \ x)) \ f) \ (((\ lambda f \ x \ ldotp f \ (f \ x)) \ f) \ x) $

$ (\ lambda x \ ldotp \ f \ (f \ x)) \ ((\ lambda f \ x \ ldotp f \ (f \ x)) \ f ) \ x) $

$ f \ (f \ (((\ lambda f \ x \ ldotp f \ (f \ x)) \ f) \ x)) $ < / P >.

$ f \ (f \ (f \ (f \ x))) $

---

.

Torniamo al primo passo.

$ (\ lambda f \ x \ ldotp f \ (f \ x)) \ (\ lambda f \ x \ ldotp f \ (f \ x)) \ f ) \ x $

---

.

Questa volta usiamo l'ordine applicativo

ordine applicativo

$ (\ Lambda f \ x \ ldotp f \ (f \ x)) \ (\ lambda x \ ldotp f \ (f \ x)) \ x $

$ (\ Lambda x \ ldotp f \ (f \ x)) \ (\ Lambda x \ ldotp f \ (f \ x)) \ x) $

$ (\ Lambda x \ LDOTP f \ (f \ x)) \ (f \ (f \ x)) $

$ f \ (f \ (f \ (f \ x))) $

---

.

Con ordine normale abbiamo ridotto l'espressione a:

$ f \ (f \ (f \ (f \ x))) $

Con l'ordine applicativo abbiamo ridotto l'espressione a:

$ f \ (f \ (f \ (f \ x))) $

I risultati sono gli stessi.