W jaki sposób nieterminalne

Myślałem o tych pytaniach:

Czy istnieje typowany rachunek lambda, który jest spójny i kompletny Turinga?

/cs/65003/if-%CE%BB-xxx-has-a-type-then-is-the-type-system-inconsistent

i już teraz istnieją trudne odpowiedzi na powiązane pytania w nietypowym otoczeniu! Mówiąc dokładniej, jestem ciekawy, czy możemy odzyskać kompletność Turinga po rozwiązaniu umowy w następujący sposób:

Pytanie: Biorąc pod uwagę (czysty) $\lambda$ term z nie słabej głowicy postaci normalnej, nie jest zawsze istnieć operator paradoksalny tak, że $t$ $Y_t$
$Y_{t} (λ x . x) = t$ $Y_t\ (\lambda x.x) = t$

Wszystkie równości są brane modulo $\beta\eta$ .

Właściwie podejrzewam, że ta wersja pytania jest fałszywa , więc można rozluźnić pytanie w kombinatorach pętlowych , w których kombinator pętli jest zdefiniowany jako taki, że dla każdego gdzie ponownie musi być kombinatorem pętli. Oczywiście wystarczy to, aby jak zwykle zdefiniować funkcje rekurencyjne. $Y$ $f$

Y f = f (Y^{'} f)

$Y\ f=f\ (Y'\ f)$

Y^{'}

$Y'$

Mówiąc bardziej ogólnie, jestem zainteresowany znalezieniem „naturalnych” sposobów przejścia od nie kończącego się do kombinatora pętli, nawet jeśli powyższe równanie nie jest spełnione. $t$

Jestem również zainteresowany słabszych wersji powyższej kwestii, np może być brane za wniosek z każdego w postaci normalnej (choć nie jestem pewien, że naprawdę pomaga). $t$ $t\equiv t_1\ t_2\ldots t_n$ $t_i$

Jak dotąd: naturalne podejście polega na przyjmowaniu i „pieprzowym” stosowaniu , np $t$ $f$

Ω := (λ x . x x) (λ x . x x)

$\Omega:=(\lambda x.x\ x)(\lambda x.x\ x)$

staje się zwykłym

Y_{Ω} := λ f . (λ x . f (x x)) (λ x . f (x x))

$Y_\Omega:= \lambda f.(\lambda x. f\ (x\ x))\ (\lambda x.f\ (x\ x))$

Chodzi o to, aby zmniejszyć wierzchołek do zastosowania lambda i zastąp go , ale następny krok jest niejasny (i jestem sceptyczny, że może to prowadzić do czegokolwiek). $t$ $\lambda x. t'$ $\lambda x.f\ t'$

Nie jestem pewien, czy rozumiem wystarczająco dużo drzew Böhm, aby zobaczyć, czy mają coś do powiedzenia, ale bardzo w to wątpię, ponieważ drzewo Böhm jest po prostu , które nie przypomina niczego dla : nieskończone drzewo abstrakcje. $\Omega$ $\bot$ $Y_\Omega$

Edycja : Mój przyjaciel zauważył, że to naiwne podejście nie działa z terminem:

(λ x . x x x) (λ x . x x x)

$(\lambda x.x\ x\ x)(\lambda x.x\ x\ x)$ Naiwne podejście dałoby

Ale toniejest kombinator punktowy! Można to naprawić, zastępując drugą aplikację

przez

(λ x . f (x x x)) (λ x . f (x x x))

$(\lambda x.f\ (x\ x\ x))(\lambda x.f\ (x\ x\ x))$

f

$f$

, ale potem

podam oryginalnego terminu. Nie jest jednak jasne, czy ten termin jest kontrprzykładem w stosunku do pierwotnego pytania (i na pewno nie jest kontrprzykładem do bardziej ogólnego).

λ y z . f y

$\lambda y z.f\ y$

f \mapsto I

$f\mapsto \mathrm{I}$

lambda-calculus combinatory-logic

— cody
źródło

Uważam, że należy wzmocnić wymóg, aby t nie miało normalnej formy głowy, aby wykluczyć również słabe formy normalnej głowy. Jeśli t jest w stanie wytworzyć lambda, to ponieważ w pozycji głowy zawsze masz kombinator punktu stałego (zaczynając od f = id), lambda powinna być przez niego wytworzona, co nie jest możliwe.

— Andrea Asperti,

@AndreaAsperti oczywiście masz rację. Poprawię pytanie.

— cody

To bardzo miłe pytanie ma kilka aspektów, więc odpowiednio ułożę tę odpowiedź. $\newcommand{\setof}[1]{\{#1\}}$ $\newcommand{\thra}{\twoheadrightarrow}$ $\newcommand{\codeof}[1]{\lceil #1 \rceil}$

1. Odpowiedź na pytanie w ramce brzmi „ nie” . Termin sugerowany przez twojego przyjaciela jest rzeczywiście kontrprzykładem. $\Omega_3 = (\lambda x.xxx)(\lambda x.xxx)$

W komentarzach zauważono wcześniej, że istnieją kontrprzykłady, takie jak „ogre” , dopóki pytanie nie ogranicza się do terminów bez słabej postaci normalnej głowy. Takie warunki są znane jako warunki zerowe . Są to warunki, które nigdy nie sprowadzają się do lambda, pod żadnym warunkiem. $K^\infty=Y K$

Do dowolnego kombinatora punktów stałych (FPC) , jest tak zwanymterminemwyciszenia(AKA „root-active”): każde jego zmniejszenie redukuje się do redeksu. $Y$ $Y I$

nie jest niemy; ani nie jest co przejawia się poprzez sprawdzenie jego zestawu reduktorów, którym jest $K^\infty$ $\Omega_3$ $-$

{Ω_{3} \underset{k}{\underset{⏟}{(λ x . x x x) \dots (λ x . x x x)}} ∣ k \in N}

$\setof{\Omega_3 \underbrace{(\lambda x. xxx) \cdots (\lambda x. xxx)}_k \mid k \in \mathbb{N}}$

Zamiast podawać dokładny argument, dlaczego jest wyciszony dla wszystkich sztuk $Y I$ (w rzeczywistości dla dowolnego kombinatora pętli) co może być pracochłonne, ale mam nadzieję, że wystarczająco jasne zajmę się oczywistym uogólnieniem twojego pytania, ograniczając się również do słów niemych. $Y$ $-$ $-$

Warunki wyciszenia są podklasą terminów zerowych, które są podklasą terminów nierozwiązywalnych. Razem są to prawdopodobnie najpopularniejsze wybory dla pojęcia „bez znaczenia” lub „nieokreślony” w rachunku lambda, odpowiadające odpowiednio trywialnym drzewom Berarducciego, Levy-Longo i B \ ". Siatka pojęć bezsensownych terminów została szczegółowo przeanalizowana przez Paulę Severi i Fer-Jana de Vriesa. [1] Nieme terminy stanowią dolny element tej sieci, tj. najbardziej restrykcyjne pojęcie „nieokreślonego”.

2. Niech będzie niemym terminem, a $M$ $Y$ być pętli syntezatora z taką właściwość, że . $YI = M$

Najpierw twierdzą, że dla świeżego zmiennej , faktycznie wygląda trochę jak $z$ $Yz$ $Y_M$ opisałeś, uzyskiwany przez „pokropienie around” jakiegoś REDUCT z . $z$ $M$

Według Church-Rosser, i mają wspólną redukcję, . Wziąć standardową redukcję . Każdy podterm odpowiada unikatowemu podtermowi ramach tej redukcji. Dla dowolnego terminu , $YI$ $M$ $M'$ $R : YI \thra_s M'$ $M'$ $YI\equiv Yz[z:=I]$ $C[N]=M'$ $R$ współczynniki jako . , gdzie środkowa noga jest słabą redukcją głowy (a ostatnia noga jest wewnętrzna). jest „strzeżony” przez jeśli ta druga odnoga zawiera pewne redeksy , a jest potomkiem podstawienia $YI \thra C[N_0] \thra_{wh} C[N_1] \thra_i C[N]$ $N$ $z$ $I P$ $I$ $[z:=I]$

Oczywiście, musi strzecniektórychsubtermów , bo w przeciwnym razie byłoby to również nieme. Z drugiej strony, należy uważać, aby nie strzec tych subtermów, które są potrzebne do nieterminacji, ponieważ w przeciwnym razie nie byłby w stanie rozwinąć nieskończonego drzewa B-omowego kombinatora pętli. $Y$ $M$

Wystarczy zatem znaleźć wyciszony termin, w którym każdy termin, każdy redukcja, jest potrzebny do nienormalizacji, w tym sensie, że umieszczenie zmiennej przed tym terminem daje termin normalizujący.

Rozważmy , gdzie . To jest jak , ale przy każdej iteracji sprawdzamy, czy wystąpienie w pozycji argumentu nie jest „blokowane” przez zmienną head, poprzez podawanie jej tożsamości. Umieszczenie przed dowolnym podtermem ostatecznie da normalną formę kształtu , gdzie każde oznacza albo , $\Psi = W W$ $W = \lambda w. w I w w$ $\Omega$ $W$ $z$ $zP_1\cdots P_k$ $P_i$ $I$ $W$ lub „ -sprinkling” owych. Więc $z$ $\Psi$ jest kontrprzykładem na pytanie uogólnione.

TWIERDZENIE. Nie ma takiego kombinatora pętli , że $Y$ . $YI = \Psi$

DOWÓD. Zbiór wszystkich reduktorów to . Aby być zamiennym za pomocą , zredukować do jednego z nich. Argument jest identyczny we wszystkich przypadkach; dla konkretności załóżmy, że $\Psi$ $\setof{WW,WIWW,IIIIWW,IIIWW,IIWW,IWW}$ $\Psi$ $YI$ . $YI \thra IIWW$

Każda standardowa redukcja może być uwzględniona jako $YI \thra_s IIWW$

\begin{aligned} Y I ↠_{w} P N_{4}, P ↠_{w} Q N_{3}, Q ↠_{w} N_{1} N_{2}, thus Y I ↠_{w} N_{1} N_{2} N_{3} N_{4} \\ N_{1} ↠ I, N_{2} ↠ I, N_{3} ↠ W, N_{4} ↠ W \end{aligned}

$\begin{align*} YI \thra_w P N_4, P \thra_w Q N_3, Q \thra_w N_1 N_2, \text{thus } YI \thra_w N_1 N_2 N_3 N_4\\ N_1 \thra I, N_2 \thra I, N_3 \thra W, N_4 \thra W \end{align*}$

się do redukcji jako oraz do redukcji rozpoczynających się od jako $YI \thra_w N_1 N_2 N_3 N_4$ $R_0$ $N_i$ . $R_i$

Te redukcje można znieść ponad podstawienie aby uzyskać tak, że to kompozycja $[z:=I]$

\begin{aligned} R_{0}^{z} : Y z ↠ z^{k} (M_{1} M_{2} M_{3} M_{4}) \\ N_{i} \equiv M_{i} [z := I] \end{aligned}

$\begin{align*} R^z_0 : Yz \thra z^k(M_1 M_2 M_3 M_4)\\ N_i \equiv M_i[z:=I] \end{align*}$

R_{0}

$R_0$

Y I \overset{R_{0}^{z} [z := I]}{↠} I^{k} (N_{1} \dots N_{4}) ↠_{w}^{k} N_{1} \dots N_{4}

$YI \stackrel{R^z_0[z:=I]}{\thra} I^k(N_1 \cdots N_4) \thra^k_w N_1 \cdots N_4$

$R_i : N_i \thra N \in \setof{I,W}$

\begin{aligned} R_{i}^{z} : M_{i} ↠ N_{i}^{z} \\ R_{i} : N_{i} \overset{R_{i}^{z} [z := I]}{↠} N_{i}^{z} [z := I] ↠_{I} N \end{aligned}

$\begin{align*} R^z_i : M_i \thra N^z_i\\ R_i : N_i \stackrel{R^z_i[z:=I]}{\thra} N^z_i[z:=I] \thra_I N \end{align*}$

$R_i$ $I$ $N^z_i[z:=I]$ $N$ $N^z_i$

$N^z_i$ $z$ $N$ $z$ $N$ $N \in \setof{I,W}$ $N^z_i$

\begin{aligned} z^{k_{1}} (λ x . z^{k_{2}} (x)) \\ z^{k_{1}} (λ w . z^{k_{2}} (z^{k_{3}} (z^{k_{5}} (z^{k_{7}} (w) z^{k_{8}} (λ x . z^{k_{9}} (x))) z^{k_{6}} (w)) z^{k_{4}} (w))) \end{aligned}

$\begin{align*} &z^{k_1}(\lambda x. z^{k_2}(x))\\ &z^{k_1}(\lambda w. z^{k_2}( z^{k_3}( z^{k_5}( z^{k_7}(w) z^{k_8}(\lambda x. z^{k_9}(x)) ) z^{k_6}(w) ) z^{k_4}(w) )) \end{align*}$

$M_1 M_2 M_3 M_4 \thra N^z_1 N^z_2 N^z_3 N^z_4$ $N^z_i$ $z$ $I$ $i =1,2$ $W$ $i=3,4$

$N^z_1 N^z_2 N^z_3 N^z_4$ should yet reduce to yield the infinite fpc Bohm tree $z(z(z(\cdots)))$ . So there must exist a "sprinkle" $z^{k_j}$ in one of the $N^z_i$ which comes infinitely often to the head of the term, yet does not block further reductions of it.

And now we are done. By inspecting each $N^z_i$ , for $i \le 4$ , and each possible value of $k_j$ , for $j \le 2+7\lfloor \frac{i-1}{2} \rfloor$ , we find that no such sprinkling exists.

For example, if we modify the last $W$ in $IIWW$ as $W^z = \lambda w. z(wIww)$ , then we get the normalizing reduction

I I W W^{z} \to I W W^{z} \to W W^{z} \to W^{z} I W^{z} W^{z} \to z (I I I I) W^{z} W^{z} ↠ z I W^{z} W^{z}

$IIWW^z \to I W W^z \to WW^z \to W^z I W^z W^z \to z (I I I I) W^z W^z \thra z I W^z W^z$

(Notice that $\Omega$ admits such a sprinkling precisely because a certain subterm of it can be "guarded" without affecting non-normalization. The variable comes in head position, but enough redexes remain below.)

3. The "sprinkling transformation" has other uses. For example, by placing $z$ in front of every redex in $M$ , we obtain a term $N = \lambda z. M_z$ which is a normal form, yet satisfies the equation $N I = M$ . This was used by Statman in [2], for example.

4. Alternatively, if you relax the requirement that $Y I = M$ , you can find various (weak) fpcs $Y$ which simulate the reduction of $M$ , while outputting a chain of $z$ s along the way. I am not sure this would answer your general question, but there are certainly a number of (computable) transformations $M \mapsto Y_M$ which output looping combinators for every mute $M$ , in such a way that the reduction graph of $Y_M$ is structurally similar to that of $M$ . For example, one can write

Y ⌈ M ⌉ z = {\begin{cases} z (Y ⌈ P [x := Q] ⌉ z) & M \equiv (λ x . P) Q \\ Y ⌈ N ⌉ z & M is not a redex and M \to_{w h} N \end{cases}

$Y \codeof{M} z = \begin{cases} z (Y \codeof{P[x:=Q]} z) &M\equiv (\lambda x.P)Q\\ Y \codeof{N} z &M \text{ is not a redex and }M \to_{wh} N \end{cases}$

[1] Severi P., de Vries FJ. (2011) Decomposing the Lattice of Meaningless Sets in the Infinitary Lambda Calculus. In: Beklemishev L.D., de Queiroz R. (eds) Logic, Language, Information and Computation. WoLLIC 2011. Lecture Notes in Computer Science, vol 6642.

[2] Richard Statman. There is no hyperrecurrent S,K combinator. Research Report 91–133, Department of Mathematics, Carnegie Mellon University, Pittsburgh, PA, 1991.

— Andrew Polonsky
źródło

This answer is great, and I will likely accept it. However, I'm not sure what the actual theorems you are describing, other than "there is no looping combinator

Y

$Y$ such that

Y I = Ω_{3}

$Y\ I=\Omega_3$ ". I think stating the theorems separately will make the arguments much easier to follow.

— cody

Good point. I just updated the answer.

— Andrew Polonsky