cálculo lambda

Question

Todo,

A continuación se muestra la expresión lambda, que me resulta difícil de reducir, es decir que no soy capaz de entender cómo hacer para este problema.

(λm λn λa λb m (NAB) b.) (Λ f x x.) (Λ f x fx.)

Esto es lo que he intentado, pero estoy atascado:

Teniendo en cuenta la expresión anterior como: (. λf x x) (λm.E) m equivale a
E = (. λn λa λb m (nAB) b)
m = (. λ f x fx)

= > (λn λa λb. (λ f x. x) (λ f x. fx) (nab) b)

C onsiderando la expresión anterior como (λn. E) M equivale a
E = (λa λb. (Λ f x. X) (λ f x. F x) (n a b) b)
M = ??

.. ¡y estoy perdido!

¿Alguien puede ayudarme a entender que, para CUALQUIER expresión de cálculo lambda, cuáles deberían ser los pasos para realizar la reducción?

Answer 1

puede seguir los siguientes pasos para reducir las expresiones lambda:

1. Totalmente entre paréntesis la expresión para evitar errores y hacerla más obvia donde se lleva a cabo la aplicación de la función
2. Buscar una aplicación de función, es decir, encontrar una aparición del patrón (λX. e1) e2 donde X puede ser cualquier identificador válido y e1 y e2 pueden ser expresiones válidas.
3. aplicar la función mediante la sustitución de (λx. e1) e2 con e1' donde e1' es el resultado de sustituir cada ocurrencia libre de x en e1 con e2.
4. Repita los pasos 2 y 3 hasta que el patrón ya no ocurra. Tenga en cuenta que esto puede conducir a un bucle infinito de expresiones no normalizado, por lo que debe detenerse después de 1000 iteraciones o menos ;-)

Así que por su ejemplo que comenzar con la expresión

((λm. (λn. (λa. (λb. (m ((n a) b)) b)))) (λf. (λx. x))) (λf. (λx. (f x))) 

Aquí la subexpresión (λm. (λn. (λa. (λb. (m ((n a) b)) b)))) (λf. (λx. x)) se ajusta a nuestro patrón con X = m, e1 = (λn. (λa. (λb. (m ((n a) b)) b)))) y e2 = (λf. (λx. x)). Así que después de la sustitución obtenemos (λn. (λa. (λb. ((λf. (λx. x)) ((n a) b)) b))), lo que hace que toda nuestra expresión:

(λn. (λa. (λb. ((λf. (λx. x)) ((n a) b)) b))) (λf. (λx. (f x))) 

Ahora podemos aplicar el patrón a toda la expresión con X = n, e1 = (λa. (λb. ((λf. (λx. x)) ((n a) b)) b)) y e2 = (λf. (λx. (f x))). Así que después de la sustitución obtenemos:

(λa. (λb. ((λf. (λx. x)) (((λf. (λx. (f x))) a) b)) b)) 

ahora ((λf. (λx. (f x))) a) se ajuste a nuestro patrón y se convierte en (λx. (a x)), lo que conduce a:

(λa. (λb. ((λf. (λx. x)) ((λx. (a x)) b)) b)) 

Esta vez podemos aplicar el patrón a ((λx. (a x)) b), que se reduce a (a b), lo que lleva a :

(λa. (λb. ((λf. (λx. x)) (a b)) b)) 

Ahora aplicar el patrón a ((λf. (λx. x)) (a b)), que se reduce a (λx. x) y obtenga:

(λa. (λb. b)) 

Ahora hemos terminado.

Answer 2

dónde va mal es que en el primer paso, no se puede tener

M = (λf x. x)(λ f x. f x) 

porque la expresión original no incluye que la expresión de la aplicación. Para aclarar esto, se puede poner entre paréntesis implícitos siguiendo la regla de que la aplicación se asociativos por la izquierda-(usando [y] para los nuevos parens y poniendo en algunos desaparecidos s ""):

[ (λm . λn . λa . λb . m (n a b) b) (λ f x. x) ] (λ f x. f x) 

Desde aquí , encuentre una expresión del formulario (λv.E) M en algún lugar dentro y reduzca reemplazando v con M en E. Tenga cuidado de que realmente es una aplicación de la función a M: no es si tiene algo como N (λv.E) M, ya que entonces N se aplica a la función y M como dos argumentos.

Si todavía está atascado, intente poner los parens para cada lambda también, básicamente, un nuevo "(" después de cada ".", Y un emparejamiento ")" que va lo más a la derecha posible mientras todavía está . concuerden con la nueva "(" a modo de ejemplo, he hecho una aquí (usando [y] para hacer que se destacan):

((λm . λn . λa . [λb . m (n a b) b]) (λ f x. x)) (λ f x. f x)