Ein Quine in reinem Lambda

Ich hätte gerne ein Beispiel für ein Quin in reinem Lambda-Kalkül . Ich war ziemlich überrascht, dass ich durch googeln keinen finden konnte. Die Quine-Seite listet Quines für viele "echte" Sprachen auf, jedoch nicht für die Lambda-Rechnung.

Dies bedeutet natürlich, zu definieren, was ich mit einem Quin im Lambda-Kalkül meine, was ich unten tue. (Ich bitte um etwas ganz bestimmtes.)

An einigen Stellen, z. B. bei Larkin und Stocks (2004), sehe ich das Folgende als einen "selbstreplizierenden" Ausdruck zitiert: $(\lambda x.x \; x)\;(\lambda x.x \; x)$ . Dies reduziert sich nach einem einzigen Beta-Reduktionsschritt auf sich selbst und verleiht ihm ein irgendwie quineartiges Gefühl. Es ist jedoch insofern ungewöhnlich, als es nicht beendet wird: Weitere Beta-Reduktionen produzieren weiterhin den gleichen Ausdruck, sodass es niemals auf die normale Form reduziert wird. Für mich ist ein Quine ein Programm, das sich selbst beendet und ausgibt, und daher möchte ich einen Lambda-Ausdruck mit dieser Eigenschaft.

Natürlich ist jeder Ausdruck, der keine Redexes enthält, bereits in normaler Form und wird sich daher selbst beenden und ausgeben. Aber das ist zu trivial. Daher schlage ich die folgende Definition vor, in der Hoffnung, dass eine nicht triviale Lösung zugelassen wird:

Definition (vorläufig): Ein Quine im Lambda-Kalkül ist ein Ausdruck der Form

(λ x . EIN)

$(\lambda x . A)$ (wobei

A

$A$ für einen bestimmten Lambda-Kalkül-Ausdruck steht), so dass

((λ x . A) y)

$((\lambda x . A)\,\, y)$ wird

(λ x . A)

$(\lambda x . A)$ oder etwas Äquivalentes unter Änderungen von Variablennamen, wenn es auf die normale Form reduziert wird, fürjedeEingabe

y

$y$ .

Angesichts der Tatsache, dass der Lambda-Kalkül genauso aussieht wie jede andere Sprache, scheint dies möglich zu sein, aber mein Lambda-Kalkül ist rostig, sodass ich mir kein Beispiel vorstellen kann.

Referenz

James Larkin und Phil Stocks. (2004) "Selbstreplizierende Ausdrücke in der Lambda-Rechnung" Konferenzen in Forschung und Praxis in der Informationstechnologie, 26 (1), 167-173. http://epublications.bond.edu.au/infotech_pubs/158

lambda-calculus Nathaniel
quelle

Keine Antwort auf meine Frage, aber für meine eigene zukünftige Referenz (und für zukünftige Besucher) wird es nützlich sein, einen Link zu wiki.haskell.org/Combinatory_logic zu haben , in dem sich jemand viel tiefer mit Quines befasst als ich.

Nathaniel

Beachten Sie, dass ein Quine seinen eigenen Quellcode erzeugen muss . Das Produzieren der Funktion, die es darstellt, ist nicht ausreichend.

PyRulez

@ PyRulez Was ist der Quellcode für einen Lambda-Ausdruck? Wenn es sich um eine Folge von Zeichen handelt, kann ein Lambda-Ausdruck diese nicht ausgeben, und folglich können wir das Wort "quine" so definieren, dass es für Lambda-Ausdrücke etwas anderes bedeutet, ohne dass Mehrdeutigkeiten befürchtet werden. Wenn Sie andererseits den Quellcode als Lambda-Expession selbst betrachten, sind "der Quellcode" und "die Funktion, die er darstellt" dasselbe. Also denke ich, dass es mir hier gut geht.

Nathaniel

Es gibt eine Kirche, die für Streicher kodiert. Ein Lambda Calculus Quine sollte die Kirchencodierung der Zeichenfolge ausgeben, die es darstellt.

PyRulez

Klar, das ist nicht schwer, wenn man es so definiert. Bei dieser Frage ging es um etwas anderes.

Nathaniel

Antworten:

Sie möchten einen Begriff , so dass : $Q$ $\forall M \in \Lambda$

Q M ⊳_{β} Q

$QM \rhd_\beta Q$

Ich werde nicht weiter einschränken (z. B. in Bezug auf seine Form und ob es normalisiert) und ich werde Ihnen zeigen, dass es definitiv nicht normalisiert sein muss. $Q$

Angenommen, ist in normaler Form. Wählen Sie (wir können dies tun, weil der Satz für alle ). Dann gibt es drei Fälle. $Q$ $M \equiv x$ $M$
- ist ein Atom . Dann ist . Dies ist nicht reduzierbar . $Q$ $a$ $QM \equiv ax$ $a$
- ist irgendeine Anwendung . Dann ist . ist hypothetisch eine Normalform, daher ist auch in Normalform und nicht auf reduzierbar. $Q$ $(RS)$ $QM \equiv (RS)x$ $(RS)$ $(RS)x$ $(RS)$
- ist eine Abstraktion (wenn in frei sein soll, könnenwir der Einfachheit halber einfach wählen, das der Variablen entspricht,über die abstrahiert wird). Dann . Da in normaler Form vorliegt, gilt dies auch für $Q$ $(\lambda x.A)$ $x$ $A$ $M$ $\lambda$ $QM \equiv (\lambda x.A)x \rhd_\beta A[x/x] \equiv A$ $(\lambda x.A)$ $A$ . Folglich können wir auf reduzieren . $A$ $(\lambda x.A)$
Wenn also ein solches existiert, kann es nicht in normaler Form vorliegen. $Q$
Der Vollständigkeit halber suppose hat eine normale Form, ist aber nicht in Normalform (vielleicht ist es schwach Normalisieren ist), dh mit , so dass : $Q$ $\exists N \in \beta\text{-nf}$ $N \not\equiv Q$ $\forall M \in \Lambda$
$Q M ⊳_{β} Q ⊳_{β} N$

Dann muss mit auch eine Reduktionsfolge , weil: $M \equiv x$ $Qx \rhd_\beta Nx \rhd_\beta N$
- ist möglich durch die Tatsachedass . $Qx \rhd_\beta Nx$ $Q \rhd_\beta N$
- muss sich normalisieren, da ein nf und nur ein Atom ist. $Nx$ $N$ $\beta$ $x$
- Wenn sich auf etwas anderes als normalisieren sollte , dann hat zwei nfs, was durch eine Folgerung aus dem Church-Rosser-Theorem nicht möglich ist. (Der Church-Rosser-Satz besagt im Wesentlichen, dass Reduktionen konfluent sind, wie Sie wahrscheinlich bereits wissen.) $Nx$ $N$ $Qx$ $\beta$
Beachten Sie jedoch, dass durch das obige Argument (1) nicht möglich ist, sodass unsere Annahme, dass eine normale Form hat, nicht haltbar ist. $Nx \rhd_\beta N$ $Q$
Wenn wir ein solches zulassen , sind wir sicher, dass es nicht normalisierend sein darf. In diesem Fall können wir einfach einen Kombinator verwenden, der alle Argumente eliminiert, die er erhält. Denis Vorschlag funktioniert gut: Dann in nur zwei -Reduktionen: $Q$
$Q \equiv (λ z . (λ x . λ z . (x x)) (λ x . λ z . (x x)))$ $Q \equiv (\lambda z.(λx.λz.(x x)) (λx.λz.(x x)))$ $\beta$ $\begin{aligned} Q M & \equiv (λ z . (λ x . λ z . (x x)) (λ x . λ z . (x x))) M \\ ⊳_{1 β} (λ x . λ z . (x x)) (λ x . λ z . (x x)) \\ ⊳_{1 β} (λ z . ((λ x . λ z . (x x)) (λ x . λ z . (x x))) \\ \equiv Q \end{aligned}$ $\begin{align} QM &\equiv (\lambda z.(λx.λz.(x x)) (λx.λz.(x x))) M \\ & \rhd_{1\beta} (λx.λz.(x x)) (λx.λz.(x x)) \\ & \rhd_{1\beta} (λz.((λx.λz.(x x))(λx.λz.(x x))) \\ & \equiv Q \end{align}$

Dieses Ergebnis ist nicht sehr überraschend, da Sie im Wesentlichen nach einem Begriff fragen, der alle Argumente beseitigt, und dies ist etwas, das ich oft als direkte Anwendung des Festkomma-Theorems erwähne.

Roy O.
quelle

Wenn ich Denis 'Antwort auch akzeptieren könnte, würde ich es tun, aber (nachdem ich ein bisschen mehr gelernt und es vollständig verstanden hatte) war es diese Antwort, die mich wirklich davon überzeugt hat, dass dieser "Quine Combinator" nicht von einem implementiert werden kann Lambda-Ausdruck in normaler Form.

Nathaniel

Einerseits ist dies unmöglich, da ein Quine seinen eigenen Code ausgeben soll und der reine Lambda-Kalkül keine Möglichkeit zur Ausgabe hat.

Wenn Sie andererseits annehmen, dass der resultierende Term die Ausgabe ist, ist jede normale Form eine Quine.

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

Dave Clarke
quelle

Das ist ein interessanter Punkt. In der Frage habe ich versucht, eine Definition dessen zu geben, was im Lambda-Kalkül als nicht-triviales Quin gelten könnte: eine Funktion, die, wenn sie auf eine Eingabe angewendet wird, das Beta auf sich selbst reduziert (bis zu Variablennamensubstitutionen). Es mag sein, dass dies unmöglich ist, aber es ist zumindest für mich nicht offensichtlich.

Nathaniel

Hier ist ein Vorschlag:

$A$ $f=\lambda t. (\lambda z.t)$

$Y=\lambda g.((\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x)))$ $A=Y f=(\lambda x.\lambda z.(x\ x))\ (\lambda x.\lambda z.(x\ x))$

$A$ $A$ $\lambda z.A$ $y$ $(\lambda z.A)y \to_\beta A \to_\beta (\lambda z.A)$

Denis
quelle

(λ z . A) y

$(\lambda z.A)\;y$

(λ z . A)

$(\lambda z.A)$

A

$A$

y

$y$

y

$y$

y

$y$

A

$A$

(λ z . A) y

$(\lambda z.A)y$

A

$A$

A

$A$

λ z . A

$\lambda z.A$

A

$A$

λ - c a l c u l u s

$\lambda-calculus$

Ahh, du hast natürlich recht. Ich hätte das sehen sollen. Ich bin nicht sicher, ob ich Ihre Antwort akzeptieren oder die Frage bearbeiten soll, um eine bessere Definition zu erhalten. Ich werde es mir etwas überlegen. (Es scheint mir immer noch, dass es möglich sein sollte, eine nicht triviale Definition zu geben, in der Sie nach etwas fragen, das enden wird, aber ich bin nicht sicher, wie.)

Nathaniel

z

$z$

z

$z$

A

$A$

A

$A$ if z==p then return q, otherwise return q