In 1992, the philosopher George Boolos gave what he called the “Hardest Logic Puzzle Ever”, which he attributed to Raymond Smullyan. In 2008, a clever paper by two graduate students, Brian Rabern and Landon Rabern, appeared in the philosophical journal “Analysis” which gave a simpler solution to the puzzle than Boolos gave—and furthermore claimed that a solution to a stronger puzzle was possible!
As its name implies, the “Hardest Logic Puzzle Ever” has a number of complicating factors which will be irrelevant for this discussion. Instead, consider the following much simpler puzzle which will do just as well.
You are on an island populated by knights and knaves. Knights always tell the truth; knaves always lie. You meet a inhabitant of the island who you know is holding up either 1, 2, or 3 fingers behind his back. You don’t know if this inhabitant is a knight or a knave. By asking two yes-or-no questions, determine how many fingers the inhabitant has behind his back.
There are a number of ways to solve this. One solution follows from the observation that, for any question Q, if you ask a inhabitant of the island
If I asked you question Q, would you say “yes”?
then you will get a truthful response to question Q. A knight will tell the truth about his truthful response to Q, whereas a knave would lie about his false response to Q.
So one solution would be to ask
If I asked you if you were holding 1 finger up, would you say “yes”?
If the inhabitant says “yes”, then you know he is holding 1 finger up. On the other hand, if the inhabitant says “no”, then you ask “If I asked you if you were holding 2 fingers up, would you say `yes’?” If the inhabitant says “yes”, then he is holding 2 fingers up, otherwise he is holding 3 fingers up.
This works, and it seems like you can’t do any better: There are three possibilities for how many fingers the inhabitant could be holding up, and since you can only ask yes-or-no questions, you couldn’t determine which of the three possibilities holds with only one question. But this is exactly what Rabern and Rabern claim you can do.
Consider what would happen if you asked a knight, “Will you answer `no’ to this question?”. If he is bound to answer the question, then he is in trouble, because no matter if he says “yes” or “no” he will have lied. Rabern and Rabern argue that in this sort of situation, the knight’s head would simply explode as there is nothing else he can do.
Assume that a inhabitant’s head explodes exactly when he cannot consistently answer “yes” or “no” to a question. Given this, we can solve the above problem by asking the single question. To make things simpler, suppose that we know that the inhabitant is a knight. Then we may ask:
Is it the case that you are holding up one finger or (you are holding up two fingers iff you will answer “no” this question)?
In this instance, if he answers “yes”, then he’s holding up one finger, if he answers “no”, he’s holding up three fingers, and if his head explodes, he was holding up two fingers.
I think Rabern and Rabern’s argument is really clever, but I don’t think it goes far enough. If we can observe inhabitants’ heads exploding and reason based on it, we should be able to ask inhabitants about it. Consider what would happen if we asked a knight:
Is it the case that you will answer “no” to this question and that your head will not blow up upon hearing this question?
If the knight’s head does not blow up upon hearing the question, then he can neither truthfully answer “yes” nor answer “no.” Therefore his head blows up. But if his head blows up only when he can’t answer a question, there’s a problem because given that his head blew up, he could have consistently answered “no” to the question.
So what happens? Well it must be the case that God’s (or whoever decides whether or not to blow up a head) head blows up because God won’t be able to decide whether or not the knight’s head should blow up. Similarly, if we suppose that SuperGod is in charge of deciding whether or not God’s head blows up, SuperGod’s head is in danger of blowing up due to a clever self-referential question, and so forth. So we may actually extract an unbounded amount of information from a single yes-or-no question by choosing the question carefully and then observing how much of the universe is destroyed by our asking it.
We can eliminate this silliness a bit by seeing how this applies to the usual Liar’s Paradox. The Liar’s Paradox is
This sentence is false.
(Or “This sentence is not true,” but the two will be equivalent for our purposes.) If it was true, then it would be false, and if it was false, then it would be true. Many people say that this sentence simply doesn’t have a well-defined truth value.
But consider this sentence, which I call the Second-Level Liar’s Paradox:
This sentence is false and it has a well-defined truth-value.
We can’t say that this sentence doesn’t have a well-defined truth-value, since if it doesn’t, then it is unproblematically false! Similarly, we can’t say that it has a well-defined truth value, since in that case it reduces to the Liar’s Paradox and can be neither true nor false. So, the Second-Level Liar’s Paradox has no well-defined (well-defined truth-value or not)-value.
Of course, we can iterate this. It seems that we should have at least the following truth values: true, false, paradoxical0, paradoxical1, paradoxical2, … and possibly more extending in to the ordinals depending on the expressive power of the language with respect to which sets of truth values it can refer to. (Here, a sentence is paradoxicali + 1 if it cannot consistently be paradoxicali.)
I’ve made a lot of assumptions here which I’m sure could be challenged about how we should reason in murky, paradoxical situations. One issue which I’m not quite sure how to resolve is the question of why, given that a sentence being false implies that it has a well-defined truth value, the Liar Paradox and Second Level Liar Paradox are not equivalent. But my guess would be that this can be made to give some sort of interesting paraconsistent logic, and probably some interesting puzzles as well.
XOR's Hammer 
This is fantastic. My favorite sentence is “If we can observe inhabitants’ heads exploding and reason based on it, we should be able to ask inhabitants about it.” and my favorite sentence fragment is “…by choosing the question carefully and then observing how much of the universe is destroyed by our asking it.”
Deduction by exploding heads — brilliant!
Nice! It looks like you are attempting to construct a question that has some kind of analogous relationship to a revenge liar. The key here is where you say “it is inconsistent that his head explodes”. You must be thinking, “Look, if he explodes, then the correct answer to the question is ‘no’ (it is not the case that his head failed to explode) and since he is a truth-teller, then he should answer ‘no’. So exploding is “inconsistent” with telling the truth.
The problem is that head explosion is not meant to be like a third truth-value. The head explodes when there is no other recourse. The way we were thinking of the procedure is something like this: If you ask him a yes-no question, then (i) he will say ‘yes’, if he can provide a truthful answer without contradicting himself and said truthful answer is ‘yes’, (ii) he will say ‘no’ if he can provide a truthful answer without contradicting himself and said truthful answer is ‘no’ (iii) and he will explode otherwise.
Thus, all insurmountable problems lead to head explosion; the knight reasons “if my head explodes, then I could have answered ‘no'”, and he continues “but if I answer ‘no’, then I lie, so that doesn’t work, I can’t answer ‘yes’, so I must explode, but then I could answer ‘no’, but nope that’s no good, …”, hence his head explodes. So if he gets stuck in a loop he cannot resolve, then he explodes regardless of how he got in the loop, by definition.
The important point is that the knight explodes instead of trying to save face by responding with ‘neuter’ or ‘gappy’. If ‘neuter’ is taken to mean “neither ‘yes’ or ‘no’ are the truthful answer”, then there is a revenge problem (just as you outline). Ask: “Will you answer this question by responding either ‘neuter’ or ‘no’?” He can’t respond ‘yes’, he can’t respond ‘no’ and he can’t respond ‘neuter’.
But exploding is understood to be different. It is like the knight replying “I cannot provide a truthful yes-no response without contradicting myself”. If we ask: “Will you answer this question by responding either ‘I cannot provide a truthful yes-no response’ or ‘no’?”. The knight will just say “I cannot provide a truthful yes-no response” (or he could just say “donkey!”). This doesn’t get him into trouble because he is not attempting to answer the question. He is just throwing up his hands, shrugging his shoulders, etc. We imagined the knight (or god in the original case) being very reluctant to give up; he would try so hard to provide a true yes-no answer that his head would explode. So if you ask him, “Are you going to answer ‘no’ to this question or explode when I pose it to you?”, he will just explode. But there is no revenge problem here (he couldn’t answer without contradicting himself, so boom!). When he explodes we might infer that the correct answer was ‘yes’. But just because that was the correct answer it doesn’t mean that the god could answer ‘yes’ truthfully.
I like the idea of adding super gods to the story such that we can get an unbounded amount of information from a single yes-or-no question by watching the world explode all around us. I am not sure exactly how it is supposed to work, though. You imagine an infinite chain reaction of explosions up the hierarchy. But why is it that the lower gods explode given that they are just waiting on word from the higher gods? Each god_i is waiting for god_{i+1} to instruct them; we will hear a great silence instead of a big boom (a clever way to distract the gods for eternity). In any case, the details need to be fleshed out.
It is an interesting question what the relationship between these self-referential questions, truth-telling gods and the semantic paradoxes are. Perhaps trying to solve the Liar paradox is like trying to figure out what the god should answer without being inconsistent. What answer should the god give? It seems that any attempt is open to a revenge problem. So the god just throws up his hands (or explodes). Does this suggest that if we are asked if the Liar sentence is true the best we can do is throw up our hands? I am not sure. Maybe this does suggest a kind of quietism. But I am not very satisfied with that […would a dialetheist god would respond “yes & no”?].
Thanks for the detailed reply Brian! I should have made it more clear that the “hierarchy-of-gods” that I was proposing wasn’t the only interpretation of the circumstances under which one’s head might explode, and that it was certainly different from the one you used in your paper.
Here’s a stab at a formulation of the “hierarchy-of-gods” interpretation: There are a chain of gods, god_0, god_1, … . The zeroth god, god_0, is asked a question (I’ll get to how to formalize the question in a moment.) For each god, there is a decision that that god might have to make. For god_0, the decision is whether to answer “yes” or “no” to the question. For i > 0, god_i’s decision is whether or not to absolve each god_j for j < i of the responsibility of making their decision. We also stipulate that each god is stingy with their absolutions, which is to say that, given what all the other gods have done, they only absolve the lower gods if there was nothing they could do that is, ultimately, consistent with giving a correct answer to the question.
Note that it may be the case that a god is absolved of the responsibility of making a decision, but makes one anyway.
Now to flesh it out a bit. Let
be propositional variables. The variable 
is intended to mean that god_0 replies “yes.” The variable 
is intended to mean that god_0 replies “no.” For 
, the variable 
is intended to mean that god_i does not absolve the lesser gods of their responsibilities. The variable 
is intended to mean that god_i does absolve the lesser gods of their responsibilities.
A question
will then be a finite propositional formula whose propositional variables are among the 
.
We call an assignment of truth values to the propositional variables a world.
In a given world, we say that the gods are law-abiding if for all
, if 
holds then for some 
, 
holds.
In a given world, we say that the gods act singly if for all
, 
holds.
In a given world, we say that god_0 acts acceptably if
and 
hold.
In a given world, we say that god_1 is stingy with his absolutions if the following holds: If
holds, then in the world that is the same as the current one except that 
is true, god_0 does not act acceptably (i.e., 
does not hold) and in the world that is the same as the current one except that 
is true, god_0 does not act acceptably (i.e., 
does hold).
For
, we say that god_i is stingy with absolutions if the following holds: If 
holds, then in the world that is the same as the current one except that 
is true, god_{i-1} is not stingy with absolutions and in the world that is the same as the current one except that 
is true, god_{i-1} is not stingy with absolutions.
Then, for a given question, we say that a solution to the question is one where the gods are law-abiding, act singly, where god_0 acts acceptably and the rest are all stingy with their absolutions.
I believe you can then prove existence of a solution for all questions. (I may have to tweak the definitions a bit; I’m not sure yet as I haven’t written this out formally.) The existence should follow from the naive algorithm: Start with no god being absolved of their responsibility, and work your way up. Each god tries his best and if he fails, the next god absolves him of his responsibility. Because the question might refer to that eventuality however, some lower god might now be able to succeed, in which case there may need to be more absolutions. If all else fails, the first god not mentioned in the question, which involves only finitely many gods, simply absolves all the gods mentioned of responsibility.
Of course, there is no uniqueness for solutions, since a question like “Will you answer ‘yes’ to this question?” may be asked.
As another note, hopefully it will be possible to adapt the hierarchy-of-gods interpretation (or one similar to it) to provability logic.
For example, you can adapt what I called the Second-Order Liar to a Second-Order Gödel Sentence: one whose decidability is undecidable: Given an arithmetical sentence
, let 
be the sentence asserting that 
is provable in PA (Peano Arithmetic).
Then, by diagonalization or fixed point or some such proposition, we know that there is a sentence
such that Peano Arithmetic proves that 
.
Now we would like to show that
is undecidable in PA.
First suppose that PA proves
. Then PA proves 
and thus 
. By the 
-consistency of PA and the proof of Gödel’s first incompleteness theorem, PA does not prove 
and does not prove 
. Now, using the fact that all statements provable in PA are actually true and the assumption that PA proves 
, we have a contradiction.
Now suppose that PA proves
. Then PA proves 
. So PA proves 
. So PA proves 
. So PA proves 
. On the other hand, since PA proves 
, PA proves 
. So PA is inconsistent.
It occurred to me that the fact that
is a sentence whose decidability is undecidable in PA is actually not at all remarkable: every sentence which is undecidable in PA is such that its decidability is undecidable in PA, since for PA to prove a sentence is undecidable in PA, it would have to prove that it can’t prove something, which is equivalent to it proving its consistency. So I will have to work a little harder to find a provability model of this.
Just stumbled on this webpage.
I thought the answer was to ask two questions to the Knight (or Knave) as follows:
“If I were to ask a member of the other tribe whether you were holding up one finger, what would his answer be?”
If the inhabitant is actually holding up one finger, whether he is a Knight or a Knave the answer will be “No”, and you will know that he is holding up one finger. If the inhabitant is holding up instead two (or three) fingers, the answer would be “Yes”.
If he does answer “Yes’ then you must ask a second question, “If I were to ask a member of the other tribe whether you were holding up two fingers, what would his answer be”
Once again, if the inhabitant answers “No”, he actually is holding up two fingers; if instead he answers “Yes” again, you can then deduce that he is holding up three fingers.
The point being that a Knight will always give the hypothetical Knave’s lying response, and the Knave will always reverse the hypothetical Knight’s truthful response.
No need for exploding heads.
TJ, that has the same effect as the first solution given – you can only ascertain the answer to one of the three options at a time. Thus, you may need to ask two questions to work out how many fingers are being held up.
But with the exploding heads approach you only ever need to ask *one* question.
http://www.srcf.ucam.org/~te233/maths/puzzles/evenharder.html
“So we may actually extract an unbounded amount of information from a single yes-or-no question by choosing the question carefully and then observing how much of the universe is destroyed by our asking it.”
LOL!!!
“”Consider what would happen if you asked a knight, “Will you answer `no’ to this question?”. If he is bound to answer the question, then he is in trouble, because no matter if he says “yes” or “no” he will have lied.””
This is not correct because you are only asking what his response to the question is. Assume the knight is holding up 1 finger and you ask “Will you answer ‘no’ if I ask you if you are holding one finger up?”
His response to THAT question would be “No(I will answer ‘yes'(when you ask that question))” and he would not have lied.
Ask the knight “Will you answer ‘no’ if I ask you if you are holding two fingers up?” he would respond “Yes(I WILL say ‘no’ (when you ask THAT question))”
By asking “What will your response to Q be?”, you are asking only that, and not question Q itself
If a question is asked that leads to a contradiction if a knave is being asked it, the probability that the inhabitant is a knave becomes 0 and two questions are required, as usual. Are there any questions which lead to a contradiction when asked to a knight and when asked to a knave?