Является ли MALL + неограниченные рекурсивные типы Turing-complete?

Если вы посмотрите на рекурсивные комбинаторы в нетипизированном лямбда-исчислении, такие как Y-комбинатор или омега-комбинатор: Понятно, что все эти комбинаторы в конечном итоге дублируют переменную где-то в своем определении.

\begin{array}{lcl} ω & знак равно & (λ Икс, Икс Икс) (λ Икс, Икс Икс) \\ Y & знак равно & λ е, (λ Икс, е (Икс Икс)) (λ Икс, е (Икс Икс)) \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}$

Кроме того, все эти комбинаторы можно вводить в простейшем лямбда-исчислении, если расширить его рекурсивными типами , где допускается отрицательно в рекурсивном типе. $\mu\alpha.\,A(\alpha)$ $\alpha$

Однако что произойдет, если вы добавите полные (с отрицательным вхождением) рекурсивные типы к фрагменту линейной логики без экспоненты (т. Е. MALL)?

$!A$

! A ≜ μ α, я & A & (α \otimes α)

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

Это тот случай, когда MALL плюс неограниченные рекурсивные типы все еще нормализуются?

lo.logic pl.programming-languages linear-logic Нил Кришнасвами
источник

Я думал об этом только на днях и провел несколько часов, играя с некоторыми идеями, но не мог ни найти способ выразить рекурсивную ценность, ни убедить себя, что это невозможно. Моя интуиция такова, что это не так! Я не рассматривал другое направление, хотя - если вы принимаете правило введения для! и рекурсивные типы, это позволяет вам определить комбинатор с фиксированной точкой?

CA McCann

Я всегда думал, что

термин, в котором каждая переменная встречается не более одного раза, можно вводить в простой типизированный фрагмент. Это показывает, что вы не можете определить комбинатор с фиксированной точкой, в котором переменные используются линейно.

λ

$\lambda$

Андрей Бауэр

Я думаю , что вы только что ответили на вопрос для МП, но добавки

делают позволяют переменным дублироваться (линейность , то подразумевает единичные вхождения в последовательности сокращения, грубо говоря).

A & B

$A & B$

Нил Кришнасвами

Ответы:

Если аддитивные коммутации опущены в MALL, легко показать, что размер доказательства уменьшается с каждым шагом исключения среза. Если допускаются аддитивные коммутации, доказательство не так просто, но оно было предоставлено в оригинальной статье «Линейная логика». Она называется теоремой малой нормализации (следствие 4.22, стр. 71), в которой говорится, что до тех пор, пока не применяется правило сокращения-продвижения (как в случае МОЛЛ), имеет место нормализация. Аргумент не опирается на сами формулы, они могут быть бесконечными (например, рекурсивно определенными).

Это означает, что невозможно закодировать промо для типа в MALL, поскольку это позволило бы использовать комбинаторы с фиксированной точкой. Для этого понадобится дополнительная конструкция рекурсии. $\mu\alpha.\;I \;\&\; A \;\&\; (\alpha \otimes \alpha)$

Примечание: я полагаю, что можно использовать MALL вместе с принципом коиндукции (введение двойного ), чтобы нормализовать систему и получить повышение по этой кодировке . Разрешение рекурсивных типов в MALL + Coinduction сделает завершение Тьюринга. Но до тех пор, пока MALL рассматривается один, использование рекурсивных типов не имеет большого значения. $\mu$ $!A$

Стефан Хименес
источник

Также обратите внимание, что предлагаемый тип кратко упоминается на странице 101 (последняя страница) документа.

Стефан Гименес