Когда (или должен) Теоретический CS заботится о интуиционистских доказательствах?

Из того, что я понимаю (что очень мало, поэтому, пожалуйста, поправьте меня, где я ошибаюсь!), Теория языков программирования часто связана с "интуиционистскими" доказательствами. В моей собственной интерпретации, подход требует, чтобы мы серьезно относились к последствиям вычислений для логики и доказуемости. Доказательство не может существовать, если не существует алгоритма, строящего последствия из гипотез. Например, мы можем отвергнуть в качестве аксиомы принцип исключенной середины, поскольку он демонстрирует некоторый объект, который является или ¬ X , неконструктивно.$X$$\lnot X$

Вышеприведенная философия может привести нас к тому, что мы предпочитаем интуитивно обоснованные доказательства тем, которые не являются таковыми. Тем не менее, я не видел какой-либо озабоченности по поводу фактического использования интуиционистской логики в работах в других областях теоретической CS. Мы, кажется, счастливы доказать наши результаты, используя классическую логику. Например, можно представить себе использование принципа исключенного среднего для доказательства правильности алгоритма. Другими словами, мы заботимся и серьезно относимся к вычислительно ограниченной вселенной в наших результатах, но не обязательно в наших доказательствах этих результатов.

1. Заинтересованы ли когда-нибудь исследователи теоретической CS в написании интуитивно обоснованных доказательств? Я мог бы легко представить себе область теоретической информатики, которая стремится понять, когда результаты TCS, особенно алгоритмические, сохраняются в интуиционистской логике (или, что более интересно, когда они этого не делают). Но я еще не сталкивался ни с одним.

2. Есть ли философский аргумент, который они должны? Кажется, можно утверждать, что результаты информатики должны быть доказаны интуитивно, когда это возможно, и мы должны знать, какие результаты требуют, например, PEM. Кто-нибудь пытался привести такой аргумент? Или, возможно, существует консенсус, что этот вопрос просто не очень важен?

3. В качестве дополнительного вопроса мне любопытно знать примеры случаев, когда это действительно имеет значение: известны ли важные результаты TCS в классической логике, но не в интуиционистской логике? Или подозреваемый не придерживается интуиционистской логики.

Извиняюсь за мягкость вопроса! Это может потребовать переписывания или реинтерпретации после заслушивания экспертов.

Как я сказал в комментариях, интуиционистская логика не главное. Более важным моментом является наличие конструктивного доказательства. Я думаю, что теория типов Мартина-Лёфа гораздо более актуальна для теории языка программирования, чем интуиционистская логика, и есть эксперты, которые утверждают, что работа Мартина-Лёфа является главной причиной возрождения общего интереса к конструктивной математике.

Вычислительная интерпретация конструктивности является одной из возможных перспектив, но она не единственная. Мы должны быть осторожны здесь, когда мы хотим сравнить конструктивные доказательства с классическими доказательствами. Хотя оба могут использовать одни и те же символы, их значения различны.

Всегда полезно помнить, что классические доказательства можно перевести на интуиционистские доказательства. Другими словами, в некотором смысле классическая логика является подсистемой интуиционистской логики. Поэтому вы можете реализовать (скажем, с помощью вычислимых функций) классические доказательства в некотором смысле. С другой стороны, мы можем думать о конструктивной математике как о некоторой математической системе в классическом сеттинге.

В конце концов, формализмы, будь то классические или конструктивные, являются инструментами для выражения заявлений. Взять классическую теорему и попытаться доказать ее конструктивно без этой перспективы не имеет большого смысла ИМХО. Когда я говорю классически Я имею в виду нечто отличное от того, что я говорю A ∨ B конструктивно. Вы можете утверждать, что «должно» быть истинным значением « ∨ », но я думаю, что это не интересно, если мы не обсуждаем то, что мы хотим выразить в первую очередь. Имеем ли мы в виду (по крайней мере) одно из них, и мы знаем, какое? Или мы просто имеем в виду одну из них?$A \lor B$$A \lor B$$\lor$

$\forall x \ \exists y \ \varphi(x,y)$$x$$y$$\varphi(x,y)$$y$$y$$x$$A$$x$$\varphi(x,A(x))$$A$ - некоторый явно заданный алгоритм. Если неясно, почему кто-то может предпочесть конструктивный способ выразить это, подумайте о языках программирования как об аналогии: вы можете написать программу для алгоритма MST Kruskal на языке ассемблера x86, где вам придется позаботиться о множестве побочных проблем или вы Можно написать программу на Python.

Теперь, почему мы не используем интуиционистскую логику на практике? Есть несколько причин. Например, большинство из нас не обучены таким настройкам. Также найти классическое доказательство утверждения может быть намного проще, чем найти конструктивное доказательство этого. Или мы могли бы заботиться о низкоуровневых деталях, которые скрыты и недоступны в конструктивном контексте (см. Также линейную логику ). Или мы могли бы просто не быть заинтересованы в получении дополнительных материалов, которые идут с конструктивным доказательством. И хотя существуют инструменты для извлечения программ из доказательств, эти инструменты, как правило, нуждаются в очень подробных доказательствах и недостаточно удобны для общего теоретика. Короче говоря, слишком много боли, слишком мало пользы.

$\Pi^0_2$$PA$$PA$$PA$

Я помню, что Дуглас С. Бриджес во введении к своей книге по теории вычислимости утверждал, что мы должны доказать наши результаты конструктивно. Он приводит пример, который IIRC, по сути, выглядит следующим образом:

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

В конце мы должны помнить, что, хотя мы используем одни и те же символы для классической и интуиционистской логики, эти символы имеют разные значения, и то, что мы используем, зависит от того, что мы хотим выразить.

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

• Существуют ли неконструктивные доказательства существования алгоритма?

Стоит задуматься о том, ПОЧЕМУ интуиционистская логика является естественной логикой для вычислений, поскольку слишком часто люди теряются в технических деталях и не могут понять суть проблемы.

Проще говоря, классическая логика - это логика совершенной информации: предполагается, что все утверждения в системе известны или известны как однозначно истинные или ложные.

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

Помимо этого, оказывается, что даже в сильно нормализующих средах, где всегда гарантируется завершение, классическая логика все еще проблематична, поскольку устранение двойного отрицания $\neg\neg P \implies P$ в конечном счете, сводится к возможности извлечь значение «из воздуха», а не вычислять его напрямую.

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

Реальные криптографические хеш-функции, такие как MD5 и SHA, не имеют ключей. Таким образом, это довольно затрудняет применение методов теоретической криптографии для обоснования их безопасности. Причина проста: для любой хеш-функции без ключа существует очень маленькая программа / злоумышленник, которая выводит коллизию под этой хеш-функцией; а именно, программа, которая имеет такое столкновение - которая должна существовать! - жестко закодировано.

В статье Фила Рогавая « Формализация человеческого невежества: хеширование без ключей», посвященной столкновениям, рассматривается эта проблема. В нем он показывает, что некоторые очень стандартные теоремы для ключевых хеш-функций (такие как конструкция Меркля-Дамгарда и парадигма hash-then-sign) могут быть адаптированы и повторно доказаны с помощью «интуитивно понятных» утверждений теорем, применяемых к хеш-функциям без ключей.

Вот хорошая глава об интуиционистской логике из обширной онлайн-книги « Логика для информатики» , 300 стр. [1] с 9,5, p210, сводка по p220:

Интуиционистская логика возникла в результате конструктивистского движения в математике, которое отвергло неконструктивные доказательства существования или те, которые основаны на законе исключенной середины. Недавно связь между интуиционистской математикой и программированием стала результатом наблюдения, что суждения и типы (в смысле программирования) эквивалентны. Разработка алгоритма в этой формальной системе, которая основана на естественном выводе, состоит из написания спецификации в логической записи и затем, рассматривая это как тип, доказывая, что он не пуст. Поскольку основная логика является конструктивным доказательством, если оно может быть выполнено,

Другая близкая перспектива исходит от писателя TCSist Андрея Бауэра на тему «Математика и вычисления; математика для компьютеров» [2], который предлагает в основном, что «интуиционистская математика полезна для физики». презентация в основном с точки зрения физики, но для тех, кто рассматривает CS в тесной связи с физикой, идеология, как правило, относится к TCS.

Вычислительная интерпретация. Это интерпретация интуиционистской логики, обычно представляемая в информатике. Мы рассматриваем все наборы как представленные подходящими структурами данных - разумная точка зрения для ученого. Тогда утверждение считается истинным, если существует программа (вычислительные данные), свидетельствующая о ее истинности.

[1] Логика для информатики, Ривз и Кларк

[2] Интуиционистская математика для физики Бауэра