Niech będzie redukcją w rachunku . Zdefiniuj rozszerzenie przez .
Czy zbieżny? Innymi słowy, nie mamy, że dla każdego , jeżeli , to istnieje taki sposób, że ?
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 , to ). 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 . Aż do nazw , możemy założyć, że i że pod tym względem ani ani jest darmowe.
(Rzut) Jeśli nie jest wolny w mamy , a zatem .
Naiwny dowód indukcyjny (na i ) dla sprawy (u góry) byłby następujący:
Jeśli jest zmienną ,
Jeśli hipoteza staje , i faktycznie mają .
Jeśli , możemy po prostu użyć (Rzut).
Obowiązują te same dowody, ponieważ jest zmienną.
Dla i hipoteza staje i hipoteza indukcyjna daje takie, że co oznacza, że . Niestety nie mamy . (To sprawia, że myślę oredukcji .)
Podobny problem pojawia się w przypadku aplikacji: nie są tam, gdzie powinny być.
źródło
Odpowiedzi:
Dwa kontrprzykłady to:
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 krokMi 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 .
NiechL=(λ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 1A L←∗βA→∗βR A σ A=C1[(λz.M)N] C1 jest 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[z←N]→∗βS .
Zauważ, że każdy zL 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[z←N]→∗β(λ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ˇP Nˇ N L bc bc N L bc
Jeśliτ kończy się na L , to M→∗βbz(bc) , N→∗βc i M[z←N]→∗β(λ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ówN daje żadnych informacji o M . Przepraszamy za niekompletny post, pomyślę o tym z dnia na dzień.
źródło
źródło