Sunday, October 15, 2006

The Hardest Logic Puzzle Ever

Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for 'yes' and 'no' are 'da' and 'ja' in some order. You do not know which word means which. (Boolos, 1996, p.62) ( illustration of the puzzle)


A Simple Solution to the Hardest Logic Puzzle Ever (with landon)


5 comments:

Richard said...

Could you explain how EQL* works for Random? Here's an apparent counterexample:

Suppose 'ja' means yes. Suppose I ask Random "E(Q)", and his internal coin lands on "liar". Further suppose that if I were to later ask him about Q, then Random would speak truly. Suppose that Q is true. So Random would truthfully say 'ja' if asked about it. So E(Q) is true. So the lying Random will say 'da', even though the correct answer to Q is 'yes'. So EQL* is false.

Perhaps we could correct this with a more careful embedded question, say:

E*(Q) = "If this very question I'm asking had been 'Q', would your answer have been 'ja'?"

This should prevent Random from shifting truth-stances between the two questions. (Assuming the internal coin flip is determinate, so that it could not have landed differently had you asked a different question in place of that one.)

douglys said...

Thanks Richard. Thats right. Here is the worry again:

Assume 'ja' means yes and 'Q' is true.

Ask Random @t1: If I asked you 'Q' would you say 'ja'?
Coin = Liar
Answer: 'da'

Ask Random @t2: Q?
Coin = Truth-teller
Answer: 'ja'

Random answered 'da' but Q is true. This seems to contradict EQL* (i.e. when any God is asked E(Q), a response of 'ja' indicates that the correct answer to Q is 'yes' and a response of 'da' indicates that the correct answer to Q is 'no').

First note that the first question we put to Random is underspecified. When we direct that question to True, really what we are sayng is: 'If *at any time* I asked you 'Q' would you say 'ja'?' or better 'For all times t, if I asked you 'Q' at t would you say 'ja'?'

But we don't want to put that question to Random. When the coin=true, he will answer negatively and when coin=lie he will answer affirmatively, and he will do this regardless of the truth-value of Q.

We need a fix along the lines you suggest. I think your question does the trick but this is a bit simplier and I think it also does the trick.

E`(Q) = 'If I asked you 'Q' *right now* would you say 'ja'?'

douglys said...

If I asked you 'Q' *in your present state of mind* would you say 'ja'?

also works. I guess what I suggested before or this is what we meant by E(Q).

In any case, the precisified question supports the thesis.

EQL*: When any God is asked "If I asked you 'Q' in your present state of mind would you say 'ja'?" a response of 'ja' indicates that the correct answer to Q is 'yes' and a response of 'da' indicates that the correct answer to Q is 'no'

mex (aka Syb) said...

say what?

the metaphysician said...

I think you should definitely try to publish your (and your brother's) results. It's rigorous, terse, elegant, and, I think, correct. It's the kind of piece that's tailor made for a journal like ANALYSIS.