Pourquoi les constructivistes ne semblent pas trop se soucier de call / cc

Donc, il y a quelque temps, quelqu'un m'a d'abord dit que call / cc pouvait autoriser des objets de preuve pour des preuves classiques en implémentant la loi de Peirce. J'ai réfléchi au sujet récemment et je n'arrive pas à trouver un défaut. Cependant, je n'arrive pas vraiment à voir quelqu'un d'autre en parler. Il semble vide de discussion. Ce qui donne?

Il me semble que si vous avez une construction comme dans un certain contexte, alors 1 des deux choses est vraie. Soit vous avez accès à une instance ⊥ d'une manière ou d' une autre dans le contexte actuel, auquel cas le flux de contrôle n'atteindrait jamais ici et nous pouvons supposer quoi que ce soit OU étant donné que f : ¬ ( ¬ P ) signifie f : ( P → ⊥ ) → ⊥ le la seule façon dont f peut retourner ⊥ est de construire une instance de $f : \neg(\neg P)$$\bot$$f : \neg(\neg P)$$f : (P \to \bot) \to \bot$$f$$\bot$$P$et en l'appliquant à deux c'est l'argument (une instance de . Dans un tel cas, il y avait déjà QUELQUE façon de construire une instance de P ; il semble raisonnable que call / cc retire cette construction pour moi. Mon raisonnement ici me semble quelque peu suspect, mais ma confusion persiste. Si call / cc ne crée pas simplement une instance de P à partir de rien (je ne vois pas comment c'est), alors quel est le problème?$P \to \bot)$$P$$P$

Certains termes bien dactylographiés ne contenant pas call / cc n'ont-ils pas des formes normales? Existe-t-il une autre propriété de telles expressions qui les rend suspectes? Y a-t-il une raison notée pour laquelle un constructiviste ne devrait pas aimer call / cc?

Les mathématiques constructives ne sont pas seulement un système formel, mais plutôt une compréhension de la nature des mathématiques. Ou pour le dire différemment, tous les types de sémantique ne sont pas acceptés par un mathématicien constructif.

Pour un mathématicien constructif, cela call/ccressemble à de la triche. Considérez comment nous voyons utiliser :$p \lor \lnot p$call/cc

1. Nous fournissons une fonction qui prouve prétendument ¬ p . En réalité, f est un sac d'astuces.$f$$\lnot p$$f$
2. Si quelqu'un applique jamais à une preuve de p , alors f déchaîne pour faire reculer le temps, et avec une preuve de p en main, change d'avis sur p ∨ ¬ p : cette fois en prétendant que c'est une preuve de p .$f$$p$$f$call/cc$p$$p \lor \lnot p$$p$

La compréhension constructive de la disjonction est la décidabilité algorithmique , mais ce qui précède ne prend guère de décisions. À titre de test, un mathématicien constructif pourrait vous demander comment call/ccaider à prouver que chaque machine Turing s'arrête ou diverge. Et quel est le programme témoin de ce fait? (Ce devrait être l'Oracle Halting.)

Comme vous le constatez, il existe une possible interprétation constructive de la logique classique dans ce sens. Le fait que la logique classique soit équitablement cohérente avec la logique intuitionniste (disons, Heyting Arithmetic) est connu depuis un certain temps (déjà en 1933, par exemple Godel ) utilisant une traduction à double négation.

Par un argument plus sophistiqué, on peut montrer que Peano Arithmetic est conservateur sur HA pour les instructions . L'essence du résultat est que les preuves classiques de Π 0 2 impliquant c a l l / c c ont le même contenu de calcul qu'une déclaration sans cette construction (par une transformation CPS ).$\Pi^0_2$$\Pi^0_2$$\mathrm{call/cc}$

Cependant, cela n'est pas vrai pour les déclarations au-dessus de : les déclarations en Σ 0 3 , prouvables en PA, peuvent ne pas avoir une forme normale susceptible d'extraire un témoin! Les informaticiens peuvent ne pas se soucier de l'informatique avec des preuves à ce niveau, mais c'est quelque peu gênant pour des considérations philosophiques : avons-nous prouvé l'existence de quelque chose, ou non?$\Pi^0_2$$\Sigma^0_3$

Je pense que cela résume pourquoi «fixer» la logique non constructive par l'addition de peut être insatisfaisant.$\mathrm{call/cc}$

Cela étant dit, il y a beaucoup de travail explorant les aspects computationnels du calcul dans le cadre "classique de Curry-Howard", par exemple la machine Krivine, le calcul de Parigot ( ) et bien d'autres. Voir ici pour un aperçu.$\lambda\overline{\mu}\tilde\mu$

Enfin, il pourrait être utile de noter que si la situation est plutôt bien comprise dans le calcul des prédicats et les cas arithmétiques, des théories plus puissantes sont beaucoup moins explorées. Par exemple, IIRC, ZFC est conservateur sur IZF pour phrases et (ZFC est conservatrice sur ZF pour les phrases arithmétiques et ZF est conservateur sur IZF), ce qui suggère qu'il existe un sens de calcul pour l'axiome du choix. Cependant, c'est un domaine de recherche très actif ( krivine , Berardi et al. )$\Pi^0_2$

Edit: Une question très pertinente sur mathoverflow apparaît ici: /mathpro/29577/solved-sequent-calculus-as-programming-language

Je suis d'accord avec la réponse d'Andrej et de Cody. Cependant, je pense qu'il convient également de mentionner pourquoi les constructivistes devraient se soucier des opérateurs de contrôle (call / cc).

$\neg\neg P\vdash P$

$\Pi^0_2$

$P$$\Sigma^0_1$