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:
    April 7, 2013 at 6:14 pm

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

  2. Edward Z. Yang says:
    April 7, 2013 at 6:26 pm

    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:
    April 7, 2013 at 6:38 pm

    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. Edward Z. Yang says:
    April 7, 2013 at 6:50 pm

    “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:
    April 7, 2013 at 6:54 pm

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

  6. Edward Z. Yang says:
    April 7, 2013 at 7:03 pm

    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:
    April 7, 2013 at 7:40 pm

    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:
    April 7, 2013 at 11:25 pm

    > 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:
    April 7, 2013 at 11:39 pm

    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:
    April 7, 2013 at 11:41 pm

    Oh, now I see what SonOfLilit did. Clever.

  11. Danno says:
    April 8, 2013 at 12:17 am

    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:
    April 8, 2013 at 1:52 am

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

  13. Tom E says:
    April 8, 2013 at 4:00 am

    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:
    April 8, 2013 at 10:13 am

    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:
    April 8, 2013 at 12:54 pm

    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:
    April 8, 2013 at 2:11 pm

    (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:
    April 8, 2013 at 4:40 pm

    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:
    April 9, 2013 at 6:33 am

    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:
    April 10, 2013 at 6:46 pm

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

  20. Anonymous Coward says:
    April 11, 2013 at 10:45 am

    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:
    April 15, 2013 at 2:09 pm

    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:
    June 22, 2013 at 5:10 pm

    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