Тип населенного пункта
-
Определение типа в теории типов
- Проблема определения типа в типизированном математическом анализе: существует ли λ-код M, такой что Γ ⊢ M : τ?
- Обитатель типа: объект M, который является членом типа τ в заданной среде Γ.
-
Связь с логикой
- Тип имеет обитателя, если соответствующее предложение является тавтологией в минимальной импликативной логике.
- Система типа F имеет обитателя, если утверждение является тавтологией интуиционистской логики второго порядка.
- Парадокс Жирара демонстрирует связь между обитаемостью типов и согласованностью системы типов.
- Надежная система типов должна быть необитаемого типа.
-
Формальные свойства
- Проблема определения типа является сложной для большинства типизированных вычислений.
- Ричард Стейтман доказал, что для простого типизированного лямбда-исчисления задача определения типа является PSPACE-полной.
- Для системы F проблема определения типа неразрешима.
-
Рекомендации
- Статья является заглушкой и требует расширения для включения в Википедию.
Полный текст статьи: