Тип проживания - Type inhabitation

В теория типов, филиал математическая логика, в данном типизированном исчислении тип обитания проблема для этого исчисления возникает следующая проблема:^[1] учитывая тип ${\displaystyle \tau }$ и среда ввода ${\displaystyle \Gamma }$, существует ли ${\displaystyle \lambda }$-терм M такой, что ${\displaystyle \Gamma \vdash M:\tau }$? В среде пустого типа такой M называется обитателем ${\displaystyle \tau }$.

Отношение к логике

В случае просто типизированное лямбда-исчисление, у типа есть житель тогда и только тогда, когда его соответствующий предложение - это тавтология минимальной импликативной логики. Аналогично Система F у типа есть житель тогда и только тогда, когда его соответствующий предложение - это тавтология логика второго порядка.

Парадокс Жирара показывает, что заселение типов сильно связано с согласованностью системы типов с соответствием Карри – Ховарда. Чтобы быть здоровой, такая система должна иметь необитаемые типы.

Формальные свойства

Для большинства типизированных исчислений проблема типа обитания очень жесткий. Ричард Статман доказал, что для просто типизированное лямбда-исчисление проблема типа обитания PSPACE-полный. Для других расчетов, например Система F, проблема даже в неразрешимый.

Смотрите также

• Изоморфизм Карри – Ховарда

Рекомендации

1. Павел Уржичин (1997). «Обитание в типизированных лямбда-исчислениях (синтаксический подход)». Конспект лекций по информатике. Springer: 373–389.