Реализуемость
-
Определение реализуемости
- Реализуемость — это метод, который позволяет определить, является ли формула доказуемой в интуиционистской логике.
- Формула считается доказуемой, если существует число, которое реализует формулу.
-
Примеры и свойства
- Примеры формул, которые являются доказуемыми, включают дизъюнкцию, импликацию и экзистенциальные формулы.
- Существуют свойства, такие как «принцип Маркова» и «принцип независимости посылок», которые можно доказать с помощью реализуемости.
-
Модификации и приложения
- Крейзель представил модифицированную реализуемость, использующую типизированное лямбда-исчисление.
- Реализуемость используется в proof mining для извлечения программ из математических доказательств.
-
Рекомендации и библиография
- Ссылки на статьи и книги по реализуемости и смежным темам доступны в коллекции ссылок.
Полный текст статьи: