George Boolos' original puzzle is stated as follows:
Three gods A, B, and C are called, in no particular order,
True
,False
, andRandom
.True
always speaks truly,False
always speaks falsely, but whetherRandom
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?
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,
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.
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 are very interesting. There are several ways to cause a god's head to explode, and several ways to cause equivalent mayhem in JavaScript.
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.
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?"
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.
Random
's behaviourAnother 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)
Random
's behaviourAs 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"
3 questions are necessary and sufficient to solve this problem.
Each yes/no question can at best divide the possibility space in half, rounded up.
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.
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" : . |
da | Ask B, B === True ? B.ask(true) === "da" : . |
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:
2014-01-26 00:39:09 by DanielLC:
2014-01-26 09:19:55 by danil:
2014-01-26 12:33:09 by qntm:
2014-01-26 20:01:28 by itaibn:
2014-01-27 00:22:14 by nathanwe:
2014-01-28 00:11:44 by g:
2014-02-05 09:46:11 by HiEv:
2014-02-05 10:22:26 by qntm:
2014-02-05 23:53:20 by qntm:
2014-03-18 21:50:45 by Eduardo:
2014-03-20 22:44:40 by Stephen:
2014-03-27 14:47:12 by Aegeus:
2014-04-21 02:35:59 by robje:
2015-04-20 13:19:16 by EyWtt:
2015-04-20 16:32:42 by qntm:
2015-04-22 09:39:54 by EyWtt:
2015-04-22 10:47:00 by qntm:
2015-04-22 11:34:27 by EyWtt:
2015-04-22 13:19:54 by qntm:
2015-04-22 13:33:59 by EyWtt:
2015-04-24 10:38:26 by GU:
2015-08-31 03:16:02 by Anon:
This discussion is closed.