The Hardest Logic Puzzle Ever is a logic puzzle so called by American philosopher and logician George Boolos and published in The Harvard Review of Philosophy in 1996. Boolos' article includes multiple ways of solving the problem. A translation in Italian was published earlier in the newspaper La Repubblica, under the title L'indovinello più difficile del mondo.
It is stated as follows:
Boolos provides the following clarifications: a single god may be asked more than one question, questions are permitted to depend on the answers to earlier questions, and the nature of Random's response should be thought of as depending on the flip of a fair coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.Note that the Random god in Boolos' puzzle is a god who acts randomly as either a truth-teller or a liar. This is different from a god who answers 'yes' or 'no' randomly. One usual trick in solving many logic puzzles is to design a (perhaps composite) question that forces both a truth-teller and a liar to answer 'yes'. For such a question, a person who randomly chooses to be a truth-teller or a liar is still forced to answer 'yes', but a person who answers randomly may answer 'yes' or 'no'.
History
Boolos credits the logician Raymond Smullyan as the originator of the puzzle and John McCarthy with adding the difficulty of not knowing what da and ja mean. Related puzzles can be found throughout Smullyan's writings. For example, in What is the Name of This Book?, he describes a Haitian island where half the inhabitants are zombies (who always lie) and half are humans (who always tell the truth). He explains that "the situation is enormously complicated by the fact that although all the natives understand English perfectly, an ancient taboo of the island forbids them ever to use non-native words in their speech. Hence whenever you ask them a yes–no question, they reply Bal or Da—one of which means yes and the other no. The trouble is that we do not know which of Bal or Da means yes and which means no." There are other related puzzles in The Riddle of Scheherazade.
The puzzle is based on Knights and Knaves puzzles. One setting for this puzzle is a fictional island inhabited only by knights and knaves, where knights always tell the truth and knaves always lie. A visitor to the island must ask a number of yes/no questions in order to discover what he needs to know (the specifics of which vary between different versions of the puzzle). One version of these puzzles was popularized by a scene in the 1986 fantasy film Labyrinth. There are two doors, each with one guard. One guard always lies and the other always answers truthfully. One door leads to the castle and the other leads to 'certain death'. The puzzle is to find out which door leads to the castle by asking one of the guards one question. In the movie, the protagonist does this by asking "Would he [the other guard] tell me that this door leads to the castle?"
Solutions Boolos provided his solution in the same article in which he introduced the puzzle. Boolos states that the "first move is to find a god that you can be certain is not Random, and hence is either True or False". There are many different questions that will achieve this result. One strategy is to use complicated logical connectives in your questions (either biconditionals or some equivalent construction).
Boolos' question was to ask A:
Does da mean yes if and only if you are True, if and only if B is Random?
In everyday language, this sentence is hardly comprehensible. In logical terminology, “if and only if” is meant as: do two propositions have the same truth value? So, the sentence is intended to express the following logical connection:
(da = yes) NXOR (you are True) NXOR (B is Random).
Using another notation (where ⊕ means XOR and ¬ means NOT):
(da = yes) ¬⊕ (you are True) ¬⊕ (B is Random).
A logical equivalent is the following sentence, more comprehensible in everyday language:
Are an odd number of the following statements true: da means yes, you are True, B is Random?
It was observed by Roberts (2001) and by Rabern and Rabern (2008) that the puzzle's solution can be simplified by using certain counterfactuals. The key to this solution is that, for any yes/no question Q, asking either True or False to the question:
If I asked you Q, would you say ja?
the answer ja means the truthful answer to Q is yes, and the answer da means the truthful answer to Q is no (Rabern and Rabern (2008) call this result the embedded question lemma). It also works with any other expression for yes and no - if the given expression is repeated, the Answer to Q is yes, and otherwise it is no.
This can be seen by reasoning through all possible cases (the meaning of ja and da, which god we ask, and what their answer is): Assume that ja means yes and da means no. True is asked and responds with ja. Since he is telling the truth, the truthful answer to Q is ja, which means yes. True is asked and responds with da. Since he is telling the truth, the truthful answer to Q is da, which means no. False is asked and responds with ja. Since he is lying, it follows that if you asked him Q, he would instead answer da. He would be lying, so the truthful answer to Q is ja, which means yes. False is asked and responds with da. Since he is lying, it follows that if you asked him Q, he would in fact answer ja. He would be lying, so the truthful answer to Q is da, which means no.
Assume ja means no and da means yes. True is asked and responds with ja. Since he is telling the truth, the truthful answer to Q is da, which means yes. True is asked and responds with da. Since he is telling the truth, the truthful answer to Q is ja, which means no. False is asked and responds with ja. Since he is lying, it follows that if you asked him Q, he would in fact answer ja. He would be lying, so the truthful answer to Q is da, which means yes. False is asked and responds with da. Since he is lying, it follows that if you asked him Q, he would instead answer da. He would be lying, so the truthful answer to Q is ja, which means no. The reason this works can also be seen by studying the logical form of the expected answer to the question. This logical form (Boolean expression) is developed below ('Q' is true if the answer to Q is 'yes', 'God' is true if the god to whom the question is asked is acting as a truth-teller and 'Ja' is true if the meaning of ja is 'yes'): How a god would choose to answer Q is given by the negation of the exclusive disjunction between Q and God (if the answer to Q and the nature of the god are opposite, the answer given by the god is bound to be 'no', while if they are the same, it is bound to be 'yes'): ¬ ( Q ⊕ God) Whether the answer given by the god would be ja or not is given again by the negation of the exclusive disjunction between the previous result and Ja ¬ ( ( ¬ ( Q ⊕ God) ) ⊕ Ja ) The result of step two gives the truthful answer to the question: 'If I ask you Q, would you say ja'? What would be the answer the God will give can be ascertained by using reasoning similar to that used in step 1 ¬ ( ( ¬ ( ( ¬ ( Q ⊕ God) ) ⊕ Ja ) ) ⊕ God ) Finally, to find out if this answer will be ja or da, (yet another) negation of the exclusive disjunction of Ja with the result of step 3 will be required ¬ ( ( ¬ ( ( ¬ ( ( ¬ ( Q ⊕ God) ) ⊕ Ja ) ) ⊕ God ) ) ⊕ Ja )
This final expression evaluates to true if the answer is ja, and false otherwise. The eight cases are worked out below (1 represents true, and 0 false). Q True if answer to
Q is 'yes'God True if god behaves
as truth-tellerJa True if meaning of
ja is 'yes'Step 1 (God's answer to Q)Step 2 (Is it ja?)Step 3 (God's answer to counterfactual)Step 4 (Is it ja?)00010100011100010011001100001000101101001111010011111111 Comparing the first and last columns makes it plain that the answer is ja only when the answer to the question is 'yes'. The same results apply if the question asked were instead: 'If I asked you Q, would you say da'? because the evaluation of the counterfactual does not depend superficially on meanings of ja and da.
Regardless of whether the asked god is lying or not and regardless of which word means yes and which no, you can determine if the truthful answer to Q is yes or no.
The solution below constructs its three questions using the lemma described above. Q1: Ask god B, "If I asked you 'Is A Random?', would you say ja?". If B answers ja, either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is indeed Random. Either way, C is not Random. If B answers da, either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is not Random. Either way, you know the identity of a god who is not Random. Q2: Go to the god who was identified as not being Random by the previous question (either A or C), and ask him: "If I asked you 'Are you False?', would you say ja?". Since he is not Random, an answer of da indicates that he is True and an answer of ja indicates that he is False. Q3: Ask the same god the question: "If I asked you 'Is B Random?', would you say ja?". If the answer is ja, B is Random; if the answer is da, the god you have not yet spoken to is Random. The remaining god can be identified by elimination.
Case 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16A True True False Random False Random True True False Random False RandomB False Random True True Random False False Random True True Random FalseC Random False Random False True True Random False Random False True TrueDa Yes Yes Yes Yes Yes Yes No No No No No NoJa No No No No No No Yes Yes Yes Yes Yes YesIs A indeed Random? No No No Yes No Yes No No No Yes No YesHow would B answer "Is A Random?" English Yes Either No Yes Either No Yes Either No Yes Either No Their language Da Either Ja Da Either Ja Ja Either Da Ja Either DaB's response to Question 1—"If I asked you 'Is A Random', would you say ja?" English Yes Either Yes No Either No No Either No Yes Either YesTheir languageDa Either Da Ja Either Ja Da Either Da Ja Either Ja Da Ja Da Ja Da Ja Da JaThus __ (hereafter called X) is not Random. A A C A C A C C A A C A C A C CIs X indeed False? No No Yes Yes Yes Yes No No No No Yes Yes Yes Yes No NoHow would X answer "Are you False?" English No No No No No No No No No No No No No No No No Their language Ja Ja Ja Ja Ja Ja Ja Ja Da Da Da Da Da Da Da DaX's response to Question 2—"If I asked you 'Are you False?', would you say ja?" English Yes Yes No No No No Yes Yes No No Yes Yes Yes Yes No No Their language Da Da Ja Ja Ja Ja Da Da Da Da Ja Ja Ja Ja Da DaThus X is __. True True False False False False True True True True False False False False True TrueIs B indeed Random? No Yes No No Yes No No Yes No No Yes NoHow would X answer "Is B Random?" English No Yes No Yes Yes No Yes No No Yes No Yes Yes No Yes No Their language Ja Da Ja Da Da Ja Da Ja Da Ja Da Ja Ja Da Ja DaX's response to Question 3—"If I asked you 'Is B Random?', would you say ja?" English Yes No No Yes Yes No No Yes No Yes Yes No No Yes Yes No Their language Da Ja Ja Da Da Ja Ja Da Da Ja Ja Da Da Ja Ja DaThus __ is Random. C B B C A B B A C B B C A B B AThus by elimination, (Letter) is (Name). Letter B C A B B C A B B C A B B C A B Name False False True True True True False False False False True True True True False False
A similar table as above would prove that the first question given by Boolos has, in the end, the same effect and logical structure as the counterfactual tricks of Roberts and Rabern/Rabern. Random's behavior
Boolos' third clarifying remark explains Random's behavior as follows:
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.