In diesem Artikel wird vorgeschlagen , dass es Kombinatoren gibt (die symbolische Berechnungen darstellen), die vom Lambda-Kalkül nicht dargestellt werden können (wenn ich die Dinge richtig verstehe):
Es gibt einige Dinge, die man in der Praxis machen möchte und die nicht direkt in der Lambda-Rechnung ausgedrückt werden können.
Der SF-Kalkül ist ein Beispiel. Seine Ausdruckskraft ist keine Neuigkeit; Der interessante Teil der Arbeit (nicht in den Folien gezeigt) ist die Kategorietheorie dahinter. Der SF-Kalkül ist analog zu einer lisp-Implementierung, bei der Sie Funktionen erlauben, die Darstellung ihres Arguments zu überprüfen - so können Sie Dinge wie (print (lambda (x) (+ x 2)))⟹ schreiben "(lambda (x) (+ x 2))".
Ein weiteres wichtiges Beispiel ist Plotkins Parallele oder . Intuitiv ausgedrückt gibt es ein allgemeines Ergebnis, das besagt, dass die Lambda-Rechnung sequentiell ist: Eine Funktion, die zwei Argumente benötigt, muss eines auswählen, um zuerst ausgewertet zu werden. Es ist unmöglich, einen Lambda-Term orso zu schreiben, dass ( or⊤ ⊤) ⟹ ⊤, ( or⊥ ⊥) ⟹ ⟹ und or⊥ ⊥ ⊥ (wobei ⊥ ein nicht terminierender Term und and ein terminierender Term ist). Dies wird als "parallel" oder "parallel" bezeichnet, da eine parallele Implementierung einen Schritt jeder Reduzierung ausführen und anhalten kann, wenn eines der Argumente endet.
Eine weitere Sache, die Sie im Lambda-Kalkül nicht tun können, ist die Eingabe / Ausgabe. Sie müssten dafür zusätzliche Primitive hinzufügen.
Natürlich können alle diese Beispiele in der Lambda-Rechnung dargestellt werden, indem eine Indirektionsebene hinzugefügt wird, die im Wesentlichen Lambda-Terme als Daten darstellt. Aber dann wird das Modell weniger interessant - Sie verlieren die Beziehung zwischen Funktionen in der modellierten Sprache und Lambda-Abstraktionen.
Die Antwort auf Ihre Frage hängt davon ab, wie Sie "Berechnungen" und "dargestellt" definieren. Der Thread zu LtU, den sclv erwähnt hat, besteht zumeist aus Personen, die aufgrund falscher Definitionen verschiedener Begriffe aneinander vorbeigehen.
Die Unterscheidung betrifft sicherlich nicht die Rechenleistung - jedes betrachtete System ist Turing-äquivalent. Es geht darum, dass bloße Turing-Äquivalenz nichts über die Struktur oder Semantik eines Ausdrucks aussagt. Was das betrifft, in extrem minimalistischen Berechnungsmodellen , die komplexen Kodierungen oder nicht-triviale Anfangszustände erfordern, kann es sogar unklar sein , ob ein System ist universell Berechnung der Lage ist oder ob eine Illusion der Allgemeinheit wird von jemandes Interpretation des Systems erstellt . In dieser Mailingliste finden Sie beispielsweise Informationen zu einer Turing-Maschine mit zwei Zuständen und drei Symbolen, insbesondere zu den von Vaughan Pratt angesprochenen Bedenken.
Auf jeden Fall wird unterschieden zwischen:
Turing-Äquivalenz impliziert nur, dass ein System das dritte Kriterium für eine berechenbare Funktion erfüllt, wohingegen es häufig das erste Kriterium ist, das uns interessiert, entweder in einem formalen Logiksystem oder in einer Programmiersprache (in welchem Ausmaß sich diese tatsächlich unterscheiden).
Das ist eine sehr informelle Beschreibung, aber die Grundidee kann präziser formuliert werden. In dem oben erwähnten LtU-Thread finden sich einige Verweise auf bestehende Arbeiten in ähnlicher Weise.
Sowohl Schönfinkels kombinatorische Logik als auch die λ-Rechnung von Church wurden ursprünglich als destillierte Abstraktionen logischen Denkens entworfen, und als solche bildet ihre Struktur sehr genau auf logisches Denken ab und umgekehrt. Sie tragen auch eine Annahme von Extensionalität , wie durch die Eta-Reduktionsregel beschrieben: λx. f x, wo xtritt nicht auf , in f, entspricht nur fallein.
In der Praxis kann ein sehr strenger Begriff der Extensionalität zu einschränkend sein, während eine ungehemmte Intensionalität die lokale Argumentation über Unterausdrücke schwierig oder unmöglich macht.
Der SF-Kalkül ist ein modifizierter Kombinator-Kalkül, der als primitive Operation eine eingeschränkte Form der Intensionsanalyse bietet: Die Fähigkeit, teilweise angewendete Ausdrücke zu dekonstruieren, jedoch keine primitiven Werte oder nicht normalisierten Ausdrücke. Dies lässt sich gut auf Ideen wie Pattern Matching abbilden, wie sie in ML-ähnlichen Programmiersprachen oder Makros in Lisps zu finden sind, kann aber nicht in SK- oder λ-Calculus beschrieben werden, ohne effektiv einen Interpreter zur Auswertung von "intensionalen" Begriffen zu implementieren.
Zusammenfassend: Der SF-Kalkül kann nicht direkt im λ-Kalkül in dem Sinne dargestellt werden, dass die bestmögliche Darstellung höchstwahrscheinlich die Implementierung eines SF-Kalkül-Interpreters beinhaltet, und der Grund dafür ist ein grundlegender semantischer Unterschied: Haben Ausdrücke interne Struktur oder sind sie nur durch ihr äußeres Verhalten definiert?
Der SF-Kalkül von Barry Jay ist in der Lage, die Struktur von Begriffen zu untersuchen, auf die er angewendet wird. Die Lambda-Rechnung und die traditionelle kombinatorische Logik sind rein funktional und können dies nicht.
Es gibt viele Erweiterungen des Lambda-Kalküls, die Dinge tun, die gegen die Reinheit verstoßen. Für die meisten muss die Umschreibestrategie bis zu einem gewissen Grad festgelegt werden, z. B. das Hinzufügen von Status, Steuerelementen (z. B. über Fortsetzungen) oder logischen Variablen.
quelle