Почему конструктивисты не слишком заботятся о call / cc

15

Итак, некоторое время назад я сначала попросил кого-то сказать мне, что call / cc может разрешить объекты доказательства для классических доказательств путем реализации закона Пирса. Недавно я немного подумал над этой темой и не могу найти в ней недостаток. Однако я не могу видеть, чтобы кто-то еще говорил об этом. Это кажется пустым обсуждением. Что дает?

Мне кажется, что если в каком-то контексте у вас есть конструкция типа то 1 из двух вещей верен. Либо у Вас есть доступ к экземпляру как - то в текущем контексте , в котором управление потоком случае никогда бы не достичь здесь , и мы с уверенностью предположить , что бы ни ИЛИ , учитывая , что е : ¬ ( ¬ P ) означает F : ( P ) Единственный способ, которым f может вернуть - это создать экземпляр Pе:¬(¬п)е:¬(¬п)е:(п)епи применяя два аргумента (пример . В таком случае уже был какой-то способ построения экземпляра P ; кажется разумным для call / cc вытащить эту конструкцию для меня. Мои рассуждения здесь кажутся мне несколько подозрительными, но мое замешательство сохраняется. Если call / cc не просто создает экземпляр P из воздуха (я не понимаю, как это), то в чем проблема?п)пп

У некоторых хорошо типизированных терминов, не содержащих call / cc, нет нормальных форм? Есть ли какое-либо другое свойство таких выражений, которое вызывает у них подозрение? Есть ли причина, по которой конструктивисту не нравится call / cc?

Джейк
источник

Ответы:

19

Конструктивная математика - это не просто формальная система, а понимание того, что такое математика. Иными словами, не каждый вид семантики принимается конструктивным математиком.

Для конструктивного математика call/ccвыглядит как измена. Рассмотрим, как мы видим используя :п¬пcall/cc

  1. Мы предлагаем функцию , которая якобы доказывает ¬ р . На самом деле е это мешок с хитростями.е¬пе
  2. Если кто-либо когда-либо применяет к доказательству p , то f запускает время отката и, имея в руках доказательство p , меняет свое мнение о p ¬ p : на этот раз утверждая, что это доказательство p .епеcall/ccпп¬пп

Конструктивное понимание дизъюнкции - это алгоритмическая разрешимость , но вышесказанное вряд ли принимает какие-либо решения. В качестве теста конструктивный математик может спросить вас, как call/ccпомогает доказать, что каждая машина Тьюринга останавливается или расходится. И какая программа свидетельствует об этом? (Это должен быть Остановочный Оракул.)

Андрей Бауэр
источник
Ах !! Я думаю, что это то, что я искал.
Джейк
9

Как вы заметили, в этом смысле возможна конструктивная интерпретация классической логики. Тот факт, что классическая логика эквивалентна интуиционистской логике (скажем, арифметике Хейтинга), был известен довольно давно (уже в 1933 году, например, Годель ) с использованием перевода с двойным отрицанием.

К более сложному аргументу, можно показать , что арифметика Пеано является консервативной над HA для заявления. Суть результата состоит в том, что классические доказательства Π 0 2 с использованием c a l l / c c имеют то же вычислительное содержание, что и утверждение без этой конструкции (с помощью преобразования CPS ).Π20Π20сaLL/сс

Однако это не верно для операторов выше : заявления в Й 0 3 , доказуемы в PA, не могут иметь нормальную форму поддающегося извлечению свидетеля! Компьютерные ученые могут не заботиться о вычислениях с доказательствами на этом уровне, но это несколько неудобно для философских соображений: доказали ли мы что-то существование или нет?Π20Σ30

Я считаю , что это подводит итог , почему «фиксация» неконструктивные логик добавления может быть неудовлетворительными.сaLL/сс

Тем не менее, существует много работы, посвященной вычислительным аспектам вычислений в рамках "классической структуры Карри-Ховарда", например, машина Кривина, исчисление Париго ( ) и многие другие. Смотрите здесь для обзора.λμ¯μ~

Π20

Изменить: очень актуальный вопрос о mathoverflow появляется здесь: /mathpro/29577/solved-fter-calculus-as-programming-language

Коди
источник
1
Является ли это равенство истинным конструктивно?
Джеффри Ирвинг
3
¬¬
Что подразумевается под «может не иметь нормальной формы, поддающейся извлечению свидетеля». Это просто семантически означает, что у этих терминов есть основание для семантики, или это означает что-то более странное?
Джейк
3
@Jake: термины все еще имеют нормальные формы, но, возможно, не те, которые вы ожидаете: например, доказательство A¬Ainr (fun x -> callcc(...))A
Понял. Благодарность! Я все еще перевариваю части вашего ответа. Я не очень знаком с арифметической иерархией, поэтому мне потребовалось немного больше, чтобы обработать.
Джейк
8

Я согласен с ответом Андрея и Коди. Тем не менее, я думаю, что стоит также упомянуть, почему конструктивисты должны заботиться об управляющих операторах (call / cc).

¬¬пп

Π20

Еще одно преимущество, о котором должен заботиться конструктивист, заключается в том, что управляющие операторы показывают способ построения расширения интуиционистской логики Карри-Ховарда, которое все еще конструктивно. Например, ограничение пΣ10

Данко Илик
источник