Dlaczego konstruktywiści nie dbają zbytnio o call / cc

Jakiś czas temu po raz pierwszy ktoś mi powiedział, że call / cc może zezwalać na obiekty proof dla klasycznych proofów poprzez wdrożenie prawa Peirce'a. Ostatnio zastanawiałem się nad tym tematem i wydaje mi się, że nie mogę go znaleźć. Jednak naprawdę nie widzę, żeby ktokolwiek mówił o tym. Wydaje się być pozbawiony dyskusji. Co daje?

Wydaje mi się, że jeśli masz konstrukcję typu w pewnym kontekście, to jedna z dwóch rzeczy jest prawdą. Albo masz dostęp do instancji ⊥ jakoś w bieżącym kontekście, w którym przepływ sterowania sprawa nigdy nie osiągnie tutaj i jesteśmy bezpiecznie założyć cokolwiek LUB zważywszy, że f : ¬ ( ¬ P ) środki f : ( P → ⊥ ) → ⊥ jedynym sposobem, w jaki f może zwrócić ⊥, jest zbudowanie instancji $f : \neg(\neg P)$$\bot$$f : \neg(\neg P)$$f : (P \to \bot) \to \bot$$f$$\bot$$P$i zastosowanie go dwa to argument (instancja . W takim przypadku istniał już NIEKTÓRY sposób skonstruowania instancji P ; rozsądne wydaje się, aby call / cc wyciągnęło dla mnie tę konstrukcję. Moje rozumowanie tutaj wydaje mi się nieco podejrzane, ale moje zamieszanie nadal istnieje. Jeśli call / cc nie tworzy tylko instancji P z powietrza (nie wiem, jak to jest), to na czym polega problem?$P \to \bot)$$P$$P$

Czy niektóre dobrze wpisane terminy nie zawierające call / cc nie mają normalnych formularzy? Czy istnieje jakaś inna właściwość takich wyrażeń, która powoduje, że są podejrzani? Czy jest jakiś znany powód, dla którego konstruktywista nie powinien lubić call / cc?

Matematyka konstruktywna to nie tylko system formalny, ale raczej zrozumienie tego, na czym polega matematyka. Innymi słowy, nie każda semantyka jest akceptowana przez konstruktywnego matematyka.

Dla konstruktywnego matematyka call/ccwygląda jak oszustwo. Zastanów się, w jaki sposób jesteśmy świadkami używając :$p \lor \lnot p$call/cc

1. Zapewniamy funkcję która rzekomo potwierdza ¬ p . W rzeczywistości f to worek sztuczek.$f$$\lnot p$$f$
2. Jeśli ktokolwiek kiedykolwiek zastosuje do dowodu p , f zwolni się, aby cofnąć czas, i mając dowód p w ręce, zmieni zdanie na temat p ∨ ¬ p : tym razem twierdząc, że jest to dowód p .$f$$p$$f$call/cc$p$$p \lor \lnot p$$p$

Konstruktywne rozumienie rozłączności jest rozstrzygalnością algorytmiczną , ale powyższe prawie nie podejmuje żadnych decyzji. Jako test konstruktywny matematyk może zapytać cię, w jaki sposób call/ccpomaga udowodnić, że każda maszyna Turinga zatrzymuje się lub rozbiega. A jaki program świadczy o tym fakcie? (To powinna być Wyrocznia Zatrzymująca.)

Jak zauważasz, istnieje możliwa konstruktywna interpretacja klasycznej logiki w tym sensie. Fakt, że logika klasyczna jest spójna z logiką intuicyjną (powiedzmy, arytmetyką Heytinga) jest znany już od pewnego czasu (już w 1933 r., Np. Godel ), stosując tłumaczenie podwójnej negacji.

Bardziej wyrafinowanym argumentem można wykazać, że arytmetyka Peano jest konserwatywna w stosunku do HA dla instrukcji . Istotą wyniku jest to, że klasyczne dowody Π 0 2 obejmujące c a l l / c c mają taką samą treść obliczeniową jak instrukcja bez tego konstruktu (przez transformację CPS ).$\Pi^0_2$$\Pi^0_2$$\mathrm{call/cc}$

Jednak nie jest to prawdą w przypadku oświadczeń powyżej : oświadczenia w Σ 0 3 , możliwe do udowodnienia w PA, mogą nie mieć normalnej formy podatnej na wyciągnięcie świadka! Informatycy mogą nie przejmować się obliczeniami z dowodami na tym poziomie, ale jest to nieco niewygodne ze względów filozoficznych : czy udowodniliśmy istnienie czegoś, czy nie?$\Pi^0_2$$\Sigma^0_3$

Myślę, że to podsumowuje, dlaczego „naprawianie” niekonstruktywnej logiki przez dodanie może być niezadowalające.$\mathrm{call/cc}$

To powiedziawszy, wiele pracy poświęcono obliczeniowym aspektom obliczeń w ramach „klasycznego modelu Curry-Howarda”, np. Krivine Machine, rachunek Parigota ( ) i wielu innych. Zobacz tutaj na przegląd.$\lambda\overline{\mu}\tilde\mu$

Na koniec warto zauważyć, że chociaż sytuacja jest raczej dobrze rozumiana w rachunku predykatu i przypadkach arytmetycznych, o tyle silniejsze teorie są znacznie mniej badane. Na przykład IIRC, ZFC jest konserwatywny w stosunku do IZF również dla zdań (ZFC jest konserwatywny w stosunku do ZF dla zdań arytmetycznych, a ZF jest konserwatywny w stosunku do IZF), co sugeruje, że istnieje obliczeniowe znaczenie aksjomatu wyboru. Jest to jednak bardzo aktywny obszar badań ( krivine , Berardi i in. )$\Pi^0_2$

Edycja: Tutaj pojawia się bardzo istotne pytanie dotyczące przepływu matematyki: /mathpro/29577/solved-sequent-calculus-as-programming-language

Zgadzam się z odpowiedzią Andreja i Cody'ego. Myślę jednak, że warto również wspomnieć, dlaczego konstruktywiści powinni dbać o operatory kontroli (call / cc).

$\neg\neg P\vdash P$

$\Pi^0_2$

Kolejną korzyścią, na którą powinien dbać konstruktywista, jest to, że operatorzy kontroli pokazują sposób, w jaki sposób zbudować rozszerzenie Curry-Howarda intuicyjnej logiki, które jest nadal konstruktywne. Na przykład ograniczenie z prawa eliminacji podwójnej negacji do $P$$\Sigma^0_1$