Zbieg ekspansji beta

10

Niech β będzie redukcją β w rachunku λ . Zdefiniuj β rozszerzenie β przez tβttβt .

Czy β zbieżny? Innymi słowy, nie mamy, że dla każdego l,d,r , jeżeli lβdβr , to istnieje u taki sposób, że lβuβr ?

Słowa kluczowe: zbieżność w górę, własność CR do góry nogami


Zacząłem od spojrzenia na słabszą właściwość: lokalną konfluencję (tj. Jeśli lβdβr , to lβuβr ). Nawet gdyby to była prawda, nie oznaczałoby to konfluencji, ponieważ rozszerzenie β nie kończy się, ale pomyślałem, że pomoże mi to zrozumieć przeszkody.

(Góra) W przypadku, w którym obie redukcje są na górnym poziomie, hipoteza staje (λx1.b1)a1b1[a1/x1]=b2[a2/x2](λx2.b2)a2 . Aż do nazw α , możemy założyć, że x1x2i że pod tym względem ani x1 ani x2 jest darmowe.

(Rzut) Jeśli x1 nie jest wolny w b1 mamy b1=b2[a2/x2] , a zatem (λx1.b1)a1=(λx1.b2[a2/x2])a1(λx1.(λx2.b2)a2)a1(λx2.b2)a2 .

Naiwny dowód indukcyjny (na b1 i b2 ) dla sprawy (u góry) byłby następujący:

  • Jeśli b1 jest zmienną y1 ,

    • Jeśli y1=x1 hipoteza staje (λx1.x1)a1a1=b2[a2/x2](λx2.b2)a2 , i faktycznie mają (λx1.x1)a1=(λx1.x1)(b2[a2/x2])(λx1.x1)((λx2.b2)a2)(λx2.b2)a2 .

    • Jeśli y1x1 , możemy po prostu użyć (Rzut).

  • Obowiązują te same dowody, ponieważ b2 jest zmienną.

  • Dla b1=λy.c1 i b2=λy.c2 hipoteza staje (λx1.λy.c1)a1λy.c1[a1/x1]=λy.c2[a2/x2](λx2.λy.c2)a2 i hipoteza indukcyjna dajed takie, że(λx1.c1)a1d(λx2.c2)a2 co oznacza, żeλy.(λx1.c1)a1λy.dλy.(λx2.c2)a2 . Niestety nie mamyλy.(λx2.c2)a2(λx2.λy.c2)a2 . (To sprawia, że ​​myślę oredukcjiσ .)

  • Podobny problem pojawia się w przypadku aplikacji: λ nie są tam, gdzie powinny być.

xavierm02
źródło
1
@chi O ile się nie mylę, działa. (λb.yb)y(λa.(λb.ab)y)y(λa.ay)y
xavierm02
1
W pewnym stopniu zgadzam się z @chi, że wydaje się zbieżny po tym, jak o tym pomyślisz i zobaczysz kilka kontrprzykładów. Ale właściwie co z ? (λx.xxy)yyyy(λx.yxx)y
Rodolphe Lepigre
2
Chociaż byłoby to dla mnie wygodne, gdyby to była prawda, jestem trochę bardziej pesymistą. Mój kolega poczynił następującą uwagę, która sprawia, że ​​wydaje się to mało prawdopodobne: oznaczałoby to, że można połączyć dowolne dwa dowolne programy obliczające tę samą liczbę całkowitą (kościelną).
xavierm02
2
Odpowiedź brzmi nie. Ćwiczenie 3.5.11 w Barendregt daje przeciwny przykład przypisany Plotkinowi, ale bez odniesienia: oraz ( λ x . X x ) ( b c ) . Poszukam dowodu. (λx.bx(bc))c(λx.xx)(bc)
Gilles 'SO - przestań być zły'
1
Zamieściłem kontrprzykład jako odpowiedź z tym, co uważałem za dowód, ale jest krok, którego nie potrafię zrozumieć. Jeśli ktoś może to rozgryźć, proszę opublikować odpowiedź, a ja ją usunę.
Gilles „SO- przestań być zły”

Odpowiedzi:

7

Dwa kontrprzykłady to:

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

Kontrprzykład opisany poniżej podano w The Lambda Calculus: Its Syntax and Semantics autorstwa HP Barenredgt, wydanie poprawione (1984), ćwiczenie 3.5.11 (vii). Jest to przypisywane Plotkinowi (bez dokładnego odniesienia). Daję niekompletny dowód, który został zaadaptowany z dowodu Vincenta van Oostroma z innego kontrprzykładu, w Take Five: an Easy Expansion Exercise (1996) [PDF] .

Podstawą dowodu jest twierdzenie o standaryzacji, które pozwala nam rozważać tylko rozszerzenia beta pewnej formy. Intuicyjnie mówiąc, standardowa redukcja to redukcja, która powoduje wszystkie jej skurcze od lewej do prawej. Dokładniej, taka redukcja jest niestandardowy IFF jest krok Mi którego REDEX jest rezydualną Redex do lewej strony Redex poprzedniego kroku Mj ; „Lewy” i „prawy” dla redeksu są zdefiniowane przez pozycję λ która jest eliminowana, gdy redeks jest kurczony. Twierdzenie o standaryzacji stwierdza, że ​​jeśli MβN to występuje standardowa redukcja z M doN .

Niech L=(λx.bx(bc))c oraz R=(λx.xx)(bc) . Oba terminy beta zmniejszają się do bc(bc) w jednym kroku.

Załóżmy, że istnieje wspólny przodek takie, że L * β* β R . Dzięki twierdzeniu o standaryzacji możemy założyć, że obie redukcje są standardowe. Bez utraty ogólności, załóżmy, że A jest pierwszym krokiem, w którym różnice te są różne. Z tych dwóch redukcji, niech σ będzie tą, w której redeks pierwszego kroku znajduje się na lewo od drugiego, i napisz A = C 1 [ ( λ z . M ) N ] gdzie C 1ALβAβRAσA=C1[(λz.M)N]C1jest kontekstem tego skurczu, a (λz.M)N to redeks. Niech τ będzie drugą redukcją.

Ponieważ τ jest standardem, a jego pierwszym krokiem jest na prawo od dołka w C1 , nie może się skurczyć na C1 ani na lewo od niego. W związku z tym ostateczny termin τ ma postać C2[(λz.M)N] , gdzie część C1 i C2 na lewo od ich otworów są identyczne, MβM i NβN. Ponieważ σ zaczyna się od zmniejszenia przy C1 i nigdy nie zmniejsza się dalej w lewo, jego końcowy człon musi mieć postać C3[S] gdzie część C3 na lewo od jego otworu jest identyczna z lewą częścią C1 i C2 , a M[zN]βS .

Zauważ, że każdy z L i R zawiera pojedynczą lambdę, która znajduje się po lewej stronie operatora aplikacji na najwyższym poziomie. Ponieważ τ zachowuje lambda λz.M , to Lambda jest w zależności od tego, jeden z L lub R jest ostatni termin τ i w tym okresie argument zastosowania otrzymuje się przez redukcję N . Redeks znajduje się na najwyższym poziomie, co oznacza, że C1=C2=C3=[] .

  • Jeśli τ kończy się na R , to Mβzz , Nβbc i M[zN]β(λx.bx(bc))c . Jeżeli N ma zstępnych L wówczas potomek musi zmniejszyć do bc , która jest normalnie postać N . W szczególności brak potomkaN może być lambda takσ nie może zawrzeć subterm formy N P , gdzie N jest potomkiem N . Ponieważ jedynym subterm z L , który redukuje się do b , c jest b c , jedyną możliwą potomkiem N w L jest jedynym występowanie b c siebie.NˇPNˇNLbcbcNLbc

  • Jeśli τ kończy się na L , to Mβbz(bc) , Nβc i M[zN]β(λx.xx)(bc) . Jeśli N ma potomka w R potomek ten musi również zredukować do c przez zbieg.

W tym momencie, wniosek powinien być zgodny z łatwością według van Oostrom, ale jestem czegoś brakuje: Nie widzę jak śledzenie potomków N daje żadnych informacji o M . Przepraszamy za niekompletny post, pomyślę o tym z dnia na dzień.

Gilles „SO- przestań być zły”
źródło
0

βxv(λx.v)t1βv(λx.v)t2βvt1t2βt1t2uuβt1uβt2

Rodolphe Lepigre
źródło
2
(λx.v)t1(λx.(λx.v)t1)t2(λx.v)t2
Cholera, masz rację! Później spróbuję wymyślić coś innego, nie mam teraz czasu.
Rodolphe Lepigre