Существует ли типизированное лямбда-исчисление, в котором соответствующая логика в соответствии с соответствием Карри-Ховарда непротиворечива, и где для каждой вычислимой функции существуют лямбда-выражения с типизацией?
Это, по общему признанию, неточный вопрос, в котором отсутствует точное определение «типизированного лямбда-исчисления». Мне в основном интересно, есть ли (а) известные примеры этого или (б) известные доказательства невозможности чего-либо в этой области.
Редактировать: @cody дает точную версию этого вопроса в своем ответе ниже: существует ли логическая система чистого типа (LPTS), которая является последовательной и завершенной по Тьюрингу (в определенном ниже смысле)?
type-theory
lambda-calculus
typed-lambda-calculus
curry-howard
Морган Томас
источник
источник
Ответы:
Хорошо, я расскажу об этом: в общем, для системы данного типа верно следующее:T
Доказательство, как правило, основывается на предположении, что у вас есть термин типа F a l s e , с использованием приведения субъекта для получения нормальной формы, а затем на основе индукции по структуре такого термина для получения противоречия.absurd False
Естественно задаться вопросом, верно ли обратное, т.е.
Проблема с этим заключается в том, что нет реального наиболее общего понятия «системы типов» и еще меньше согласия относительно значения логической согласованности для таких систем. Тем не менее, мы можем эмпирически проверить, что
Как это связано с полнотой Тьюринга? Ну, например, если проверка типов разрешима , то аргумент Андрея показывает, что должно выполняться одно из следующего :
Это говорит о том, что:
Чтобы дать реальную теорему, а не предложение, необходимо сделать математически точным понятие систем типов и логических интерпретаций.
Теперь на ум приходят два замечания:
Существует неразрешимая система типов, система типов пересечений, которая имеет логическую интерпретацию и может представлять каждую нормализующую терму. Как вы заметили, это не совсем то же самое, что завершить по Тьюрингу, поскольку может потребоваться обновить (на самом деле) тип функции total перед применением ее к желаемому аргументу. Исчисление является исчислением "стиля карри" и равно STLC + Γ ⊢ M : τλ
и
Γ⊢M:τ∩σ
Существует класс систем типов, Системы Чистых Типов , в которых такой вопрос может быть уточнен. Однако в этом контексте логическая интерпретация менее ясна. Может возникнуть соблазн сказать: «PTS непротиворечив, если он имеет необитаемый тип». Но это не работает, поскольку типы могут жить в разных «вселенных», где некоторые могут быть последовательными, а некоторые нет. Кокванд и Гербелин определяют понятие логических систем чистого типа , в которых вопрос имеет смысл, и показывают
Который отвечает на вопрос в одном направлении (не соответствует TC) в этом случае. Насколько я знаю, вопрос для общего LPTS остается открытым и довольно сложным.⇒
Изменить: Обратный результат Кокванд-Гербелин не так просто, как я думал! Вот что я придумала до сих пор.
Логический Чистая Тип системы является ВТС с (по крайней мере) сорта и Т у р е , (по крайней мере) аксиомой Р г о р : Т у р е и (по крайней мере) правило ( Р г o p , P r o p , P r o p ) , с дополнительным требованием, чтобы не было видов P p o p .Prop Type Prop:Type (Prop,Prop,Prop) Prop
Теперь я собираюсь принять конкретное утверждение о полноте Тьюринга: исправить LPTS и пусть Г будет контекстомL Γ
являетсяполной по Тьюрингутогда и только тогда, когда для любой итоговой вычислимой функции f : N → N существует такой термин t f , что Γ ⊢ t f : n a t → n a t и для любого n ∈ N t f ( S n 0 ) → ∗ β S f ( n ) 0L f:N→N tf
Теперь аргумент диагонализации Андрея показывает, что существуют не заканчивающиеся типа n a t .t nat
Теперь кажется, что мы на полпути! Учитывая не заканчивающийся термин , мы хотим заменить вхождения n a t на некоторый универсальный тип A и избавиться от 0 и S в Γ , и у нас будет наше несоответствие ( A обитаемо в контексте A : P r o p )!Γ⊢loop:nat nat A 0 S Γ A A:Prop
К сожалению, это то, где я застреваю, поскольку легко заменить на тождество, но от 0 гораздо сложнее избавиться. В идеале мы хотели бы использовать некоторую теорему Клини о рекурсии, но я еще не понял этого.S 0
источник
Вот ответ на вариант уточнения @ cody моего вопроса. Существует непротиворечивая LPTS, которая является полной по Тьюрингу в грубом смысле @ cody, если мы разрешаем введение дополнительных аксиом и правил редукции. Таким образом, строго говоря, система не является LPTS; это просто нечто очень похожее на одно.β
Рассмотрим исчисление конструкций (или ваш любимый член куба). Это LPTS, но мы собираемся добавить дополнительный материал, который делает его не LPTS. Выберите постоянные символы nat , 0 , S и добавьте аксиомы:λ nat,0,S
⊢ 0 : nat ⊢ S : nat → nat
Индексируйте программы машины Тьюринга по натуральным числам, и для каждого натурального числа выберите постоянный символ f e , добавьте аксиому f e : nat → nat , и для всех e , x ∈ N добавьте правило β- сокращенияe fe fe:nat→nat e,x∈N β
где , как обычно является выходом е й машины Тьюринга программы по х . Если Φ e ( x ) расходится, то это правило ничего не делает. Обратите внимание, что при добавлении этих аксиом и правил теоремы системы остаются рекурсивно перечислимыми, хотя ее набор правил β- редуцирования больше не разрешим, а просто рекурсивно перечислим. Я считаю, что мы могли бы легко разрешить множество правил β- редуцирования, четко указав детали модели вычислений в синтаксисе и правилах системы.Φe(x) e x Φe(x) β β
Теперь эта теория явно завершена по Тьюрингу в грубом смысле Коди, просто грубой силой; но утверждают, что это также соответствует. Давайте построим модель этого.
источник