The Hardest Logic Puzzle Ever


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.

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 and half are humans. 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. One version of these puzzles was popularized by a scene in the 1986 fantasy film Labyrinth. There are two doors with two guards. One guard lies and one guard does not. 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 Sarah, does this by asking, "Would he tell me that this door leads to the castle?"

The solution

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.
Boolos' question was to ask A:
Equivalently:
It was observed by Roberts and independently by Rabern and Rabern 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 the question
results in the answer ja if the truthful answer to Q is yes, and the answer da if the truthful answer to Q is no. The reason this works can be seen by studying the logical form of the expected answer to the question. This logical form is developed below :
  1. How a god would choose to answer Q is given by the negation of the exclusive disjunction between Q and God :
  2. * ¬
  3. 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
  4. * ¬
  5. 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
  6. * ¬ ⊕ God )
  7. Finally, to find out if this answer will be Ja or Da, negation of the exclusive disjunction of Ja with the result of step 3 will be required
  8. * ¬ ⊕ God ) ) ⊕ Ja )
This final expression evaluates to true if the answer is Ja, and false otherwise. The eight cases are worked out below :
Q
True if answer to
Q is 'yes'		God
True if god behaves
as truth-teller		Ja
True if meaning of
Ja is 'yes'		Step 1
Step 2
Step 3
Step 4
0001010
0011100
0100110
0110000
1000101
1010011
1101001
1111111

Comparing the first and last columns makes it plain to see 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. Each of the eight cases are equivalently reasoned out below in words:
  1. True is asked and responds with ja. Since he is telling the truth, the truthful answer to Q is ja, which means yes.
  2. True is asked and responds with da. Since he is telling the truth, the truthful answer to Q is da, which means no.
  3. 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.
  4. 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.
  1. True is asked and responds with ja. Since he is telling the truth, the truthful answer to Q is da, which means yes.
  2. True is asked and responds with da. Since he is telling the truth, the truthful answer to Q is ja, which means no.
  3. 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.
  4. 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.
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.

Random's behavior

Boolos' third clarifying remark explains Random's behavior as follows:
This does not state if the coin flip is for each question, or each "session", that is the entire series of questions. If interpreted as being a single random selection which lasts for the duration of the session, Rabern and Rabern show that the puzzle could be solved in only two questions; this is because the counterfactual had been designed such that regardless of whether the answerer was as a truth-teller or a false-teller, the truthful answer to Q would be clear.
Another possible interpretation of Random's behaviour when faced with the counterfactual is that he answers the question in its totality after flipping the coin in his head, but figures out the answer to Q in his previous state of mind, while the question is being asked. Once again, this makes asking Random the counterfactual useless. If this is the case, a small change to the question above yields a question which will always elicit a meaningful answer from Random. The change is as follows:
This effectively extracts the truth-teller and liar personalities from Random and forces him to be only one of them. By doing so the puzzle becomes completely trivial, that is, truthful answers can be easily obtained. However, it assumes that Random has decided to lie or tell the truth prior to determining the correct answer to the question – something not stated by the puzzle or the clarifying remark.
One can elegantly obtain truthful answers in the course of solving the original problem as clarified by Boolos without relying on any purportedly unstated assumptions, by making a further change to the question:
Here, the only assumption is that Random, in answering the question, is either answering truthfully OR is answering falsely which are explicitly part of the clarifications of Boolos. The original unmodified problem in this way can be seen to be the "Hardest Logical Puzzle Ever" with the most elegant and uncomplicated looking solution.
Rabern and Rabern suggest making an amendment to Boolos' original puzzle so that Random is actually random. The modification is to replace Boolos' third clarifying remark with the following:
With this modification, the puzzle's solution demands the more careful god-interrogation given at the top of The Solution section.

Unanswerable questions and exploding god-heads

In A simple solution to the hardest logic puzzle ever, B. Rabern and L. Rabern offer a variant of the puzzle: a god, confronted with a paradox, will say neither ja nor da and instead not answer at all. For example, if the question "Are you going to answer this question with the word that means no in your language?" is put to True, he cannot answer truthfully. Allowing the "exploding head" case gives yet another solution of the puzzle and introduces the possibility of solving the puzzle in just two questions rather than three. In support of a two-question solution to the puzzle, the authors solve a similar simpler puzzle using just two questions.
Note that this puzzle is trivially solved with three questions. Furthermore, to solve the puzzle in two questions, the following lemma is proved.
Using this lemma it is simple to solve the puzzle in two questions. Rabern and Rabern use a similar trick to solve the original puzzle in just two questions. Uzquiano uses these techniques to provide a two question solution to the amended puzzle. Two question solutions to both the original and amended puzzle take advantage of the fact that some gods have an inability to answer certain questions. Neither True nor False can provide an answer to the following question.
Since the amended Random answers in a truly random manner, neither True nor False can predict whether Random would answer ja or da to the question of whether Dushanbe is in Kirghizia. Given this ignorance they will be unable to tell the truth or lie – they will therefore remain silent. Random, however, who spouts random nonsense, will have no problem spouting off either ja or da. Uzquiano exploits this asymmetry to provide a two question solution to the modified puzzle. Yet, one might assume that the gods have an "oracular ability to predict Random's answers even before the coin flip in Random’s brain?" In this case, a two question solution is still available by using self-referential questions of the style employed in Rabern and Rabern.
Here again neither True nor False are able to answer this question given their commitments of truth-telling and lying, respectively. They are forced to answer ja just in case the answer they are committed to give is da and this they cannot do. Just as before they will suffer a head explosion. In contrast, Random will mindlessly spout his nonsense and randomly answer ja or da. Uzquiano also uses this asymmetry to provide a two question solution to the modified puzzle. However, Uzquiano's own modification to the puzzle, which eliminates this asymmetry by allowing Random to either answer "ja", "da", or remain silent, cannot be solved in fewer than three questions.