Czy najgłębsze redukcje są wieczne w nietypowym rachunku λ?

(Pytałem już o to na MathOverflow, ale nie otrzymałem tam odpowiedzi).

tło

W niepisanym rachunku lambda termin może zawierać wiele powtórzeń, a różne wybory, które należy zmniejszyć, mogą dawać bardzo różne wyniki (np. które w jednym krok ( -) zmniejsza się do lub do siebie). Różne (sekwencje) wyborów miejsca redukcji nazywane są strategiami redukcji . Mówi się, że termin normalizuje się, jeśli istnieje strategia redukcji, która doprowadza do normalnej postaci. Mówi się, że termin silnie normalizuje się, jeśli każda strategia redukcji przynosi $(\lambda x.y)((\lambda x.xx)\lambda x.xx)$ $\beta$ $y$ $t$ $t$ $t$ $t$ do normalnej postaci. (Nie martwię się o to, ale przecięcie gwarantuje, że nie może być więcej niż jedna możliwość).

Mówi się, że strategia redukcji jest normalizująca (i jest w pewnym sensie najlepsza z możliwych), jeśli kiedykolwiek ma normalną formę, to właśnie tam skończymy. Strategia najbardziej wysunięta na lewo jest normalizująca. $t$

Na drugim końcu spektrum mówi się, że strategia redukcji jest wieczysta (i jest w pewnym sensie najgorsza możliwa), jeśli kiedykolwiek istnieje nieskończona sekwencja redukcji od terminu , strategia znajduje taką sekwencję - innymi słowy, moglibyśmy się nie znormalizować, to zrobimy. $t$

Znam strategie ciągłej redukcji i podane odpowiednio przez: i (W obu przypadkach wskazany redeks jest skrajnie lewy w nazwie - i dla normalnych form strategie redukcji są koniecznie identyczne.) Strategia $F_\infty$ $F_{bk}$

\begin{array}{ll} {fa}_{b k} (do [(λ x . s) t]) = do [s [t / x]] & gdyby t jest silnie normalizujący \\ {fa}_{b k} (do [(λ x . s) t]) = do [(λ x . s) {fa}_{b k} (t)] & Inaczej \end{array}

$\begin{array}{ll} F_{bk}(C[(\lambda x.s)t])=C[s[t/x]] & \text{if $t$ is strongly normalizing} \\ F_{bk}(C[(\lambda x.s)t])=C[(\lambda x.s)F_{bk}(t)] & \text{otherwise} \end{array}$

\begin{array}{ll} {fa}_{\infty} (do [(λ x . s) t]) = do [s [t / x]] & gdyby x występuje s, albo jeśli t jest w normalnej formie \\ {fa}_{\infty} (do [(λ x . s) t]) = do [(λ x . s) {fa}_{\infty} (t)] & Inaczej \end{array}

$\begin{array}{ll} F_\infty(C[(\lambda x.s)t])=C[s[t/x]] & \text{if $x$ occurs in $s$, or if $t$ is on normal form} \\ F_\infty(C[(\lambda x.s)t])=C[(\lambda x.s)F_\infty(t)] & \text{otherwise} \end{array}$

β

$\beta$

C [(λ x . s) t]

$C[(\lambda x.s)t]$

F_{\infty}

$F_\infty$ jest nawet maksymalne - jeśli normalizuje termin, to użył do tego najdłuższej możliwej sekwencji redukcji. (Patrz np. 13.4 w książce Barendregta.)

Rozważ teraz najbardziej lewą wewnętrzną strategię redukcji. Nieformalnie zmniejszy to tylko redeks, który nie zawiera żadnych innych redeksów. Bardziej formalnie jest to zdefiniowane przez $\beta$

\begin{array}{ll} L. (t) = t & gdyby t w normalnej formie \\ L. (λ x . s) = λ x . L. (s) & dla s nie w normalnej formie \\ L. (s t) = L. (s) t & dla s nie w normalnej formie \\ L. (s t) = s L. (t) & gdyby s, ale nie t jest w normalnej formie \\ L. ((λ x . s) t) = s [t / x] & gdyby s, t oba w normalnej formie \end{array}

$\begin{array}{ll} L(t) = t &\text{if $t$ on normal form}\\ L(\lambda x.s) = \lambda x. L(s) &\text{for $s$ not on normal form}\\ L(st) = L(s)t &\text{for $s$ not on normal form}\\ L(st) = s L(t) &\text{if $s$, but not $t$ is on normal form}\\ L((\lambda x. s)t) = s[t/x] &\text{if $s$, $t$ both on normal form} \end{array}$

Naturalną intuicją dla najbardziej lewostronnej redukcji jest to, że wykona całą pracę - nie można utracić redeksu, a więc powinna być wieczna. Ponieważ odpowiednia strategia jest wieczna dla (nietypowej) logiki kombinatorycznej (najbardziej wewnętrzne redukcje są wieczne dla wszystkich ortogonalnych TRW), nie wygląda to na całkowicie nieskrępowany niebieskooki optymizm ...

Czy skrajnie najbardziej wewnętrzna redukcja jest ciągłą strategią dla nietypowego -kalkusa? $\lambda$

Jeśli odpowiedź okaże się „nie”, wskaźnik do kontrprzykładu również byłby bardzo interesujący.

— kow
źródło

Crosspost z MO.

— Hsien-Chih Chang 張顯之

... jak wspomniano w pierwszej linii.

— kow

@kow: Tak, masz rację, i nie ma nic złego w crossspostingu :) Link ma na celu śledzenie zarówno komentarzy, jak i odpowiedzi w MO, aby zapobiec podwójnej odpowiedzi. Zobacz dyskusję na temat meta .

— Hsien-Chih Chang 張顯之

@kow: Przy następnym pytaniu krzyżowym nie zapomnij dodać linku, najlepiej w obu kierunkach.

— Tsuyoshi Ito,

L (L (s) t)

$L(L(s)t)$

s

$s$

L (s)

$L(s)$

L (L (s))

$L(L(s))$

$tt$ $t=(\lambda x. (\lambda y.1) (x x))$ $L$

$L(tt)=L(t)t=L(\lambda x.(\lambda y.1) (x x))t=(\lambda x.L((\lambda y.1) (x x)))t=(\lambda x.1)t$

$F_\infty$ $F_\infty([(\lambda x.(\lambda y.1 (x x))) t]))=(\lambda y.1) (tt)$

— Radu GRIGore
źródło