Der Festkomma-Kombinator FIX (auch als Y-Kombinator bezeichnet) im (untypisierten) Lambda-Kalkül ( ) ist definiert als:
Ich verstehe seinen Zweck und kann die Ausführung seines Antrags einwandfrei verfolgen. Ich würde gerne verstehen, wie man FIX aus ersten Prinzipien ableitet .
So weit komme ich, wenn ich versuche, es selbst abzuleiten:
- FIX ist eine Funktion: FIX
- FIX übernimmt eine andere Funktion, , um sie rekursiv zu machen: FIX
- Das erste Argument der Funktion ist der "Name" der Funktion, der verwendet wird, wenn eine rekursive Anwendung beabsichtigt ist. Daher sollten alle Vorkommen des ersten Arguments von durch eine Funktion ersetzt werden, und diese Funktion sollte den Rest der Argumente von f erwarten (nehmen wir einfach an, dass ein Argument annimmt): FIX
Hier weiß ich nicht, wie ich in meinen Überlegungen "einen Schritt machen" soll. Die kleinen Ellipsen zeigen an, wo meinem FIX etwas fehlt (obwohl ich das nur durch einen Vergleich mit dem "echten" FIX erkennen kann).
Ich habe bereits Typen und Programmiersprachen gelesen , die es nicht direkt abzuleiten versuchen, sondern den Leser für eine Herleitung an den kleinen Schemer verweisen . Ich habe das auch gelesen und seine "Ableitung" war nicht so hilfreich. Darüber hinaus handelt es sich weniger um eine direkte Herleitung als vielmehr um die Verwendung eines ganz bestimmten Beispiels und einen Ad-hoc-Versuch, eine geeignete rekursive Funktion in \ lambda zu schreiben .
Antworten:
Ich habe das nirgendwo gelesen, aber ich glaube, hätte so abgeleitet werden können:Y
Lassen Sie uns eine rekursive Funktion , vielleicht eine Fakultät oder etwas Ähnliches. Informell definieren wir als Pseudo-Lambda-Term, wobei in seiner eigenen Definition vorkommt:f ff f f
Zunächst stellen wir fest, dass der rekursive Aufruf als Parameter ausgeschlossen werden kann:
Jetzt könnten wir definieren, wenn wir nur eine Möglichkeit hätten, es als Argument an sich selbst weiterzugeben. Dies ist natürlich nicht möglich, weil wir zur Hand haben. Was wir bei der Hand haben , ist . Da alles enthält, was wir brauchen, um zu definieren , können wir versuchen, als Argument anstelle von und später daraus zu rekonstruieren . Unser erster Versuch sieht so aus:f M M f M f ff f M M f M f f
Dies ist jedoch nicht ganz richtig. Zuvor wurde in ersetzt . Aber jetzt übergeben wir stattdessenWir müssen irgendwie alle Stellen reparieren, an denen wir damit sie aus rekonstruieren . Eigentlich ist das gar nicht so schwer: Da wir nun wissen, dass , ersetzen wir überall, wo wir , einfach durch .r M M r f M f = M M r ( r r )f r M M r f M f=MM r (rr)
Diese Lösung ist gut, aber wir mussten innen ändern . Das ist nicht sehr praktisch. Wir können dies eleganter tun, ohne modifizieren zu müssen, indem wir ein anderes einführen , das das Argument an sendet, das auf sich selbst angewendet wird: Indem wir als wirM λ M M ' λ x . M ( x x )M M λ M M′ λx.M(xx)
Auf diese Weise wird, wenn für , für , was durch die Definition gleich . Dies gibt uns eine nicht-rekursive Definition von , ausgedrückt als gültiger Lambda-Ausdruck!x M M r f fM x MM r f f
Der Übergang zu ist jetzt einfach. Wir können einen beliebigen Lambda-Term anstelle von und diese Prozedur darauf anwenden. So können wir ausrechnen und definierenM MY M M
Tatsächlich reduziert sich auf wie wir es definiert haben.fYM f
Anmerkung: Ich habe abgeleitet, wie es in der Literatur definiert ist. Der von Ihnen beschriebene Kombinator ist eine Variante von für Call-by-Value- Sprachen, manchmal auch . Siehe diesen Wikipedia-Artikel .Y ZY Y Z
quelle
Yuval hat darauf hingewiesen, dass es nicht nur einen Festkommaoperator gibt. Es gibt viele von ihnen. Mit anderen Worten, die Gleichung für den Fixpunktsatz hat keine einzige Antwort. Sie können den Operator also nicht von ihnen ableiten.
Es ist wie zu fragen, wie Menschen als Lösung für ableiten . Sie nicht! Die Gleichung hat keine eindeutige Lösung.x = y(x,y)=(0,0) x=y
Nur für den Fall, dass Sie wissen möchten, wie der erste Fixpunktsatz entdeckt wurde. Lassen Sie mich sagen, dass ich mich auch gefragt habe, wie sie zu den Fixpunkt- / Rekursionssätzen gekommen sind, als ich sie zum ersten Mal gesehen habe. Es scheint so genial. Insbesondere in der Form der Berechenbarkeitstheorie. Anders als Yuval sagt, ist es nicht so, dass die Leute herumgespielt haben, bis sie etwas gefunden haben. Folgendes habe ich gefunden:
Soweit ich mich erinnere, stammt der Satz ursprünglich von SC Kleene. Kleene gelangte zu dem ursprünglichen Fixpunktsatz, indem er den Beweis der Inkonsistenz von Churchs ursprünglichem Lambda-Kalkül rettete. Der ursprüngliche Lambda-Kalkül der Kirche litt unter einem Russel-Typ-Paradoxon. Der modifizierte Lambda-Kalkül vermeidet das Problem. Kleene untersuchte den Inkonsistenznachweis wahrscheinlich, um festzustellen, ob der modifizierte Lambda-Kalkül unter einem ähnlichen Problem leiden würde, und wandelte den Inkonsistenznachweis in einen nützlichen Satz des modifizierten Lambda-Kalküls um. Durch seine Arbeiten zur Äquivalenz von Lambada-Kalkül mit anderen Rechenmodellen (Turing-Maschinen, rekursive Funktionen usw.) übertrug er sie auf andere Rechenmodelle.
Wie kann man den Operator ableiten, den man fragen könnte? Hier ist, wie ich daran denke. Beim Fixpunktsatz geht es darum, die Selbstreferenz zu entfernen.
Jeder kennt das Lügnerparadoxon:
Oder in der mehr sprachlichen Form:
Jetzt denken die meisten Leute, dass das Problem mit diesem Satz in der Selbstreferenz liegt. Es ist nicht! Die Selbstreferenz kann beseitigt werden (das Problem ist die Wahrheit, eine Sprache kann im Allgemeinen nicht über die Wahrheit ihrer eigenen Sätze sprechen, siehe Tarskis Undefinierbarkeit des Wahrheitssatzes ). Das Formular, in dem die Selbstreferenz entfernt wird, lautet wie folgt:
Keine Selbstreferenz, wir haben Anweisungen, wie man einen Satz konstruiert und dann etwas daraus macht. Und der Satz, der aufgebaut wird, entspricht den Anweisungen. Beachten Sie, dass wir in -calculus keine Anführungszeichen benötigen, da es keinen Unterschied zwischen Daten und Anweisungen gibt.λ
Wenn wir dies analysieren, haben wir wobei die Anweisung ist, zu konstruieren und etwas dagegen zu tun.M x x xMM Mx xx
So ist und wir habenM λx.f(xx)
Dies ist für eine feste . Wenn Sie es zu einem Operator machen möchten, fügen Sie einfach und wir erhalten :f λf Y
Also denke ich nur an das Paradoxon ohne Selbstreferenz und das hilft mir zu verstehen, worum es bei geht.Y
quelle
Sie müssen also einen Festkomma-Kombinator definieren
aber ohne explizite Rekursion. Beginnen wir mit dem einfachsten irreduziblen Kombinator
Das
x
im ersten Lambda wird immer wieder durch das zweite Lambda ersetzt. Einfache Alpha-Konvertierung macht diesen Prozess klarer:Dh die Variable im ersten Lambda verschwindet immer. Wenn wir also ein
f
zum ersten Lambda hinzufügender
f
wird aufspringenWir haben unseren
omega
Rücken. Es sollte jetzt klar sein, dass, wenn wir einf
zum zweiten Lambda addieren , dasf
im ersten Lambda erscheint und es sich dann dreht:Schon seit
wir können den Ausdruck umschreiben als
welches ist gerade
und wir haben unsere Gleichung
Y f = f (Y f)
. DerY
Kombinator ist also im Wesentlichenf
f
rauf und raufquelle
Möglicherweise haben Sie das klassische Beispiel einer Gleichung ohne Normalform gesehen:
Eine ähnliche Gleichung wird für die allgemeine Rekursion vorgeschlagen:
(A) ist eine Möglichkeit, allgemeine rekursive Gleichungen im Lambda-Kalkül zu schreiben (jenseits von primitiv rekursiv). Wie löst man die Gleichung ? Geben Sie in der obigen Gleichung für , um Folgendes zu erhalten:Yf=f(Yf) f R
Y = λ f . ( λ x . f ( x x ) ) ( λ x . f ( x x ) )
quelle