Lambda-Calculus-Terme, die sich auf sich selbst reduzieren

In meiner fortwährenden Suche nach dem Lambda-Kalkül erwähnt Hindley & Seldins "Lambda-Kalkül und Kombinatoren eine Einführung" die folgende Abhandlung (von Bruce Lercher), die beweist, dass der einzige reduzierbare Ausdruck derselbe ist (Modulo-Alpha-Konvertierung) ist: $(\lambda x.xx)(\lambda x.xx)$ .

Obwohl ich an das Ergebnis glaube, folge ich dem Argument überhaupt nicht.

Es ist ziemlich kurz (weniger als ein Absatz). Alle Erklärungen wären sehr willkommen.

Vielen Dank,

Charlie

Beachten Sie zunächst, dass das Ergebnis besagt, dass der einzige Beta-Redex, bei dem die rechte Seite der linken Seite gleich ist (Modulo-Alpha-Konvertierung), . Es gibt andere Begriffe, die sich auf sich selbst reduzieren und diese Redex in einem Kontext haben.$(\lambda x. x x) (\lambda x. x x)$

Ich kann sehen, wie die meisten Beweise von Lercher funktionieren, obwohl es Punkte gibt, an denen ich nicht vorbeikommen kann, ohne den Beweis geringfügig zu ändern. Nehmen wir an, dass (ich verwende = für Alpha-Äquivalenz) und gemäß der Variablenkonvention, dass x in B nicht frei vorkommt .$(\lambda x. A) B = [B/x] A$$=$$x$$B$

Zähle die Anzahl von auf der linken und rechten Seite. Die Reduktion entfernt man aus dem redex sowie diejenigen von B , und fügt so viele wie in ist B multipliziert mit der Anzahl der Vorkommen von x in A . Mit anderen Worten, wenn L ( M ) die Anzahl von λ in M ist und # x ( M ) die Anzahl von freien Vorkommen von x in M ist, dann ist 1 + L ( B ) = # x$\lambda$$B$$B$$x$$A$$L(M)$$\lambda$$M$$\#_x(M)$$x$$M$ . Die einzige Lösung für diese diophantinische Gleichung ist # x ( A ) = 2 (und L ( B ) = 1, aber wir werden diese Tatsache nicht verwenden).$1 + L(B) = \#_x(A) \times L(B)$$\#_x(A) = 2$$L(B)=1$

Ich verstehe Lerchers Argument für den obigen Absatz nicht. Er zählt die Anzahl der - und Atomterme; Schreiben wir dieses # ( M ) . Die Gleichung lautet # ( B ) + 1 = # x ( A ) × ( # ( B ) - 1 ) und hat zwei Lösungen: # x ( A ) = 2 , # ( B ) = 3 und # x ( $\lambda$$\#(M)$$\#(B) + 1 = \#_x(A) \times (\#(B) - 1)$$\#_x(A)=2, \#(B)=3$ . Ich sehe keinen offensichtlichen Weg, um die zweite Möglichkeit auszuschließen.$\#_x(A)=3, \#(B)=2$

Wenden wir nun dieselbe Argumentation auf die Anzahl der Subtermen an, die auf beiden Seiten gleich . Die Reduktion entfernt eine in der Nähe der Spitze und fügt so viele hinzu, wie x in A , dh 2, substituiert ist . Daher muss eine weitere Stelle von B verschwinden; da die in A bleiben (weil B kein freies x enthält ), muss das zusätzliche Vorkommen von B auf der linken Seite λ x sein . A .$B$$x$$A$$B$$A$$B$$x$$B$$\lambda x. A$

Ich verstehe nicht, wie Lercher schlussfolgert, dass kein B als Subterm hat, aber dies ist für den Beweis tatsächlich nicht relevant.$A$$B$

Nach der Anfangshypothese ist eine Anwendung. Dies kann nicht der Fall sein, wenn A = x , daher ist A selbst eine Anwendung M N mit λ x . M N = [ ( λ x . M N ) / x ] M = [ ( λ x . M N ) / x ] $[(\lambda x. A)/x] A$$A = x$$A$$M N$$\lambda x.M N = [(\lambda x. M N)/x] M = [(\lambda x. M N)/x] N$. Da sich nicht als Subterm haben kann , kann M nicht die Form λ x haben . P , also M = x . In ähnlicher Weise ist N = x .$M$$M$$\lambda x.P$$M = x$$N = x$

Ich bevorzuge einen Beweis ohne Zählargumente. Nehmen wir an, dass .$(\lambda x. A) B = [B/x] A$

Wenn dann haben wir ( λ x . A ) B = B , was nicht möglich ist, da B kein Teil von sich sein kann. Da also die rechte Seite der Hypothese gleich einer Anwendung ist, muss A eine Anwendung A 1 A 2 und λ x sein . A = [ B / x ] A 1 und B = [ B / x ] A 2 .$A = x$$(\lambda x. A) B = B$$B$$A$$A_1 A_2$$\lambda x. A = [B/x] A_1$$B = [B/x] A_2$

Aus der ersteren Gleichung ergibt sich entweder oder A 1 = λ x . [ B / x ] A . Im zweiten Fall ist A 1 = λ x . ( λ x . A 1 A 2 ) B , was nicht möglich ist, da $ A_1 kein Teil von sich sein kann.$A_1 = x$$A_1 = \lambda x. [B/x] A$$A_1 = \lambda x. (\lambda x. A_1 A_2) B$

$A_2 = x$$A_2$$x$$B$$A_2 = B$

$A = x x$$B B$$B = \lambda x. A$ = $\lambda x. x x$.