The Hardest Logic Puzzle Ever
Encyclopedia
The Hardest Logic Puzzle Ever is a title coined by American philosopher and logician George Boolos
in an article published in The Harvard Review of Philosophy
in 1996 (an Italian
translation was published earlier in the newspaper La Repubblica
, under the title L'indovinello più difficile del mondo) for the following Raymond Smullyan
inspired logic puzzle:
Boolos provides the following clarifications:
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, e.g. in What is the Name of This Book?, pp. 149–156, he describes a Haitian island where half the inhabitants are zombies (who always lie) and half are humans (who always tell the truth) and 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 Sheherazade.
More generally this puzzle is based on Smullyan's famous Knights and Knaves
puzzles (e.g. on a fictional island, all inhabitants are either knights, who always tell the truth, or knaves, who always lie. The puzzles involve a visitor to the island who must ask a number of yes/no questions in order to discover what he needs to know). A 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, named Sarah, does this by asking, "Would he [the other guard] tell me that this door leads to the castle?"
or some equivalent construction).
Boolos' question was to ask A:
Equivalently:
It was observed by Roberts (2001) -- and independently 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 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 (Rabern and Rabern (2008) call this result the embedded question lemma). The reason it works can be seen by looking at the eight possible cases.
The solution below constructs its three questions using the lemma described above.
This says that Random randomly acts as a false-teller or a truth-teller, not that Random answers randomly.
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 simpler.
Rabern and Rabern (2008) 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 end of the The Solution section.
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 (2008) use a similar trick (tempering the liar's paradox) to solve the original puzzle in just two questions. In "How to solve the hardest logic puzzle ever in two questions" G. 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 (2010) 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 (2008).
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 (2010) also uses this asymmetry to provide a two question solution to the modified puzzle.
George Boolos
George Stephen Boolos was a philosopher and a mathematical logician who taught at the Massachusetts Institute of Technology.- Life :...
in an article published in The Harvard Review of Philosophy
The Harvard Review of Philosophy
The Harvard Review of Philosophy is an academic journal covering philosophy and published annually as a single volume since 1991. The journal is entirely edited and published by students at Harvard University, mostly undergraduates....
in 1996 (an Italian
Italian language
Italian is a Romance language spoken mainly in Europe: Italy, Switzerland, San Marino, Vatican City, by minorities in Malta, Monaco, Croatia, Slovenia, France, Libya, Eritrea, and Somalia, and by immigrant communities in the Americas and Australia...
translation was published earlier in the newspaper La Repubblica
La Repubblica
la Repubblica is an Italian daily general-interest newspaper. Founded in 1976 in Rome by the journalist Eugenio Scalfari, as of 2008 is the second largest circulation newspaper, behind the Corriere della Sera.-Foundation:...
, under the title L'indovinello più difficile del mondo) for the following Raymond Smullyan
Raymond Smullyan
Raymond Merrill Smullyan is an American mathematician, concert pianist, logician, Taoist philosopher, and magician.Born in Far Rockaway, New York, his first career was stage magic. He then earned a BSc from the University of Chicago in 1955 and his Ph.D. from Princeton University in 1959...
inspired logic puzzle:
Boolos provides the following clarifications:
History
Boolos credits the logician Raymond SmullyanRaymond Smullyan
Raymond Merrill Smullyan is an American mathematician, concert pianist, logician, Taoist philosopher, and magician.Born in Far Rockaway, New York, his first career was stage magic. He then earned a BSc from the University of Chicago in 1955 and his Ph.D. from Princeton University in 1959...
as the originator of the puzzle and John McCarthy
John McCarthy (computer scientist)
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
with adding the difficulty of not knowing what da and ja mean. Related puzzles can be found throughout Smullyan's writings, e.g. in What is the Name of This Book?, pp. 149–156, he describes a Haitian island where half the inhabitants are zombies (who always lie) and half are humans (who always tell the truth) and 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 Sheherazade.
More generally this puzzle is based on Smullyan's famous Knights and Knaves
Knights and knaves
Knights and Knaves is a type of logic puzzle devised by Raymond Smullyan.On a fictional island, all inhabitants are either knights, who always tell the truth, or knaves, who always lie. The puzzles involve a visitor to the island who meets small groups of inhabitants...
puzzles (e.g. on a fictional island, all inhabitants are either knights, who always tell the truth, or knaves, who always lie. The puzzles involve a visitor to the island who must ask a number of yes/no questions in order to discover what he needs to know). A version of these puzzles was popularized by a scene in the 1986 fantasy film, Labyrinth
Labyrinth (film)
Labyrinth is a 1986 British/American fantasy film directed by Jim Henson, produced by George Lucas, and designed by Brian Froud. Henson collaborated on the screenwriting with children's author Dennis Lee, Terry Jones from Monty Python, and Elaine May .The film stars David Bowie as Jareth the Goblin...
. 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, named Sarah, does this by asking, "Would he [the other guard] 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 (either biconditionalsLogical biconditional
In logic and mathematics, the logical biconditional is the logical connective of two statements asserting "p if and only if q", where q is a hypothesis and p is a conclusion...
or some equivalent construction).
Boolos' question was to ask A:
- Does da mean yes iffIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
you are True iffIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
B is Random?
Equivalently:
- Are an odd number of the following statements true: you are False, da means yes, B is Random?
It was observed by Roberts (2001) -- and independently by Rabern and Rabern (2008) -- that the puzzle's solution can be simplified by using certain counterfactuals
Counterfactual conditional
A counterfactual conditional, subjunctive conditional, or remote conditional, abbreviated , is a conditional statement indicating what would be the case if its antecedent were true...
. The key to this solution is that, for any yes/no question Q, asking either True or False the question
- If I asked you Q, would you say ja?
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 (Rabern and Rabern (2008) call this result the embedded question lemma). The reason it works can be seen by looking at the eight possible cases.
- 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 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, then 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, then either B is Random (and is answering randomly), or B is not Random and the answer indicates that A is not Random. Either way, A 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 True?', would you say ja?". Since he is not Random, an answer of ja indicates that he is True and an answer of da 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 then B is Random; if the answer is da then the god you have not yet spoken to is Random. The remaining god can be identified by elimination.
Random's behavior
Most readers of the puzzle assume that Random will provide completely random answers to any question asked of him; however, Rabern and Rabern (2008) have pointed out that the puzzle does not actually state this. And in fact, Boolos' third clarifying remark explicitly refutes this assumption.- 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.
This says that Random randomly acts as a false-teller or a truth-teller, not that Random answers randomly.
A small change to the question above yields a question which will always elicit a meaningful answer from Random. The change is as follows:
- If I asked you Q in your current mental state, would you say ja?
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 simpler.
- Ask god A, "If I asked you 'Are you Random?' in your current mental state, would you say ja?"
- If A answers ja, then A is Random: Ask god B, "If I asked you 'Are you True?', would you say ja?"
- If B answers ja, then B is True and C is False.
- If B answers da, then B is False and C is True. In both cases, the puzzle is solved.
- If A answers da, then A is not Random: Ask god A, "If I asked you 'Are you True?', would you say ja?"
- If A answers ja, then A is True.
- If A answers da, then A is False.
- If A answers ja, then A is Random: Ask god B, "If I asked you 'Are you True?', would you say ja?"
- Ask god A, "If I asked you 'Is B Random?', would you say ja?"
- If A answers ja, then B is Random, and C is the opposite of A.
- If A answers da, then C is Random, and B is the opposite of A.
Rabern and Rabern (2008) 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:
- Whether Random says ja or da should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he says ja; if tails, he says da.
With this modification, the puzzle's solution demands the more careful god-interrogation given at the end of the The Solution section.
Unanswerable questions and exploding god-heads
In A simple solution to the hardest logic puzzle ever, B. Rabern and L. Rabern develop the puzzle further by pointing out that it is not the case that ja and da are the only possible answers a god can give. It is also possible for a god to be unable to 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. (The paper represents this as his head exploding, "...they are infallible gods! They have but one recourse – their heads explode.") Allowing the "exploding head" case gives yet another solution of the puzzle and introduces the possibility of solving the puzzle (modified and original) 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.- Three gods A, B, and C are called, in some order, Zephyr, Eurus, and Aeolus. The gods always speak truly. Your task is to determine the identities of A, B, and C by asking yes-no questions; each question must be put to exactly one god. The gods understand English and will answer in English.
Note that this puzzle is trivially solved with three questions. Furthermore, to solve the puzzle in two questions, the following lemma
Lemma (mathematics)
In mathematics, a lemma is a proven proposition which is used as a stepping stone to a larger result rather than as a statement in-and-of itself...
is proved.
- Tempered Liar Lemma. If we ask A "Is it the case that {[(you are going to answer 'no' to this question) AND (B is Zephyr)] OR (B is Eurus) }?", a response of 'yes' indicates that B is Eurus, a response of 'no' indicates that B is Aeolus, and an exploding head indicates that B is Zephyr. Hence we can determine the identity of B in one question.
Using this lemma it is simple to solve the puzzle in two questions. Rabern and Rabern (2008) use a similar trick (tempering the liar's paradox) to solve the original puzzle in just two questions. In "How to solve the hardest logic puzzle ever in two questions" G. 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.
- Would you answer the same as Random would to the question 'Is DushanbeDushanbe-Economy:Coal, lead, and arsenic are mined nearby in the cities of Nurek and Kulob allowing for the industrialization of Dushanbe. The Nurek Dam, the world's highest as of 2008, generates 95% of Tajikistan's electricity, and another dam, the Roghun Dam, is planned on the Vakhsh River...
in Kirghizia?'?
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 (2010) 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 (2008).
- Would you answer ja to the question of whether you would answer da to this question?
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 (2010) also uses this asymmetry to provide a two question solution to the modified puzzle.
See also
- George BoolosGeorge BoolosGeorge Stephen Boolos was a philosopher and a mathematical logician who taught at the Massachusetts Institute of Technology.- Life :...
- Raymond SmullyanRaymond SmullyanRaymond Merrill Smullyan is an American mathematician, concert pianist, logician, Taoist philosopher, and magician.Born in Far Rockaway, New York, his first career was stage magic. He then earned a BSc from the University of Chicago in 1955 and his Ph.D. from Princeton University in 1959...
- Knights and KnavesKnights and knavesKnights and Knaves is a type of logic puzzle devised by Raymond Smullyan.On a fictional island, all inhabitants are either knights, who always tell the truth, or knaves, who always lie. The puzzles involve a visitor to the island who meets small groups of inhabitants...
- Logic PuzzleLogic puzzleA logic puzzle is a puzzle deriving from the mathematics field of deduction.-History:The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of Alice's Adventures in Wonderland...
External links
- George Boolos. The hardest logic puzzle ever. The Harvard Review of Philosophy, 6:62–65, 1996.
- T.S. Roberts. Some thoughts about the hardest logic puzzle ever. Journal of Philosophical Logic, 30:609–612(4), December 2001.
- Brian Rabern and Landon Rabern. A simple solution to the hardest logic puzzle ever. Analysis 68 (298), 105–112, April 2008.
- Tom Ellis. Even harder than the hardest logic puzzle ever.
- Brian Rabern and Landon Rabern. In defense of the two question solution to the hardest logic puzzle ever.
- Gabriel Uzquiano. How to solve the hardest logic puzzle ever in two questions.
- Walter Carnielli. Contrafactuais, contradição e o enigma lógico mais difícil do mundo. Revista Omnia Lumina.