¿Cuál es la intuición detrás de la lógica lineal?

Estoy tratando de entender la lógica lineal para comprender mejor los sistemas de tipo lineal. Sin embargo, cuando leí las reglas, no llego a tener una intuición detrás de él como lo he hecho en la lógica modal - significa se requiere como en los marcos de Kripke es necesaria para todos los mundos accesibles [ es es posible , mutatis mutandis]. Pero no puedo encontrar ninguna explicación intuitiva para la dualidad y cuál de los pares de conjunción / disyunción (si corresponde) corresponde a y . $\Box A$ $A$ $A$ $\Diamond A$ $A$ $\land$ $\lor$

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

El documento original de Girard es donde debe mirar si quiere comprender la intuición detrás de ellos. La pregunta como es es demasiado general y la respuesta sería mirar la página de Wikipedia para la lógica lineal.

Kaveh

Estoy de acuerdo en que esto es un poco demasiado pan y definitivamente no es un nivel de investigación, tal vez debería hacer la pregunta en CS Stack Exchange. Sin embargo, le desanimaría de usar el artículo original de Girard como punto de entrada a la lógica lineal. Quizás la Wikipedia sea un mejor lugar para comenzar.

Damiano Mazza

Esto es bastante amplio. Una sugerencia, tal vez, podría comenzar a considerar las fórmulas como una "moneda" que se puede gastar, en lugar de declaraciones de verdad. Entonces, la conjunción podría ser

lo que significa que podemos gastar tanto

moneda a como una moneda

. Otro tipo de conjunción podría ser

, lo que significa que podemos elegir entre gastar

y gastar

(¡pero no ambos!). Puedes encontrar algunos ejemplos en Wikipedia, como sugirió Damiano.

a \otimes b

$a \otimes b$

a

$a$

b

$b$

a & b

$a \& b$

a

$a$

b

$b$

chi

@chi No estoy seguro de que la "interpretación de recursos" sea la mejor manera de entender la dualidad en LL. La interpretación del proceso es mucho más comprensible.

Martin Berger

Respuestas:

No estoy seguro de que esta pregunta sea ideal para CSTheory, pero dado que ya está reuniendo votos a favor, aquí hay una respuesta que alguien podría haber dado si la pregunta se hubiera publicado en cs.stackexchange .

$(\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}$

En esta lectura es el proceso que se comunica con . $A^{\bot} ⅋ B^{\bot}$ $A \otimes B$

El equivalente de la disyunción de la lógica lineal puede recibir una lectura teórica de proceso similar. La formula

A & B

$A\ \&\ B$

También debe verse como dos procesos y en paralelo, pero en lugar de enviar mensajes activamente, esperan que el entorno decida qué ejecutar. Así que se sienta allí, esperando en su canal para un bit de información que decide si debe funcionar como o como . Esta es una versión 'paralela' del en lenguajes secuenciales de programación. El dual de es $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}$

puede verse como un proceso que envía 1 bit de información a , a saber: "continuar como " o "continuar como ". Esto es similar a evaluando a mientras evaluando a , excepto que la elección entre y ahora es hecha por el entorno. $A \& B$ $A$ $B$ $if\ true\ then\ P\ else\ Q$ $P$ $if\ false\ then\ P\ else\ Q$ $Q$ $A$ $B$

El operador! También tiene una interpretación teórica del proceso: si se lee como un proceso, entonces se puede leer como ejecutando infinitos procesos en paralelo.

A

$A$

! A

$!A$

A

$A$

En esta lectura el axiomas de la lógica convertido en simples 'cables' lineales que reenviar mensajes de procesos a procesos . Esta interpretación de los axiomas ya está en las redes de prueba de Girard (3). $A \vdash A$ $A^{\bot}$ $A$

Esta interpretación teórica del proceso ha sido influyente y ha dado lugar a una gran cantidad de trabajo de seguimiento como, por ejemplo, (2) para los tipos de sesión. Sin embargo, hay algunos casos extremos que lo hacen un poco incómodo, y que yo sepa, no se ha hecho que funcione perfectamente para una lógica lineal completa incluso en 2017.

_{1. S. Abramsky, Interpretaciones computacionales de la lógica lineal .

2. P. Wadler, Propuestas como sesiones .

3. Wikipedia, Prueba de red .}

Martin Berger
fuente