Как указано в заголовке, мне интересно какое-либо отношение и различие между CIC и ITT. Может ли кто-нибудь объяснить или указать мне некоторую литературу, которая сравнивает эти две системы? Спасибо.
type-theory
день
источник
источник
Ответы:
Я уже несколько ответил, но постараюсь дать более подробный обзор теоретического горизонта типа, если хотите.
Я немного не в курсе исторической специфики, поэтому более информированные читатели должны простить меня (и исправить меня!). Основная история заключается в том, что Карри обнаружил базовое соответствие между комбинаторами простого типа (или -terms) и логикой высказываний, которая была расширена Говардом, чтобы охватить логику первого порядка, и IIRC, независимо обнаруженный де Брюйном в исследованиях вокруг очень влиятельная система Automath .λ
Система Automath была усовершенствованием простой теории типов Черча, которая сама по себе была резким упрощением теории типов Рассела и Уайтхеда с использованием вселенных и аксиомы сводимости . Это была относительно известная логическая местность к 1960-м годам.
Однако предоставление последовательной, простой, основополагающей системы, охватывающей как системы доказательств, так и терминов, к 1970 году все еще оставалось очень открытым вопросом, и первый ответ дал Пер Мартин-Лёф. Он дает очень философский обзор о значении логических констант и обосновании логических законов . Он полагает, что как в логике, так и в математике значение конструкций можно определить, изучив правила введения, которые позволяют формировать эти конструкции в качестве суждений, например, для соединения
Определяет соответствующее правило исключения. Затем он дал очень мощную основополагающую систему, основанную на таких суждениях, что позволило ему дать основополагающую систему, аналогичную Automath, используя очень мало синтаксических конструкций. Жирар обнаружил, что эта система была противоречивой, побудив Мартина-Лёфа принять предикативные вселенные «в стиле Рассела» , серьезно ограничив выразительность теории (эффективно удаляя аксиому сводимости) и сделав ее несколько более сложной (но обладающей преимуществом: делая это последовательно).
Однако элегантные конструкции, позволяющие определять логические символы, больше не работали, что побудило ML представить их в другой форме в качестве индуктивно определенных семейств . Это очень мощная идея, так как она позволяет определять все, начиная от объективного равенства и логических операторов до натуральных чисел и функциональных типов данных, как они появляются в информатике. Обратите внимание, что каждое добавляемое нами семейство сродни добавлению ряда аксиом, которые должны быть обоснованы как согласованные в каждом случае. Эту систему (зависимые типы + вселенные + индуктивные семейства) обычно называют ITT .
Однако было некоторое длительное разочарование, поскольку мощная, но простая основополагающая система была непоследовательна, и получающаяся в результате система была более сложной и несколько слабой (в том смысле, что в ней было трудно разработать большую часть современной математической основы). Энтер Тьерри Кокванд, который вместе со своим руководителем Жераром Уэтом представил «Конструктивное исчисление» (CoC) , которое в основном решает следующие проблемы: унифицированный подход к доказательствам и типам данных, мощная (непредсказуемая) основополагающая система и способность определять «конструкции» «логического или математического разнообразия. Это в конечном итоге переросло в реальную реализацию системы, разработанной как современная альтернатива Automath, кульминацией которой стала система Coq , которую мы знаем и любим.
Я настоятельно рекомендую эту основополагающую статью о CoC, так как Тьерри знает нелепое количество исторического развития теории типов и, вероятно, объясняет это гораздо лучше, чем я. Возможно, вы также захотите проверить его статью по теории типов, хотя это не так. объяснить переписку СН в деталях.
источник