Wie kann man den Lambda-Kalkül ohne Typensystem stark normalisieren?

9

Gibt es ein System ähnlich dem Lambda-Kalkül, das sich stark normalisiert, ohne dass ein Typsystem hinzugefügt werden muss?

MaiaVictor
quelle
5
Die Frage ist etwas unkonzentriert: Was meinst du mit "ähnlich"? Sind endliche Zustandsautomaten ähnlich? Der Kalkül ist ein universelles Berechnungsmodell, daher wird alles, was ihm "ähnlich" ist, wahrscheinlich nicht terminierende Berechnungsformen aufweisen. λ
Martin Berger

Antworten:

22

Ich kann mir einige mögliche Antworten aus der linearen Logik vorstellen.

Der einfachste ist der affine Lambda-Kalkül: Betrachten Sie nur Lambda-Terme, in denen jede Variable höchstens einmal vorkommt. Dieser Zustand bleibt durch Reduktion erhalten und es ist sofort ersichtlich, dass die Größe der affinen Terme mit jedem Reduktionsschritt streng abnimmt. Daher normalisiert sich der untypisierte affine Lambda-Kalkül stark.

Interessantere Beispiele (in Bezug auf die Ausdruckskraft) sind die sogenannten "leichten" Lambda-Kalküle, die sich aus den von Girard in "Light Linear Logic" (Information and Computation 143, 1998) eingeführten Subsystemen der linearen Logik ergeben als Lafonts "Soft Linear Logic" (Theoretical Computer Science 318, 2004). Es gibt mehrere solcher Kalküle in der Literatur, vielleicht ist Teruis "Lichtaffine Lambda-Kalkül- und Polynomzeit-starke Normalisierung" eine gute Referenz (Archive for Mathematical Logic 46, 2007). In dieser Arbeit definiert Terui einen Lambda-Kalkül, der aus der lichtaffinen Logik abgeleitet ist, und beweist ein starkes Normalisierungsergebnis dafür. Obwohl Typen in der Veröffentlichung erwähnt werden, werden sie im Normalisierungsnachweis nicht verwendet. Sie sind nützlich für eine saubere Formulierung der Haupteigenschaft des lichtaffinen Lambda-Kalküls, nämlich dass die Terme eines bestimmten Typs genau die Polytime-Funktionen darstellen. Ähnliche Ergebnisse sind für die Elementarberechnung unter Verwendung anderer "leichter" Lambda-Kalküle bekannt (Teruis Artikel enthält weitere Referenzen).

Als Randnotiz ist es interessant zu beobachten, dass der affine Lambda-Kalkül beweistheoretisch der intuitionistischen Logik ohne die Kontraktionsregel entspricht. Grishin beobachtete (bevor die lineare Logik eingeführt wurde), dass die naive Mengenlehre (dh mit uneingeschränktem Verständnis) ohne Kontraktion konsistent ist (dh Russels Paradoxon gibt keinen Widerspruch). Der Grund dafür ist, dass die Eliminierung von Schnitten für die naive Mengenlehre ohne Kontraktion durch ein einfaches Argument zur Größenverringerung (wie das oben angegebene) bewiesen werden kann, das nicht auf der Komplexität von Formeln beruht. Über die Curry-Howard-Korrespondenz ist dies genau die Normalisierung des untypisierten affinen Lambda-Kalküls. Dies geschieht durch die Übersetzung von Russels Paradoxon in lineare Logik und durch "Optimieren" die exponentiellen Modalitäten, so dass kein Widerspruch abgeleitet werden konnte, dass Girard eine leichte lineare Logik entwickelte. Wie oben erwähnt, liefert die lichtlineare Logik rechnerisch eine Charakterisierung der polynomialzeitberechnbaren Funktionen. In beweistheoretischen Begriffen kann eine konsistente naive Mengenlehre in der lichtlinearen Logik so definiert werden, dass die nachweislich Gesamtfunktionen genau die polynomialzeitberechnbaren Funktionen sind (es gibt eine andere Arbeit von Terui zu diesem Thema: "Lichtaffine Mengenlehre: Eine naive Mengenlehre der Polynomzeit ", Studia Logica 77, 2004).

Damiano Mazza
quelle
Ich würde sagen, dass Teruis Light Affine Lambda Calculus aufgrund der Einschränkungen bei der Verwendung affiner Variablen, der Schichtung von Let-Operatoren und der Monoidalität des! -Operators typisiert ist. Es ist nur so, dass diese Einschränkungen informell eingeführt werden. Girards LLL ist ebenfalls getippt.
Martin Berger
@ Martin: Ich bin anderer Meinung. Die strukturellen Einschränkungen, die den lichtaffinen Begriffen auferlegt werden, sind anderer Natur als die eines Typisierungssystems. Der größte Unterschied besteht darin, dass die Typisierung notwendigerweise induktiv ist, während die Bildung von Bohrlöchern (dh Schichtung, affine Verwendung usw.) als kombinatorische Eigenschaft eines Begriffs definiert werden kann. Wenn Sie beispielsweise einen Begriff eingeben, müssen Sie normalerweise seine Subterme eingeben, während ein Subterm eines geschichteten Begriffs nicht geschichtet werden muss.
Damiano Mazza
Entschuldigung, noch etwas zu Girards LLL: Das System ist offensichtlich typisiert, weil es Formeln enthält. Wie ich in meiner Antwort erwähnt habe, spielen Formeln bei der Eliminierung von LLL-Schnitten überhaupt keine Rolle. Tatsächlich können beliebige Fixpunkte von Formeln hinzugefügt werden (einschließlich Russels paradoxer Formel, die seiner eigenen Negation entspricht!), Ohne dass die LLL inkonsistent wird. Dies liegt daran, dass die Cut-Elimination aus "rein strukturellen" Gründen gilt, unabhängig davon, dass Sie Ihren Proofs Typen hinzufügen können (technisch kann der Cut-Elimination-Satz für LLL in untypisierten Proof-Netzen bewiesen werden).
Damiano Mazza
OK, wenn Sie Induktivität zu einer Bedingung dafür machen, dass etwas ein Schreibsystem ist. Das ist ein interessanter Standpunkt, auf den ich vorher noch nicht gestoßen war.
Martin Berger
... und es ist ein Standpunkt, den ich als falsch bezeichnen würde. Zum Beispiel ist es in Systemen mit Subtypisierung (allgemeiner, wenn eine extrinsische Interpretation von Typen im Sinne von Reynolds betrachtet wird) sehr natürlich, eine koinduktive Sichtweise der Typisierung zu vertreten. Es gibt einige Beispiele in der Literatur (obwohl ich denke, dass dies unterschätzt wird).
Noam Zeilberger
12

Das Originalpapier von Church und Rosser, "Some Properties of Conversion", beschreibt etwas, das ein Beispiel dafür sein könnte, wonach Sie suchen.

λx.MxM

BAmABm

Obwohl Sie nicht terminierende Begriffe in den (untypisierten) strengen Lambda-Kalkül schreiben können, normalisiert sich jeder Begriff mit einer normalen Form stark. Das heißt, jede Folge von Reduktionen erreicht diese einzigartige Normalform.

Rob Simmons
quelle
1
m
Diesmal die Theoremaussage beendet, danke. Der Teil, den ich als [Modulo-Alpha-Äquivalenz] geschrieben habe, war ursprünglich "(innerhalb der Anwendungen von Regel I)", was dasselbe bedeutet, es sei denn, ich erinnere mich nicht richtig an Regel I.
Rob Simmons
10

Hier ist eine lustige von Neil Jones und Nina Bohr:

λ

λλ

Der Vorteil des Schreibens liegt natürlich sowohl in den geringen Komplexitätskosten als auch in der Modularität des Ansatzes: Im Allgemeinen sind Terminierungsanalysen sehr nicht modular, aber das Schreiben kann "Stück für Stück" erfolgen.

Cody
quelle
Das ist wirklich interessant!
MaiaVictor