15
$\begingroup$

The type of call/cc (which may be realized with the 𝜆𝜇-calculus) corresponds with Peirce's Law, which implies LEM. This answer by Pierre-Marie Pédrot explains how Markov's principle can be realized by the Dialectica interpretation or statically-bound exceptions.

What other axioms have a computational interpretation?

$\endgroup$
4
  • 1
    $\begingroup$ The univalence axiom is probably the most famous one. It does have a computational interpretation. $\endgroup$
    – Trebor
    Mar 8 at 4:48
  • $\begingroup$ @Trebor Good point! I get the impression it has some "difficulties" too, since from what Andras Kovacs has told me, it sounds like the rules for cubical glue types are extremely hard to understand and CTT is super complicated in general. $\endgroup$ Mar 8 at 5:13
  • 2
    $\begingroup$ @JamesMartin Recently I have found the newer ABCFHL explanation of glue computation to be much easier to understand than the original CCHM version. Now I don't think that CTTs are excessively complicated. Pedagogy and streamlined explanations matter. $\endgroup$ Mar 8 at 8:51
  • $\begingroup$ I edited out the part about "difficulties" because it may make the question too broad. $\endgroup$ Mar 9 at 19:43

2 Answers 2

14
$\begingroup$

This is a very broad question. Actually, it is even a whole research area, which is a major theme of what I would call the French school of type theory. Extending the Curry-Howard isomorphism from "proof are programs" to "side-effects implement axioms" is a core principle of this community, see e.g. the works of Krivine or Herbelin.

Below is a pot-pourri of the additional logical expressivity provided by side-effects. As usual, there are two ways to understand an effect, either in direct style, i.e. as new terms and reductions added to the language, or in indirect style, i.e. as a program translation. Note that a single axiom may have various implementations that do not behave the same computationally.

  • A monotonous read-only global cell (i.e. the direct syle corresponding to presheaves) gives rise to a whole lot of axioms, depending on the underlying type of the cell. They are used to implement modalities, typically. This is the computational interpretation of intuitionistic forcing, so you can use it e.g. to negate CH.

  • Dynamic exceptions implement Markov's rule. This is literally the computational content of the Friedman's A-translation.

  • Delimited continuations can prove Double Negation Shift.

  • Threads with message passing can be also used to implement classical logic. I don't have a reference for this one, but morally to prove A ∨ ¬A you fork, in the first process you go left and wait on the shared channel, while in the second process you go right and return a function that sends its argument on the channel and dies.

  • When mixing presheaves with a CPS, you get Cohen's classical forcing. The resulting effect looks like a monotonous state.

  • As already mentioned in OP's question, Markov's principle can be realized via the Dialectica transformation. Fun fact, the computational content of the Dialectica transformation is essentially differentiable programming.

I might add more examples if they come to my mind.

$\endgroup$
1
  • 2
    $\begingroup$ Browerian continuity and compactness principles, formal Church's thesis, various forms of the axiom of choice. And then there's also Ulrich Kohlenbach's use of Dialectica-style translations to extract computational content from classical proofs in analysis. As you said, it's a research area. $\endgroup$ Mar 10 at 7:46
2
$\begingroup$

It's not really axioms themselves that are nonconstructive it's the combination of axioms which cause issues with constructive interpretations.

LEM collapses a Cartesian closed category (even distributive categories) to be nonconstructive.

If you have a substructural logic (so a closed monoidal category) or more radically cointuitionistic logic (like Set^op) you can have constructive interpretations for versions of the law of excluded middle.

You can kind of think of the situation as being like exceptions or continuations can let you "observe the evaluation order of the interpreter." So you can either weaken identities (substructural logic) or ban some constructs out right.

It's not really quite an issue of there being a constructive interpretation or not. It's more an issue of there being constructive interpretations satisfying all the logical identities we want.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.