¿Por qué los constructivistas no parecen preocuparse demasiado por call / cc

Entonces, hace un tiempo, primero tuve a alguien que me dijo que call / cc podría permitir objetos de prueba para pruebas clásicas mediante la implementación de la ley de Peirce. Pensé un poco sobre el tema recientemente y parece que no puedo encontrar un defecto con él. Sin embargo, realmente no puedo ver a nadie más hablando de eso. Parece vacío de discusión. ¿Lo que da?

Me parece que si tienes una construcción como en algún contexto, entonces 1 de dos cosas es cierta. O tiene acceso a una instancia ⊥ de alguna manera en el contexto actual, en cuyo caso el flujo de control nunca llegaría aquí y estamos seguros de asumir lo que sea O dado que f : ¬ ( ¬ P ) significa f : ( P → ⊥ ) → ⊥ el la única forma en que f puede devolver ⊥ es construyendo una instancia de $f : \neg(\neg P)$$\bot$$f : \neg(\neg P)$$f : (P \to \bot) \to \bot$$f$$\bot$$P$y aplicándolo dos es argumento (una instancia de . En tal caso, ya había ALGUNA forma de construir una instancia de P ; me parece razonable que call / cc pueda sacar esta construcción por mí. Mi razonamiento aquí me parece algo sospechoso, pero mi confusión sigue en pie. Si call / cc no solo está creando una instancia de P de la nada (no veo cómo es), ¿cuál es el problema?$P \to \bot)$$P$$P$

¿Algunos términos bien escritos que no contienen call / cc no tienen formas normales? ¿Hay alguna otra propiedad de tales expresiones que las haga sospechosas? ¿Hay alguna razón notoria por la que a un constructivista no le guste call / cc?

La matemática constructiva no es solo un sistema formal sino más bien una comprensión de lo que se trata la matemática. O para decirlo de otra manera, no todo tipo de semántica es aceptado por un matemático constructivo.

Para un matemático constructivo call/ccparece una trampa. Considere cómo presenciamos usando :$p \lor \lnot p$call/cc

1. Proporcionamos una función que supuestamente prueba ¬ p . En realidad, f es una bolsa de trucos.$f$$\lnot p$$f$
2. Si alguien aplica a una prueba de p , entonces f se desata para retroceder en el tiempo, y con una prueba de p en la mano, cambia de opinión sobre p ∨ ¬ p : esta vez afirma que es una prueba de p .$f$$p$$f$call/cc$p$$p \lor \lnot p$$p$

La comprensión constructiva de la disyunción es la capacidad de decisión algorítmica , pero lo anterior apenas toma decisiones. Como prueba, un matemático constructivo podría preguntarle cómo call/ccayuda a demostrar que cada máquina de Turing se detiene o diverge. ¿Y cuál es el programa testigo de este hecho? (Debería ser el Oráculo detenido).

Como se observa, existe una posible interpretación constructiva de la lógica clásica en este sentido. El hecho de que la lógica clásica es equiconsistente con la lógica intuicionista (por ejemplo, Heyting Arithmetic) se conoce desde hace bastante tiempo (ya en 1933, por ejemplo, Godel ) utilizando una traducción de doble negación.

Mediante un argumento más sofisticado, se puede demostrar que la aritmética de Peano es conservadora sobre HA para declaraciones . La esencia del resultado es que las pruebas clásicas de Π 0 2 que involucran c a l l / c c tienen el mismo contenido computacional que una declaración sin esa construcción (por una transformación CPS ).$\Pi^0_2$$\Pi^0_2$$\mathrm{call/cc}$

Sin embargo, esto no es cierto para las declaraciones anteriores : las declaraciones en Σ 0 3 , demostrables en PA, ¡pueden no tener una forma normal que permita extraer un testigo! Los informáticos pueden no preocuparse por la informática con pruebas a este nivel, pero es algo inconveniente por consideraciones filosóficas : ¿hemos demostrado la existencia de algo o no?$\Pi^0_2$$\Sigma^0_3$

Creo que esto resume por qué "arreglar" la lógica no constructiva mediante la adición de puede ser insatisfactorio.$\mathrm{call/cc}$

Dicho esto, hay mucho trabajo explorando los aspectos computacionales de la computación dentro del marco "clásico de Curry-Howard", por ejemplo, la máquina Krivine, el cálculo Parigot ( ) y muchos otros. Consulte aquí para obtener una descripción general.$\lambda\overline{\mu}\tilde\mu$

Finalmente, podría ser útil notar que si bien la situación se entiende bastante bien en el cálculo de predicados y los casos aritméticos, las teorías más poderosas son mucho menos exploradas. Por ejemplo, IIRC, ZFC es conservador sobre IZF para frases también (ZFC es conservador más de ZF para frases aritméticas, y ZF es conservador sobre IZF), que sugiere que hay un significado computacional para el axioma de elección. Sin embargo, este es un campo de investigación muy activo ( Krivine , Berardi et al. )$\Pi^0_2$

Editar: una pregunta muy relevante sobre mathoverflow aparece aquí: /mathpro/29577/solved-sequent-calculus-as-programming-language

Estoy de acuerdo con la respuesta de Andrej y Cody. Sin embargo, creo que también vale la pena mencionar por qué los constructivistas deberían preocuparse por los operadores de control (call / cc).

$\neg\neg P\vdash P$

$\Pi^0_2$

$P$$\Sigma^0_1$