¿Cuál es el punto de la conversión

18

Creo que no lo entiendo, pero la conversión me parece una conversión que no hace nada, un caso especial de conversión donde el resultado es solo el término en la abstracción lambda porque no hay nada hacer, una especie de conversión sentido.β β βηβββ

Entonces, tal vez -conversion es algo realmente profundo y diferente de esto, pero, si lo es, no lo entiendo, y espero que me puedan ayudar con eso.η

(Gracias y lo siento, sé que esto es parte de los conceptos básicos del cálculo lambda)

Trylks
fuente

Respuestas:

20

Actualización [2011-09-20]: amplié el párrafo sobre η -expansión y extensionalidad. Gracias a Anton Salikhmetov por señalar una buena referencia.

η -conversion(λx.fx)=f es un caso especial deβ - conversiónsoloen el caso especial cuandof es en sí mismo una abstracción, por ejemplo, sif=λy.yy luego

(λx.fx)=(λx.(λy.yy)x)=β(λx.xx)=αf.
Pero, ¿quépasasif es una variable o una aplicación que no se reduce a una abstracción?

En cierto modo, η -rule es como un tipo especial de extensionalidad, pero tenemos que tener un poco de cuidado sobre cómo se afirma. Podemos establecer la extensionalidad como:

  1. para todos los términos M y N , si M x = N x entonces M = N , oλMNMx=NxM=N
  2. para todo si x . f x = g x entonces f = g .f,gx.fx=gxf=g

El primero es una metadeclaración sobre los términos del cálculo . En ella x aparece como una variable formal, es decir, es parte del cálculo λ . Se puede probar a partir de las reglas β η , véase por ejemplo el Teorema 2.1.29 en "Cálculo de Lambda: su sintaxis y semántica" de Barendregt (1985). Puede entenderse como una declaración sobre todas las funciones definibles , es decir, aquellas que son denotaciones de términos λ .λxλβηλ

La segunda afirmación es cómo los matemáticos suelen entender las afirmaciones matemáticas. La teoría del cálculo describe un cierto tipo de estructuras, llamémoslas " modelos λ ". Un modelo λ podría ser incontable, por lo que no hay garantía de que cada elemento corresponda a un término λ (al igual que hay más números reales que expresiones que describen reales). La extensibilidad luego dice: si tomamos dos cosas f y g en un modelo λ , si f x = g x para todas las x en el modelo, entonces f = gλλλλfgλfx=gxxf=g. Ahora, incluso si el modelo satisface la regla , no necesita satisfacer la extensionalidad en este sentido. (Se necesita referencia aquí, y creo que debemos tener cuidado de cómo se interpreta la igualdad).η

Hay varias formas en que podemos motivar las conversiones y η . Elegiré aleatoriamente la categoría teórica, disfrazada de cálculo λ , y alguien más puede explicar otras razones.βηλ

Consideremos el cálculo tipificado (porque es menos confuso, pero más o menos el mismo razonamiento funciona para el cálculo λ sin tipo). Una de las leyes básicas que deben bodegas es la ley exponencial C A × B( C B ) Una . (Estoy usando las anotaciones A B y B A de manera intercambiable, seleccionando la que parezca mejor). ¿Qué hacen los isomorfismos i : C A × B( C B ) A y j :λλ

CA×B(CB)A.
ABBAi:CA×B(CB)A parece, escrito en λ- cálculo? Es de suponer que serían i = λ f : C A × B . λ una : Una . λ b : B . f un , b y j = λ g : ( C B ) A . λ p : A × Bj:(CB)ACA×Bλ
i=λf:CA×B.λa:A.λb:B.fa,b
Un corto cálculo con un par de beta -reductions (incluyendo la β -reductions π 1un , b = una y π 2un , b = b para los productos) nos dice que, para cada g : ( C B ) A tenemos i ( j g ) =
j=λg:(CB)A.λp:A×B.g(π1p)(π2p).
ββπ1a,b=aπ2a,b=bg:(CB)A Desde i y j son inversas entre sí, esperamos que i ( j g ) = g , pero para realmente probar esto tenemos que utilizar η -Reducción dos veces: i ( j g ) = ( λ un : A . Λ b : B . g a b ) = η (
i(jg)=λa:A.λb:B.gab.
iji(jg)=gη Esta es una razón para tenerreducciones η . Ejercicio: ¿quéregla η se necesita para mostrar que j ( i f ) = f ?
i(jg)=(λa:A.λb:B.gab)=η(λa:A.ga)=ηg.
ηηj(if)=f
Andrej Bauer
fuente
ββηβη
ηβη
1
==βMx=NxM=NM=NM=βηNη
MN
1
@AndrejBauer Estoy de acuerdo en que la regla η no es una extensionalidad completa, pero ¿no crees que sigue siendo una forma limitada de extensionalidad, es decir, representa una clase de casos obvios de extensionalidad? La pregunta original es buscar motivaciones y conceptos, y en este caso creo que pensar en términos de extensionalidad es útil (con cierto cuidado, por supuesto, para no ir demasiado lejos).
Marc Hamann
9

Para responder a esta pregunta, podemos proporcionar la siguiente cita de la monografía correspondiente "Cálculo de Lambda". Su sintaxis y semántica "(Barendregt, 1981):

βηλλ+extextMx=NxM=N

M=βηNληM=Nλ+extM=N

[Su prueba se basa en el siguiente teorema.]

λ+extλη(ext)(η)

λη

MNληM=Nλη+M=N

Las teorías completas de HP [después de Hilbert-Post] corresponden a teorías máximas consistentes en teoría de modelos para la lógica de primer orden.


fuente
7

λβη

  • λxy.xλxy.y βηβη

  • ι

    1. u =ι vt u =ι t v

    2. βηtut=ιutβηu

tut=βηιu

Esta es una consecuencia del teorema de Böhm.

cody
fuente
6

η

=βηβηM=Nλx.M=λx.N=β

=β=βηλx.Mx=MMx=NxM=N

Marcin Kotowski
fuente
η
Véase el teorema 2.1.29 en la monografía de Barendregt (cálculo de Lambda y su semántica, 1985).
2
ξ
Y, a su vez, no estoy muy contento de que la felicidad y las respuestas parecidas a las de "escuchar" ganen más atención que las citas directas relevantes con las referencias correspondientes.
ξξαβ