Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Define the axiom constants $p_{A,B}^{((A\rightarrow B)\rightarrow A)\rightarrow A}$ as realizers of the Peirce formula, and $f_A^{\bot\rightarrow A}$ as realizers of the Ex Falso Quodlibet. Then $p_{A\vee\lnot A,\bot}^{(\lnot (A\vee\lnot A)\rightarrow(A\vee\lnot A))\rightarrow(A\vee\lnot A)}\lambda_{u^{\lnot(A\vee\lnot A)}} . f_{A\vee\lnot A}^{\bot\rightarrow (A\vee\lnot A)} u (\vee_+^{\lnot A\rightarrow A\vee\lnot A} \lambda_{v^A}.u(\vee_+^{A\rightarrow A\vee\lnot A} v))$ proves the law of the excluded middle $A\vee\lnot A$.

Now, the function call-with-current-continuation, or short call/cc, in scheme, has the signature of $p$ (in Haskell, this one is replaced by its negative translation). The rest of the above term is covered by the Curry Howard Isomorphism, and therefore, using an instance of call/cc as a realizer of $p$ gives a program of type $A\vee\lnot A$.

Of course, something that one expects in programs extracted from constructive proofs must fail here, otherwise one could decide every proposition $A$. I was just wondering, what exactly it is.

Scheme's call/cc will fail with this term, since the continuation is called twice - but that is not really a problem, since one could just copy the whole context of the continuation and bind it into a new function which can then be called multiple times - that would produce a lot of overhead, but still would provide an effective algorithm which must not exist.

And having a call/cc in the beginning of a term does also not seem very useful, but inside another term, this should not be a problem.

Then, maybe in this context we must not use $f$. Normally, instances $f$ of the Ex Falso Quodlibet must never be called, and in this term, it could be called (and would give an instance of $A\vee\lnot A$) - but on the other hand, the continuation is called twice before ever coming to call $f$, so I am not sure whether this is actually the problem.

And then of course, $u$ is called twice, once with an instance of $A\vee\lnot A$ that eliminates to $A$, and once with an instance that eliminates to $\lnot A$. So probably calling $u$ with both outcomes of $A\vee\lnot A$ may produce endless loops or strange behaviour.

As I said, I am not sure what exactly fails here. Does anybody know?

share|improve this question
1  
My I recommend Frank Pfenning's notes cs.cmu.edu/~fp/courses/15317-f09/lectures/…? –  Andrej Bauer Jan 16 '11 at 23:50

1 Answer 1

up vote 5 down vote accepted

I'm not sure what you mean by 'fail' here.

It is true, as you say, that classical proofs can exhibit behaviour that constructive proofs can't. In general, it's no longer true that a term of type A reduces to a constructive proof of the proposition A -- but that's only to be expected. Proof-terms in classical logic are strongly normalizing, though (if you're sensible about it), so there are no 'endless loops'. The difference is that, in general, such proof-terms can have more than one distinct normal form, and there is no good reason to pick one over any other.

You say

Scheme's call/cc will fail with this term, since the continuation is called twice

which is not true. Scheme continuations can be called any number of times. Also

Normally, instances f of the Ex Falso Quodlibet must never be called

is not true either. The ex falso sequitur quodlibet term discards the current continuation and returns its argument to the top level.

In terms of behaviour, functional programs use their continuations exactly once. Allowing EFSQ means that a program can discard, but not copy, its continuation. Admitting the double-negation rule duplex negatio affirmat allows programs to use their continuations an arbitrary number of times, including zero (or not, for Peirce's law). This corresponds to allowing exactly one, at most one and arbitrarily many formulas on the right-hand side of the turnstile in sequent calculus.

What the excluded-middle term does is this: it pretends to be a proof of not-A until such time as it is presented with a proof of A, whereupon it travels back in time (so to speak) and returns that proof of A instead (Wadler has a paper about this, I think). In general, classical proofs behave more like systems of communicating processes than functional programs. There are a couple of papers by Barbanera and Berardi that go into this in detail.

share|improve this answer
    
Thank you for your answer. So far I was only concerned with program extraction from intuitionistic proofs. Wadler = Philip Wadler? If so, there are a lot of papers of him, could you get more specific? For Franco(?) Barbanera I do not really find much that seems to be related. And there are a lot of people called Berardi, do you have a prename? –  Christoph-Simon Senjak Jan 16 '11 at 19:08
    
That's Philip Wadler, Call-by-value is dual to call-by-name and Franco Barbanera & Stefano Berardi (look here: informatik.uni-trier.de/~ley/db/indices/a-tree/b/…). Or have a look at my TCD technical report (not peer-reviewed) here: cs.tcd.ie/publications/tech-reports/reports.08/… –  Finn Lawler Jan 16 '11 at 19:31
1  
I think it's the other way around: to implement LEM, initially take the negative disjunct and pretend to be a proof of not-A, that is, a function taking as paramter a proof of A and returning a proof of contradiction. If the function is invoked with an actual proof of A as an argument, instead of returning a contradiction (which is impossible) go "back in time" and take the positive disjunct, returning the given proof of A... –  Daniel Mehkeri Jan 17 '11 at 5:44
    
Yes, you're quite right. Fixed. –  Finn Lawler Jan 17 '11 at 14:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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