The Hardest Logic Puzzle Ever

George Boolos' original puzzle is stated as follows:

Three gods A, B, and C are called, in no particular 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.

  • It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).
  • What the second question is, and to which god it is put, may depend on the answer to the first question. (And of course similarly for the third question.)
  • Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.

You can play the JavaScript version here! How many questions did it take you?

Notes for the JavaScript version

Instead of asking a question in English, enter a JavaScript expression evaluating to true or false. For examples:

English question JavaScript expression
"Is A True?" A === True
"Does da mean 'yes'?" da === "yes"
"If I asked B 'Are you True?', would it say 'da'?" B.ask(B === True) === "da"
"Is two plus two equal to four?" 2 + 2 === 4
or just true

(Yes, eval() is used here, leaving you at mortal risk of XSS-attacking yourself.)

In this version you may ask as many questions as you like. However, as Boolos' original puzzle implies,

  1. it is possible to identify the gods with certainty in just three questions, and
  2. it is not possible to identify the gods with certainty in fewer than three questions.

Cheating and the JavaScript metaphor

Even if you limit yourself to entering code in the "Question" box, there are numerous ways to cheat. In fact, I find it extremely interesting to compare cheating in JavaScript with the analogous ways to cheat the original logic puzzle.

alert()

Using alert() or other elementary out-of-band signalling techniques is a confession of defeat.

In the metaphor, using alert() is akin to asking a god, "Hey. Please write your real name on the floor in sand, where I can read it. Now, onto my real question..." The conditions of the puzzle are that you can only ask a single yes/no question; you're not allowed to give the gods direct instructions, even if they would comply.

Variable assignment

The puzzle scenario also does not allow you to modify the world yourself. You may only passively ask questions.

Unfortunately, in the JavaScript world, you are able to provide expressions which would permanently modify the game environment. In effect, you take the role of another god with vastly greater power than True, False and Random, whom you can duplicate and destroy at a whim, and whose dictionary you can freely rewrite.

Just to begin with, you can engineer an easy win in the space of a single question, if you know which variables to set and functions to call.

Out of curiosity, I experimented with ways of sandboxing the eval() call: setting window = undefined beforehand, engineering a scope whereby the game logic was not accessible, and so on. I learned a lot about JavaScript's scoping rules, but decided the endeavour was futile, and dropped it.

Exploding heads

Exploding heads are very interesting. There are several ways to cause a god's head to explode, and several ways to cause equivalent mayhem in JavaScript.

Self-referential questions

Since the string variable question is available when eval() is called, self-referential questions are not only possible but usually break the universe pretty effectively:

"Are you going to answer this question with the word that means no in your language?"

A.ask(question) === (da === "no" ? "da" : "ja")

Or:

"Would you answer ja to the question of whether you would answer da to this question?"

"ja" === A.ask("da" === A.ask(question))

In JavaScript, both of these cause stack explosions. So much for the liar paradox; the JavaScript gods are too simple to realise that the question is unanswerable.

Infinite loop

You can stall a god indefinitely, thereby locking up your browser, using while(true){}. This is roughly equivalent to asking "Is the last binary digit of pi 0?"

Exception-throwing

This is more benign.

You can try asking questions about things (i.e. variables) which don't exist ("Is June the capital of yellow?" / June === yellow.capital).

You can cause the JavaScript to throw an exception directly using e.g. throw "urk".

Questions which are not yes/no questions also throw exceptions ("What time is it?" / new Date()).

Technically, all of these extra behaviours qualify as "out-of-band signalling", which is why they're filed here under "Cheating". Even staying at the benign end of the scale, this allows us to structure questions with three possible responses, "da", "ja" and a thrown exception/head explosion. This allows us to theoretically solve the problem using just two questions rather than three.

Ask about Random's behaviour

Another suggested head-exploder is

"Would you answer the same as Random would to the question 'Is two plus two four?'?"

Transmuting this question into JavaScript drains a lot of its supposed power. Clearly, this is just an indirect way of generating random answers:

A.ask(2 + 2 === 4) === Random.ask(2 + 2 === 4)

Rabern and Rabern (2008) on Random's behaviour

This is bunk.

As stated in the puzzle, the god Random randomly acts as a truth-teller (i.e., like True) or a falsehood-teller (i.e., like False) depending on a figurative coin flip inside its head. (Although the puzzle is unclear, it is implicit that one coin flip is carried out per question, rather than a single coin flip determining all future behaviour.)

In this JavaScript implementation, Random's coin can be accessed using Random.coin, which has string values "heads" or "tails".

Rabern and Rabern suggest asking A "If I asked you 'Are you Random?' in your current mental state, would you say ja?", as a way to suppress the coin-flip mechanism in the event that A is, indeed, Random.

Unfortunately, what they forget is that regardless of its current mental state, Random always flips a coin, potentially altering its mental state, before deciding what answer to return. Try plugging this into the game and see how far it gets you:

A.ask(A === Random) === "ja"

Solution

3 questions are necessary and sufficient to solve this problem.

Necessity

Each yes/no question can at best divide the possibility space in half, rounded up.

  • Initially, there are 3! = 6 possible configurations of the three gods.
  • After 1 question, best case scenario, we would have 3 remaining possibilities.
  • After 2 questions, best case scenario, we would have ⌈1.5⌉ = 2 remaining possibilities.
  • Therefore, at least 3 questions are necessary to reach 1 possibility.

Sufficiency

Spoilers. This table is the JavaScript translation of the English-language solution on Wikipedia.

Question 1 Answer 1 Question 2 Answer 2 Question 3 Answer 3 A B C
Ask B, B.ask(A === Random) === "ja". da Ask A, A.ask(A === False) === "ja". da Ask A, A.ask(B === Random) === "ja". da True False Random
da da ja True Random False
da ja da False True Random
da ja ja False Random True
ja Ask C, C.ask(C === False) === "ja". da Ask C, C.ask(B === Random) === "ja". da Random False True
ja da ja False Random True
ja ja da Random True False
ja ja ja True Random False

Notice how, at the end of the three questions, we still do not know the meanings of the words da and ja. This piece of information doubles the number of possibilities to 12; therefore, determining it increases the number of required questions to 4. Since we don't need to know this information to answer the logic puzzle, we deliberately avoid discovering it.

Of course, after three questions, we know the identity of True. If we cared, we could simply ask True a fourth question: true. Its response is the word for yes, and whatever it doesn't say is the word for no.

Exploding heads solution

With three possible answers to each question (da, ja and head explodes), each question divides the possibility space in three, rounded up. Thus, only two questions are required. Each question positively identifies a single god; the third is whoever is left.

Question 1 Answer 1 Question 2 Answer 2 A B C
Ask A, A === True ? A.ask(true) === "da" :
A === False ? A.ask(true) === "ja" :
676
.
da Ask B, B === True ? B.ask(true) === "da" :
B === False ? B.ask(true) === "ja" :
676
.
ja True False Random
head explodes True Random False
ja da False True Random
head explodes False Random True
head explodes da Random True False
ja Random False True

Again, after the questioning is over, we do not know the meaning of the words da and ja.

Discussion (23)

2014-01-26 00:37:40 by qntm:

I just discovered a pretty unpleasant defect with my "all possible universes"-handling code. E.g. if you ask A "Random.ask(true) === 'da'" enough times, the game concludes that A must be Random. OH WELL

2014-01-26 00:39:09 by DanielLC:

They give a very confusing explanation of Random's behavior. A much simpler model that is effectively the same is: Random ignores the question and answers "ja" or "da" at random. This is different in that Random cannot be defeated by the liar paradox or while(true) etc., but since you're not supposed to do that anyway, it's not a big deal.

2014-01-26 09:19:55 by danil:

I think a better phrasing of Rabern and Rabern's question would be: "If I had asked you Q instead of this question, would you say 'ja'?" As long as the coin flip in Random's head doesn't depend on what question you ask, the counterfactual world in which you had asked a different question should have the same coin flip as the real world, and the cancellation goes through.

2014-01-26 12:33:09 by qntm:

danil: but clearly, the flip of the coin does depend on the question asked. In fact, the coin will always flip no matter what, and because of the nature of randomness it could come down differently regardless of identical starting conditions. If you want to try to render your suggestion into JavaScript, be my guest, but I suspect that you'll find this impossible, or find that your result gives random answers still.

2014-01-26 20:01:28 by itaibn:

Another cheat: If a query doesn't evaluate to a boolean, the god always responds 'This is not a yes/no question. Please try again.' By asking things such as "ja == 'yes' ? true : 'banana'" you can gain trustworthy information from any god. I tested this, and apparently non-boolean results don't even count as questions, and so my result ended being that I guess correctly in 0 questions. In general it should be possible to guess in one 'question'.

2014-01-27 00:22:14 by nathanwe:

I don't understand the section on Random's behavior. I think it is saying that reclusive questions (e.g. if I asked you ...) to random result in multiple coin flips. Does the question "is the following true: (you are true/false/random) XOR (you are acting like false right now) XOR (ja means yes)" work? Note: I am not a java programmer.

2014-01-28 00:11:44 by g:

If any of the gods answers "ra", panic.

2014-02-05 09:46:11 by HiEv:

Technically, there *is* a way to get the answer in two guesses, but a bit of luck is involved. You could ask the question of God A, "If you are the Truth God, does 1+1=2; if you are the False or Random God, how tall is a banana tree?" If you get a "ja" or "da", you not only know God A is the truth god, but you also know whatever that god said is the word for "true". If the god doesn't respond, you know it's the False or Random God, and one of the two other gods is the Truth God. If God A turned out to be the Truth God, then for your second question you could ask God B, "If you are the Liar God, does 1+1=1; or if you are the Random God, how many donuts in a dozen?" If God B says the same word as the Truth God, you know that this is the Liar God, and the remaining God is the Random God. If the God B says nothing, then you have the Random God, and you know the other god is the Liar God. If God A wasn't the Truth God, then for your second question you could ask God B the same question as God A. If God B answered, that's the Truth God, if no response, then God C is the Truth God. It's then easy to determine which of the other two gods is which with the third question. The trick is, there aren't only two answers "ja" and "da", there's actually a third "answer", which is "no response", since they only answer yes or no questions. So if you get lucky and get the first guess correctly, it *can* be resolved in only two questions, and you even get to know what "ja" and "da" mean too.

2014-02-05 10:22:26 by qntm:

Very good, that's exactly as stated in the article. Your homework is to turn your strategy into a series of JavaScript expressions and demonstrate them in action :D

2014-02-05 23:53:20 by qntm:

I went ahead and did your homework for you. Ask A, 'A === True ? A.ask(true) === "da" : A === False ? A.ask(true) === "ja" : 676'. If A is True, the first branch is evaluated, and "da" is always returned regardless of what "da" means. If A is False, the second branch is evaluated, and "ja" is always returned regardless of what "ja" means. If A is Random, the third branch is evaluated, and you are told to ask a different question. In any case we now know A's identity. Next, ask B 'B === True ? B.ask(true) === "da" : B === False ? B.ask(true) === "ja" : 676'. The same logic applies. A response of "da" indicates B is True. "Ja" indicates B is False. An exception indicates B is Random. Now we know B's identity. C's identity is whichever god is left. In any case you have all three gods in only two questions. Possibly the game only counted one yes/no question, if A or B were Random.

2014-03-18 21:50:45 by Eduardo:

Sam, your expresion: A === True ? A.ask(true) === "da" : A === False ? A.ask(true) === "ja" : 676 What does mean translated in regular speech? (I am not conversant in math symbols)

2014-03-20 22:44:40 by Stephen:

This article explains in great detail how to solve the puzzle in only three questions, and additionally it explains why it so important to accurately interpret the puzzle correctly. http://worldsmostdifficultlogicalpuzzle.blogspot.com/

2014-03-27 14:47:12 by Aegeus:

@Eduardo: "If A is True, would asking A "true" yield "da"? Otherwise, if A is False, would asking A "true" yield "ja"? Otherwise, my question is "676". "true" can be any question whose answer is "yes." "Does 2+2=4?" would work for this. "676" is not a yes/no question, so Random will reject the question. "How tall is a banana tree?" is a good English equivalent.

2014-04-21 02:35:59 by robje:

@stephen: the solution givven in that article is wrong. @sam: are you saying that all "exploding heads" solution are cheats?

2015-04-20 13:19:16 by EyWtt:

Your missing the point of Rabern and Rabern's discussion of Random's behaviour. Consider what happens when you ask Random this: "If I asked you 'Is 2 prime?' would you say 'yes'?" If the coin lands heads, he says 'yes', if the coin lands tails, he says 'yes'. Not very "random". The whole coin flip business is, then , moot.

2015-04-20 16:32:42 by qntm:

*Two* coins get flipped when you ask that question. One in the hypothetical, and one in reality. And they don't have to come down on the same side.

2015-04-22 09:39:54 by EyWtt:

It's not clear why "two coins get flipped", but I take it that is why R&R anchor to a particular "mental state" (coin flip). But all that doesn't really matter. Make the point without using counterfactuals. Consider what happens when you ask Random this: Is it that case that: 2 is prime iff you are telling the truth? Heads (truth-teller): yes Tails (liar): yes Not very "random". So you're wrong, this does indeed suppress the coin-flip mechanism.

2015-04-22 10:47:00 by qntm:

Okay, now go and render "Is it that case that: 2 is prime iff you are telling the truth?" into a JavaScript expression. Or even read the original article, where I already covered that kind of metaquestion.

2015-04-22 11:34:27 by EyWtt:

If you are suggesting that it is hard to render that question for input into your program, then that is a problem with your program--logical operations should be easy enough. If you can put it in your machine, then either it gives the wrong result or you agree that the coin-flip mechanism is suppressed.

2015-04-22 13:19:54 by qntm:

Well, the whole point of this exercise was to make the structure of the logic problem more rigorous and formal, to make it easier to resolve this kind of tricky question about exactly what the gods do when they need to answer questions, and how they would react to unanswerable self-referential questions. It's quite obvious that when you ask Random questions about itself, two coin flips take place - you only have to follow the code to see this. Similarly, self-referential questions result in stack explosions. Of course, this is not the only possible implementation, and it would be interesting to see the behaviour of an implementation which *was* able to resolve self-referential questions, and where Random's behaviour can be suppressed in this way.

2015-04-22 13:33:59 by EyWtt:

This dissertation is very much in the spirit of making this puzzle more rigorous and formal: https://pure.uvt.nl/portal/files/1391314/Wintein_playing_10-02-2012.pdf It's worth checking out.

2015-04-24 10:38:26 by GU:

I believe the following questions also work with no need to ask a god about another god: (to A) da === "yes" ||| A === False (to B) da === "yes" ||| B === True (to C) da === "no" ||| C === False Fill in a truth table with da = (y/n) and random=(a/b/c) by assigning labels to the gods based on assuming which one is random and which word means yes/no and you will find that only one set of answers stays logically consistent for the six possible assignments.

2015-08-31 03:16:02 by Anon:

@GU That can't actually work out properly. Remember that random can always answer either way, so each ordering of gods has two sets of answers to any non-conditional sets of questions. You have a stable answer from truth, a stable answer from false and an unstable answer from random, for 1x1x2=2. You have 6 orderings and 6 possible answer combinations. If each ordering maps to 2 possible answer combinations, the 6 answer combinations cannot each map to a unique ordering.

This discussion is closed.