Sind MALL + uneingeschränkte rekursive Typen vollständig?

Wenn Sie sich die rekursiven Kombinatoren im untypisierten Lambda-Kalkül ansehen, wie den Y-Kombinator oder den Omega-Kombinator: Es ist klar, dass all diese Kombinatoren eine Variable irgendwo in ihrer Definition duplizieren.

\begin{array}{lcl} ω & = & (λ x . x x) (λ x . x x) \\ Y. & = & λ f . (λ x . f (x x)) (λ x . f (x x)) \end{array}

$\begin{array}{lcl} \omega & = & (\lambda x.\,x\;x)\;(\lambda x.\,x\;x)\\ Y & = & \lambda f.\,(\lambda x.\,f\;(x\;x))\; (\lambda x.\,f\;(x\;x)) \\ \end{array}$

Darüber hinaus sind alle diese Kombinatoren im einfach typisierten Lambda-Kalkül typisierbar, wenn Sie ihn mit den rekursiven Typen , wobei im rekursiven Typ negativ vorkommen darf. $\mu\alpha.\,A(\alpha)$ $\alpha$

Was passiert jedoch, wenn Sie dem exponentialfreien Fragment der linearen Logik (dh MALL) vollständige (negativ auftretende) rekursive Typen hinzufügen?

Dann haben Sie kein Exponential , um sich zusammenzuziehen. Sie können die Art der Exponentiale mit etwas wie aber ich verstehe nicht, wie ich die Einführungsregel dafür definieren soll, da dies einen Festkomma-Kombinator zu erfordern scheint. Und ich habe versucht, Exponentiale zu definieren, Kontraktion zu bekommen, einen Fixpunkt-Kombinator zu bekommen! $!A$

! EIN ≜ μ α . ich & EIN & (α \otimes α)

$!A \triangleq \mu\alpha.\;I \;\&\; A \;\&\; (\alpha \otimes \alpha)$

Ist es so, dass sich MALL plus uneingeschränkte rekursive Typen immer noch normalisieren?

lo.logic pl.programming-languages linear-logic Neel Krishnaswami
quelle

Ich habe erst neulich darüber nachgedacht und ein paar Stunden lang mit ein paar Ideen gespielt, aber weder einen Weg gefunden, um einen rekursiven Wert auszudrücken, noch mich davon zu überzeugen, dass es nicht möglich war. Meine Intuition ist, dass es nicht ist! Die andere Richtung habe ich allerdings nicht bedacht - wenn Sie die Einführungsregel für annehmen! und rekursive Typen, können Sie damit einen Festkomma-Kombinator definieren?

CA McCann

Ich habe immer gedacht, dass ein -Term, in dem jede Variable höchstens einmal vorkommt, in dem einfach typisierten Fragment typisierbar ist. Das würde also zeigen, dass Sie keinen Fixpunktkombinator definieren können, in dem Variablen linear verwendet werden.

λ

$\lambda$

Andrej Bauer

Ich glaube , Sie haben gerade die Frage MLL beantwortet, aber die Additive zu tun erlauben Variablen dupliziert wird (Linearität dann einzelne Vorkommen in Reduktion Sequenzen impliziert, grob).

A & B

$A & B$

Neel Krishnaswami

Wenn additive Kommutierungen in MALL weggelassen werden, ist es einfach zu zeigen, dass die Größe eines Proofs mit jedem Schnitteliminierungsschritt abnimmt. Wenn additive Kommutierungen zulässig sind, ist der Beweis nicht so einfach, er wurde jedoch im Originalpapier „Lineare Logik“ bereitgestellt. Es heißt Small Normalization Theorem (Korollar 4.22, S. 71), das besagt, dass die Normalisierung gilt, solange die Kontraktionsförderungsregel nicht involviert ist (was in MALL der Fall ist). Das Argument beruht nicht auf Formeln selbst, sie können unendlich sein (z. B. rekursiv definiert).

Dies bedeutet, dass es nicht möglich ist, eine Promotion für den Typ in MALL, da dies Fixpunktkombinatoren erlauben würde. Dazu wäre ein zusätzliches Rekursionskonstrukt erforderlich. $\mu\alpha.\;I \;\&\; A \;\&\; (\alpha \otimes \alpha)$

Hinweis: Ich glaube, dass es möglich ist, MALL zusammen mit einem Coinduktionsprinzip (Einführung von 's dual) zu verwenden, um das System zu normalisieren und eine Promotion für diese Codierung von . Das Zulassen rekursiver Typen in der MALL + -Koinduktion würde Turing dann vervollständigen. Solange MALL allein betrachtet wird, ist es jedoch keine große Sache, rekursive Typen zuzulassen. $\mu$ $!A$

Stéphane Gimenez
quelle

Beachten Sie auch, dass der vorgeschlagene Typ auf Seite 101 (letzte Seite) des Papiers kurz erwähnt wird.

Stéphane Gimenez

Sind MALL + uneingeschränkte rekursive Typen vollständig?

Antworten: