Was ist die Intuition hinter linearer Logik?

Ich versuche, lineare Logik zu verstehen, um lineare Typsysteme besser zu verstehen. Wenn ich jedoch die Regeln lese, bekomme ich keine Intuition dahinter, wie ich es in der Modallogik getan habe - $\Box A$ bedeutet, dass $A$ erforderlich ist, wie in Kripke-Frames. $A$ ist für jede erreichbare Welt erforderlich. [ $\Diamond A$ ist $A$ ist mutatis möglich mutandis]. Aber ich kann keine intuitive Erklärung für die Dualität finden und welches der Konjunktions- / Disjunktionspaare (falls vorhanden) $\land$ und $\lor$ .

lo.logic type-theory linear-logic Maciej Piechotka
quelle

In Girards Originalpapier sollten Sie nachsehen, ob Sie die Intuition dahinter verstehen möchten. Die Frage ist imo zu allgemein und die Antwort wäre, auf der Wikipedia-Seite nach linearer Logik zu suchen.

Kaveh

Ich bin damit einverstanden, dass dies ein bisschen zu Brot und definitiv kein Forschungsniveau ist. Vielleicht sollten Sie die Frage zu CS Stack Exchange stellen. Ich möchte Sie jedoch davon abhalten, Girards Originalpapier als Einstiegspunkt in die lineare Logik zu verwenden. Vielleicht ist die Wikipedia ein besserer Ausgangspunkt.

Damiano Mazza

Das ist ziemlich breit. Ein Vorschlag könnte vielleicht darin bestehen, Formeln als eine "Währung" zu betrachten, die anstelle von Wahrheitserklärungen ausgegeben werden kann. Dann könnte die Konjunktion

a \otimes b

$a \otimes b$ was bedeutet, dass wir sowohl eine

a

$a$ Münze als auch eine

b

$b$ Münze ausgeben können . Eine andere Art der Konjunktion könnte

a & b

$a \& b$ , was bedeutet, dass wir zwischen

a

$a$ und

wählen können

b

$b$ (aber nicht beides!). Sie können einige Beispiele auf Wikipedia finden, wie Damiano vorgeschlagen hat.

Chi

@chi Ich bin mir nicht sicher, ob die "Ressourceninterpretation" der beste Weg ist, die Dualität in LL zu verstehen. Die Prozessinterpretation ist viel verständlicher.

Martin Berger

Antworten:

Ich bin mir nicht sicher, ob diese Frage ideal für CSTheory ist, aber da sie bereits positive Stimmen sammelt, ist hier eine Antwort, die jemand gegeben hätte, wenn die Frage auf cs.stackexchange veröffentlicht worden wäre .

$(\cdot)^{\bot}$ $A$

$A \otimes B$ $A$ $B$ $A \otimes B$ $(a, b)$ $a$ $A$ $b$ $B$

$(.)^{\bot}$ $A \otimes B$

(A \otimes B)^{⊥} = A^{⊥} ⅋ B^{⊥}

$(A \otimes B)^{\bot} \quad = \quad A^{\bot} ⅋ B^{\bot}$

In dieser Lesart ist der Prozess, der mit kommuniziert . $A^{\bot} ⅋ B^{\bot}$ $A \otimes B$

Das Äquivalent der Disjunktion der linearen Logik kann ähnlich prozess-theoretisch gelesen werden. Die Formel

A & B

$A\ \&\ B$

sollten auch als zwei Prozesse und parallel gesehen werden, aber anstatt aktiv Nachrichten zu senden, warten sie darauf, dass die Umgebung entscheidet, welche ausgeführt werden sollen. Also sitzt dort und wartet auf seinem Kanal auf eine Information, die entscheidet, ob als oder als . Dies ist eine 'parallele' Version des in sequentiellen Programmiersprachen. Das Duale von ist $A$ $B$ $A \& B$ $A \& B$ $A$ $B$ $if/then/else$ $(A \& B)^{\bot}$ $A \& B$

(A & B)^{⊥} = A^{⊥} \oplus B^{⊥}

$(A \& B)^{\bot} \quad = \quad A^{\bot} \oplus B^{\bot}$

kann als ein Prozess angesehen werden, der 1 Bit an sendet , nämlich: "Weiter als " oder "Weiter als ". Dies ist ähnlich wie bei der Bewertung von nach während Bewertung nach , mit der Ausnahme, dass die Wahl zwischen und jetzt von der Umgebung getroffen wird. $A \& B$ $A$ $B$ $if\ true\ then\ P\ else\ Q$ $P$ $if\ false\ then\ P\ else\ Q$ $Q$ $A$ $B$

Der! -Operator hat auch eine prozess-theoretische Interpretation: Wenn als Prozess gelesen wird, kann so gelesen werden, dass unendlich viele Prozesse parallel ausgeführt werden.

A

$A$

! A

$!A$

A

$A$

In dieser Lesart werden die Axiome der linearen Logik zu einfachen 'Drähten', die Nachrichten von den Prozessen an die Prozesse weiterleiten . Diese Interpretation der Axiome findet sich bereits in Girards Beweisnetzen (3). $A \vdash A$ $A^{\bot}$ $A$

Diese prozess-theoretische Interpretation war einflussreich und führte zu vielen Folgearbeiten wie z. B. (2) für Sitzungstypen. Trotzdem gibt es einige Randfälle, die es etwas umständlich machen, und meines Wissens wurde es auch 2017 nicht perfekt für die vollständige lineare Logik gemacht.

_{1. S. Abramsky, Computerinterpretationen der linearen Logik .

2. P. Wadler, Vorschläge als Sitzungen .

3. Wikipedia, Beweisnetz .}

Martin Berger
quelle