Confluencia de la expansión beta

10

Deje ββ ser β-β reducción en el cálculo λλ . Definir β-β expansión ββ por t β tt β t tβttβt .

¿Es ββ confluente? En otras palabras, ¿tenemos eso para cualquier l , d , rl,d,r , si l β d β rlβdβr , entonces existe uu tal que l β u β rlβuβr ?

Palabras clave: Confluencia ascendente, propiedad CR invertida


Comencé mirando la propiedad más débil: confluencia local (es decir, si l β d β rlβdβr , entonces l β u β rlβuβr ). Incluso si esto fuera cierto, no implicaría confluencia ya que la expansión ββ no termina, pero pensé que me ayudaría a comprender los obstáculos.

(Arriba) En el caso donde ambos reducciones son en la parte superior de nivel, la hipótesis se convierte en ( λ x 1 . B 1 ) un 1b 1 [ un 1 / x 1 ] = b 2 [ un 2 / x 2 ] ( λ x 2 . b 2 ) un 2(λx1.b1)a1b1[a1/x1]=b2[a2/x2](λx2.b2)a2 . Hasta α-α ruming, podemos suponer que x 1x 2x1x2, y que ni x 1x1 ni x 2x2 son libres en esos términos.

(Throw) Si x 1x1 no es libre en b 1b1 , tenemos b 1 = b 2 [ un 2 / x 2 ]b1=b2[a2/x2] y por lo tanto tienen ( λ x 1 . B 1 ) un 1 = ( λ x 1 . B 2 [ una 2 / x 2 ] ) un 1( λ x 1 . ( λx 2 . b 2 ) un 2 ) un 1( λ x 2 . b 2 ) un 2(λx1.b1)a1=(λx1.b2[a2/x2])a1(λx1.(λx2.b2)a2)a1(λx2.b2)a2 .

Una prueba ingenua por inducción (en b 1b1 y b 2b2 ) para el caso (Arriba) sería la siguiente:

  • Si b 1b1 es una variable y 1y1 ,

    • Si y 1 = x 1y1=x1 , la hipótesis se convierte en ( λ x 1 . X 1 ) un 1un 1 = b 2 [ un 2 / x 2 ] ( λ x 2 . B 2 ) un 2(λx1.x1)a1a1=b2[a2/x2](λx2.b2)a2 , y de hecho tenemos ( λ x 1 . x 1 ) un 1 = ( λ x 1 .x 1 ) ( b 2 [ un 2 / x 2 ] ) ( λ x 1 . x 1 ) ( ( λ x 2 . aab 2 ) un 2 ) ( λ x 2 . b 2 ) un 2(λx1.x1)a1=(λx1.x1)(b2[a2/x2])(λx1.x1)((λx2.b2)a2)(λx2.b2)a2 .

    • Si y 1x 1y1x1 , entonces simplemente podemos usar (Lanzar).

  • Se aplican las mismas pruebas si b 2b2 es una variable.

  • Para b 1 = λ y . c 1b1=λy.c1 y b 2 = λ y . c 2b2=λy.c2 , la hipótesis se convierte en ( λ x 1 . λ y . c 1 ) un 1λ y . c 1 [ a 1 / x 1 ] = λ y . c 2 [ a 2 / x 2 ] ( Λ x 2 . Λ y . C 2 ) un 2(λx1.λy.c1)a1λy.c1[a1/x1]=λy.c2[a2/x2](λx2.λy.c2)a2 y la hipótesis de inducción da dd tal que ( λ x 1 . C 1 ) un 1d ( λ x 2 . C 2 ) un 2(λx1.c1)a1d(λx2.c2)a2 que implica que λ y . ( Λ x 1 . C 1 ) un 1λ y. d λ y . ( Λ x 2 . C 2 ) un 2λy.(λx1.c1)a1λy.dλy.(λx2.c2)a2 . Desafortunadamente, no tenemos λ y . ( Λ x 2 . C 2 ) un 2( λ x 2 . Λ y . C 2 ) un 2λy.(λx2.c2)a2(λx2.λy.c2)a2 . (Esto me hace pensar en lareducción σσ ).

  • Un problema similar surge para las aplicaciones: los λλ s no están donde deberían estar.

xavierm02
fuente
1
@chi A menos que me equivoque, ( λ b . y b ) y ( λ a . ( λ b . a b ) y ) y ( λ a . a y ) y funciona. (λb.yb)y(λa.(λb.ab)y)y(λa.ay)y
xavierm02
1
Estoy un poco de acuerdo con @chi en que parece confluente después de pensarlo y ver un par de contraejemplos. Pero en realidad, ¿qué pasa con ( λ x . XXy )y yyy ( λ x . yXx )y ? (λx.xxy)yyyy(λx.yxx)y
Rodolphe Lepigre
2
Aunque sería conveniente para mí si fuera cierto, soy un poco más pesimista. Un colega mío hizo la siguiente observación que hace que parezca poco probable: implicaría que se pueden combinar dos programas arbitrarios que computen el mismo entero (de la iglesia).
xavierm02
2
La respuesta es no. El ejercicio 3.5.11 en Barendregt da un contraejemplo atribuido a Plotkin, pero sin una referencia: ( λ x . B x ( b c ) ) c y ( λ x . X x ) ( b c ) . Voy a buscar una prueba. (λx.bx(bc))c(λx.xx)(bc)
Gilles 'SO- deja de ser malvado'
1
He publicado el contraejemplo como respuesta, con lo que pensé que sería una prueba, pero hay un paso que no puedo entender. Si alguien puede resolverlo, publique una respuesta y eliminaré la mía.
Gilles 'SO- deja de ser malvado'

Respuestas:

7

Dos contraejemplos son:

  • ( λ x . b x ( b c ) ) c(λx.bx(bc))c y ( λ x . x x ) ( b c )(λx.xx)(bc) (Plotkin).
  • ( λ x . a ( b x ) ) ( c d )(λx.a(bx))(cd) y a ( ( λ y . b ( c y ) ) d )a((λy.b(cy))d) (Van Oostrom).

El contraejemplo detallado a continuación se da en El cálculo Lambda: su sintaxis y semántica por HP Barenredgt, edición revisada (1984), ejercicio 3.5.11 (vii). Se atribuye a Plotkin (sin referencia precisa). Doy una prueba incompleta que está adaptada de una prueba de Vincent van Oostrom de un contraejemplo diferente, en Take Five: an Easy Expansion Exercise (1996) [PDF] .

La base de la prueba es el teorema de estandarización, que nos permite considerar solo las expansiones beta de una determinada forma. Intuitivamente hablando, una reducción estándar es una reducción que hace todas sus contracciones de izquierda a derecha. Más precisamente, una reducción no es estándar si hay un paso M iMi cuya redex es un residuo de una redex a la izquierda de la redex de un paso anterior M jMj ; “Izquierda” y “derecha” para una redex se definen por la posición del λλ que se elimina cuando se contrae la redex. El teorema de estandarización establece que si M β NMβN hay una reducción estándar de MM aNN .

Sea L = ( λ x . B x ( b c ) ) cL=(λx.bx(bc))c y R = ( λ x . X x ) ( b c )R=(λx.xx)(bc) . Ambos términos beta-reducen a b c ( b c )bc(bc) en un solo paso.

Supongamos que hay un ancestro común AA de tal manera que L * β A * β RLβAβR . Gracias al teorema de estandarización, podemos suponer que ambas reducciones son estándar. Sin pérdida de generalidad, suponga que AA es el primer paso donde estas reducciones difieren. De estas dos reducciones, supongamos que σσ sea ​​el lugar donde la redex del primer paso está a la izquierda del otro, y escriba A = C 1 [ ( λ z . M ) N ]A=C1[(λz.M)N] donde C 1C1 is the context of this contraction and (λz.M)N(λz.M)N is the redex. Let ττ be the other reduction.

Como ττ es estándar y su primer paso es a la derecha del agujero en C 1C1 , no puede contraerse en C 1C1 ni a la izquierda del mismo. Por lo tanto, el término final de ττ es de la forma C 2 [ ( λ z . M ) N ]C2[(λz.M)N] donde las partes de C 1C1 y C 2C2 a la izquierda de sus agujeros son idénticas, M β M MβM y N β N NβN. Dado que σσ comienza reduciendo en C 1C1 y nunca reduce más a la izquierda, su término final debe ser de la forma C 3 [ S ]C3[S] donde la parte de C 3C3 a la izquierda de su agujero es idéntica a la parte izquierda de C 1C1 y C 2C2 , y M [ z N ] * β SM[zN]βS .

Observe that each of LL and RR contains a single lambda which is to the left of the application operator at the top level. Since ττ preserves the lambda of λz.Mλz.M, this lambda is the one in whichever of LL or RR is the final term of ττ, and in that term the argument of the application is obtained by reducing NN. The redex is at the toplevel, meaning that C1=C2=C3=[]C1=C2=C3=[].

  • If ττ ends in RR, then MβzzMβzz, NβbcNβbc and M[zN]β(λx.bx(bc))cM[zN]β(λx.bx(bc))c. If NN has a descendant in LL then this descendant must also reduce to bcbc which is the normal form of NN. In particular, no descendant of NN can be a lambda, so σσ cannot contract a subterm of the form ˇNPNˇP where ˇNNˇ is a descendant of NN. Since the only subterm of LL that reduces to bcbc is bcbc, the sole possible descendant of NN in LL is the sole occurrence of bcbc itself.

  • If ττ ends in LL, then Mβbz(bc)Mβbz(bc), NβcNβc, and M[zN]β(λx.xx)(bc)M[zN]β(λx.xx)(bc). If NN has a descendant in RR then this descendant must also reduce to cc by confluence.

At this point, the conclusion should follow easily according to van Oostrom, but I'm missing something: I don't see how tracing the descendants of NN gives any information about MM. Apologies for the incomplete post, I'll think about it overnight.

Gilles 'SO- stop being evil'
fuente
0

Note that ββ-reduction can make any term disappear. Assuming that variable xx does not appear free in a term vv, you have (λx.v)t1βv(λx.v)t1βv and (λx.v)t2βv(λx.v)t2βv for any terms t1t1 and t2t2. As a consequence, the fact that reverse ββ-reduction is confluent is somewhat equivalent to: for all terms t1t1 and t2t2, there is a term uu such that uβt1uβt1 and uβt2uβt2. This seems very false to me!

Rodolphe Lepigre
fuente
2
Unless I'm mistaken, (λx.v)t1(λx.(λx.v)t1)t2(λx.v)t2(λx.v)t1(λx.(λx.v)t1)t2(λx.v)t2 works for those two terms.
xavierm02
Damn, you're right! I'll try to think of something else later, I don't have time right now.
Rodolphe Lepigre