Os tipos recursivos irrestritos do MALL + são completos com Turing?

Se você observar os combinadores recursivos no cálculo lambda sem tipo, como o combinador Y ou o combinador ômega: É claro que todos esses combinadores acabam duplicando uma variável em algum lugar de sua definição.

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

Além disso, todos esses combinadores são tipificáveis no cálculo lambda de tipo simples, se você o estender com tipos recursivos , onde é permitido ocorrer negativamente no tipo recursivo. $\mu\alpha.\,A(\alpha)$ $\alpha$

No entanto, o que acontece se você adicionar tipos recursivos completos (ocorrência negativa) ao fragmento livre de exponencial da lógica linear (ou seja, MALL)?

Então você não tem um exponencial para lhe dar contração. Você pode codificar o tipo de exponencial usando algo como $!A$ mas não vejo como definir a regra de introdução para ela, pois isso parece exigir um combinador de ponto fixo para definir. E eu estava tentando definir exponenciais, obter contração, obter um combinador de ponto fixo!

! A ≜ μ α . I & A & (α \otimes α)

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

É o caso de o MALL e os tipos recursivos irrestritos ainda estarem normalizando‽

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

Eu estava pensando nisso outro dia, e passei algumas horas brincando com algumas idéias, mas não consegui encontrar uma maneira de expressar um valor recursivo nem me convencer de que não era possível. Minha intuição é que não é! Eu não considerei a outra direção - se você assumir a regra de introdução para! e tipos recursivos, isso permite definir um combinador de ponto fixo?

CA McCann

λ

$\lambda$

A & B

$A & B$

Se as comutações aditivas forem omitidas no MALL, é fácil mostrar que o tamanho de uma prova diminui a cada etapa de eliminação de corte. Se as comutações aditivas forem permitidas, a prova não é tão fácil, mas foi fornecida no artigo “Linear Logic” original. É chamado de Teorema da Normalização Pequena (Corolário 4.22, p71), que diz que enquanto a regra de contração-promoção não estiver envolvida (como é o caso do MALL), a normalização será mantida. O argumento não se baseia nas fórmulas, elas podem ser infinitas (por exemplo, definidas recursivamente).

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

$\mu$ $!A$

Stéphane Gimenez
fonte

Observe também que o tipo sugerido é mencionado brevemente na página 101 (última página) do artigo.

Stéphane Gimenez

Os tipos recursivos irrestritos do MALL + são completos com Turing?

Respostas: