ezyang’s blog

the arc of software bends towards understanding

A classical logic fairy tale

(Selinger) Here is a fairy tale: The evil king calls the poor shepherd and gives him these orders. “You must bring me the philosophers stone, or you have to find a way to turn the philosopher’s stone to gold. If you don’t, your head will be taken off tomorrow!” What can the poor shepherd do to save his life?

Hat tip to Chris for originally telling me a different variant of this story. Unfortunately, this quote from Lectures on the Curry-Howard Isomorphism was the only reference I could find. What should the shepherd do? Is there something a little odd about this story?

22 Responses to “A classical logic fairy tale”

  1. Ashley Yakeley says:

    I have found a way of turning the philosopher’s stone into gold. But only I can perform it.

  2. Many years pass, and the shepherd believes that he has escaped from the wiles of the evil king. But one day, the king once again calls the shepherd, and tells him, “It has taken many years, but I have finally procured the philosopher’s stone. Now, make good on your promise, and turn this stone into gold.” What should the poor shepherd do now?

  3. tbelaire says:

    One approach:

    “Well, a *real* philosopher’s stone can be identified by the fact that if you tap it three times with a spoon, it turns to gold. If you give me a stone like that I will gladly turn it to gold for you.”

  4. “I see what you’ve tried to do there, with your syntactic sleight of hand, redefining A = (A’ /\ (A’ -> B)). But I am king, and *I* say that this is a philosopher’s stone—if you do not agree, then it is off to the gallows with you!” he says with a sneer.

  5. SonOfLilit says:

    Alright, I will do as you say. *Takes stone*. Here, I bring you the philosopher’s stone.

  6. If you are in the realm of intuitionistic logic, please turn to page 4. If you are in the realm of classical logic, please turn to page 32.

    Page 4: “What do you take me for, a fool?! Off with his head!” The shepherd’s head is chopped off. THE END.

    Page 32: “Well, hm, uh. I suppose I did originally ask you to give me a philosopher’s stone. I suppose that will do.” The shepherd returns home, and the evil king never troubles him again. THE END.

    (SonOfLilit wins!)

  7. Kim-Ee Yeoh says:

    Aha! This old chestnut is like an El Niño over haskell blogs. I love all the variations:

    Luke Palmer in 2007:

    http://lukepalmer.wordpress.com/2007/10/26/computing-without-a-middle/

    Wadler in 2003:

    http://parametricity.net/b/2012/04/24/the-devil-of-the-excluded-middle/

  8. Ashley Yakeley says:

    > What should the poor shepherd do now?

    He should do nothing. The king threatened to take his head on a date which passed years ago. The shepherd is therefore safe from that threat.

    Of course, if the king makes new threats, that’s a new problem.

  9. Yawar says:

    The way I remember it, the philosopher’s stone is used to transmute base metals into gold. It does not itself turn into gold.

  10. Yawar says:

    Oh, now I see what SonOfLilit did. Clever.

  11. Danno says:

    The peasant should sue the King for providing no assurance that his head wouldn’t be taken off even if he satisfied the King’s demands. The King has created a contract in bad faith.

  12. Ivo says:

    There’s a finite chance the stone will spontaneously turn into gold. The method is waiting long enough.

  13. Tom E says:

    The Philosopher’s Stone is supposed to turn lead into gold, so the shepherd could cheaply make a “machine” which takes in a Philosopher’s Stone and outputs gold. That would probably convince the king, but it doesn’t have the same logical moral as the other answer.

  14. Anonymous says:

    The shepherd gives the king a stone of gold, and says this is the philosophers stone and I have found a way to turn it into gold…

  15. Steve M says:

    Claim to have found the secret, then sell his flock and move to the next kingdom along: who wants to live under a deranged tyrant?

  16. illissius says:

    (In case it’s not clear to anyone, SonOfLilit was continuing the story from Edward’s first comment, and, after the king procures the philosopher’s stone and gives to the shepherd to be turned into gold, the shepherd instead chooses the first option, and brings the king the philosopher’s stone. So not just any old stone.)

  17. Howard B. Golden says:

    Danno, sovereigns are immune from lawsuit. In any case, a command is not a contract, because the shepherd’s participation is involuntary. Most likely, the king would kill both the shepherd and, following Dick the butcher’s advice, his lawyers!

  18. Rob Simmons says:

    Was Chris’s story the one about the devil? I think I attribute that version to Wadler’s note “Call-by-Value is Dual to Call-by-Name.” There are a couple of other retellings, of course.

  19. Chris says:

    I made a Twine game about the variant I know: http://www.cs.cmu.edu/~cmartens/if/dem.html

  20. Anonymous Coward says:

    The shepherd brings the King a small gold nugget and tells him “behold, I found the Philosopher stone and turned it to gold”.

  21. Christopher Hendrie says:

    Amusingly, the King’s second demand appears to be a choice between two Cuts — either cut Stone against (Stone –o Gold), or cut Body against Body –o Head. SonOfLit’s classical shepherd creatively escapes via a different, cut-free derivation.

    The intuitionist shepherd is effectively doomed — it’s such a sad tail [sic]. If only he could have boxed himself first, he wouldn’t have found his positioning weakening so abruptly. (In another time and place, tyrants of a different type would have bound him in concrete overshoes, with similar consequents.)

    ( With apologies to logicians, the pun-averse, and the waters so cavalierly muddled )

  22. Anonymous says:

    The shepherd, being poor, brings the king an ingot of lead. “Auspicious king,” he says, “I have found a way of turning the Philosopher’s Stone to gold: I merely had to turn it to lead, robbing it of its power as a Philosopher’s Stone, but making it suitable for transformation into gold by a second Stone.”

Leave a Comment