Проверка, является ли произвольное доказательство круговым?

13

Я думал о доказательствах и столкнулся с интересным наблюдением. Таким образом, доказательства эквивалентны программам через изоморфизм Карри-Говарда, а круговые доказательства соответствуют бесконечной рекурсии. Но из проблемы остановки мы знаем, что в общем случае проверка того, будет ли произвольная программа повторяться вечно, неразрешима. По Карри-Говарду, означает ли это, что не существует «средства проверки доказательств», которое могло бы определить, использует ли доказательство круговые рассуждения?

Я всегда думал, что доказательства должны состоять из легко проверяемых шагов (которые соответствуют приложениям правил вывода), и проверка всех шагов дает вам уверенность в том, что вывод следует. Но теперь я задаюсь вопросом: может быть, на самом деле невозможно написать такую ​​проверочную проверку, потому что у нее нет способа обойти проблему остановки и обнаружить круговые рассуждения?

logic curry-howard hewasonlyacat
источник

Ответы:

15

Подавляющее большинство систем доказательств не допускают бесконечных круговых доказательств, но они делают это, делая свои языки нетуринговыми полными.

Y∀a,(a→a)→a

aaa

Ключевым моментом здесь является то, что Y-комбинатор встроен в язык, он воспринимается как аксиома. Поэтому, если вы хотите, чтобы это не доставляло вам проблем, просто избавьтесь от этого как аксиомы!

Из-за этого большинство формальных систем доказательства требуют, чтобы ваша рекурсия была обоснованной. Они принимают только те функции, которые могут доказать, что они остановятся. И в результате они отвергают некоторые программы, которые действительно останавливаются, но не могут доказать это.

Coq делает это довольно ограниченным способом: он просто требует, чтобы у любых рекурсивных функций был аргумент, где любые рекурсивные вызовы используют только строго меньшие версии этого аргумента. Агда делает нечто похожее, но с немного более сложной проверкой, чтобы принять еще несколько программ.

jmite
источник
1
Исключает ли Coq некоторые законные теоремы, которые вы могли бы доказать в противном случае? Или всегда есть обходные пути, когда средство проверки целостности слишком консервативно? (Я предполагаю, что ответ для других помощников по доказательству, основанных на теории зависимых типов, одинаков?)
Плита
1
@boyers FWIW, в Coq можно использовать Functionили Program Fixpointконструкции, чтобы доказать, что некоторая функция является тотальной, если проверка целостности завершается неудачно. Простой пример является функция слияния сортировки по спискам. Нужно доказать вручную, что мы разбиваем списки (длиной> 1) на строго меньшие подсписки.
Антон Трунов
@boyers Да, должны быть вещи, которые вы не можете доказать в Coq по первой теореме Геделя. На практике с ними редко можно столкнуться, но всегда есть диагональный аргумент: Coq не может доказать сам Coq, он может доказать только подмножество (очень большое подмножество, включая все функции, но с более низким пределом рекурсии). это может справиться). Я помню, что читал, что теория Кока эквивалентна аксиомам Пеано плюс существование определенного большого порядкового номера (и поэтому доказательства, предполагающие, что еще больший порядковый номер не может соответствовать), но я не могу найти ссылку сейчас.
Жиль "ТАК - перестать быть злым"
@AntonTrunov В этом контексте Programи тому подобное - красная сельдь. Они не меняют теорию. Они используют синтаксический сахар для использования меры в доказательстве: вместо того, чтобы рассуждать о том, что интересующий вас объект становится меньше, вы добавляете уровень косвенности: вычисляете, что другой объект становится меньше (например, некоторый размер) и докажите, что он становится меньше. Смотрите Wfбиблиотеку.
Жиль "ТАК - перестань быть злым"
@ Жиль Я предположил, что контекст был о практической (конкретной) стороне, например, когда эвристика Кока провалилась ... Не могли бы вы попытаться найти упомянутую вами статью? Ссылка будет высоко ценится.
Антон Трунов