Lurker, but I just had to post here. A version of this was posted on The Big Questions in July. Here is my answer, pasted from there (but modified to use the different names), which beats the given answer because it uses two questions.
Let Y be “is the answer to X ‘da’”. If they respond ‘da’, that’s equivalent to saying ‘yes’ to X, and if they respond ‘ja’, that’s the equivalent of saying ‘no’ to X. This is the case even if they said ‘yes’ or ‘no’ because they lied.
“Tell me whether the correct answer to Y is the truthfulness of your answer to this question” will produce the answer to Y from anyone (True, False, or Random). You can ask it three times (with X being various ‘are you a ___’) and get correct yes/no answers all three times, which is enough to tell 6 combinations apart.
If you want to do better than that you need more than one bit per answer, which is possible by asking a question that Random cannot answer with either a yes or a no. Use a disjunction. “Tell me, in the case that you are not Random, whether the correct answer to Y is the truthfulness of your answer to this question, and in the case that you are Random, whether your answer to this question is the negation of the truthfulness of your answer to this question” will get an answer to Y from True or False, and no answer from Random. If X is ‘are you True’ and Y is the da version from above, then the entire question will be answered ‘da’ by True, ‘ja’ by False, and not at all by Random. This provides an obvious way to do it in 2 questions.
(break for formatting)
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.
Random will answer da or ja when asked any yes-no question.
These two are not equivalent. The first of these allows you to exploit the fact that some yes-no questions cannot be answered truthfully or falsely, allowing the answer above. The second does not, and implies that some answers from Random are neither true nor false.
your two-question solution doesn’t work given the constraints imposed by Boolos
If the above is quoted correctly, the constraints imposed by Boolos are contradictory. It is not possible that 1) Random always answers truthfully or falsely and 2) Random always answers “da” or “ja”. So the fact that I had to throw out the latter constraint is of no import—since the constraints are contradictory, I had no choice but to throw one out.
Well, you don’t have to throw one out. You could interpret the constraints (which are quoted correctly, btw) as narrowing the set of legitimate questions to those which Random can answer both truthfully and falsely with “da” or “ja”. I’m not sure why Boolos would have that constraint in there unless it was to rule out the kind of solution you’re proposing. Still, I agree the problem is clumsily phrased.
Maybe the question could be patched by adding the possibility that the gods (including Random) don’t respond at all, but also changing Random’s behavior from “randomly answers truthfully or falsely” to “randomly says either ‘da’, ‘ja’ or nothing”. If you patch it in this way, I’m pretty sure a two-question solution isn’t possible.
ETA: Also, I don’t want to downplay the cleverness of your two-question solution. Whether or not it perfectly fulfills the constraints of the problem, it is still very nice.
The patched version requires three questions. In fact it requires asking three people—if you only ask two people any number of questions, Random could pretend that he is the other person and the other person is Random.
First of all, you need a question which lets you determine who any person B is, when asked of Truth.
You want to ask “if B is Truth, then yes, else if B is False, then no, else don’t answer”. Presumably, you can’t directly ask someone not to answer—they can only refuse to answer if they are Random or if yes/no would violate constraints, so this comes out to “if B is Truth, then yes, else if B is False, then no, else tell me if your answer to this question is ‘no’.”
Then you modify this question so that it can be asked either of Truth or False. As before, adding “tell me if the answer to Y is the truthfulness of your answer to this question” will produce a correct answer to a yes/no question from either True or False, so you get “tell me, in the case that B is not Random, if the answer to “if B is Truth, then yes, else no” is the truthfulness of the answer to your question, and in the case that B is Random, if your answer to this question is the negation of the truthfulness of your answer to this question’”.
You now have a question that can determine who one person is, when asked of either True or False.
(The version with da and ja is left as an exercise to the reader.)
Use that question to ask person 1 who person 3 is. Then use it to ask person 2 who person 3 is.
If 1 and 2 give the same answer, then they are either Truth or False giving an informative answer or Random imitating an informative answer. Either way you know the identity of 3, and you also know one non-Random person. Ask this non-Random person the question to find the identity of a second person, which gives you all three.
If 1 and 2 give different answers, then one of them is Random. In that case, you know that 3 is not Random, and you can ask 3 who 1 is. You now know the identity of 1, and you know whether 1 or 2 is Random; the non-Random one told you who 3 was, so you have the identity of 3 as well. This again gives you the identity of two people and so you have all three.
Lurker, but I just had to post here. A version of this was posted on The Big Questions in July. Here is my answer, pasted from there (but modified to use the different names), which beats the given answer because it uses two questions.
(break for formatting)
These two are not equivalent. The first of these allows you to exploit the fact that some yes-no questions cannot be answered truthfully or falsely, allowing the answer above. The second does not, and implies that some answers from Random are neither true nor false.
Nice! Although, as you mention, your two-question solution doesn’t work given the constraints imposed by Boolos (or Smullyan). Still, very clever.
If the above is quoted correctly, the constraints imposed by Boolos are contradictory. It is not possible that 1) Random always answers truthfully or falsely and 2) Random always answers “da” or “ja”. So the fact that I had to throw out the latter constraint is of no import—since the constraints are contradictory, I had no choice but to throw one out.
Well, you don’t have to throw one out. You could interpret the constraints (which are quoted correctly, btw) as narrowing the set of legitimate questions to those which Random can answer both truthfully and falsely with “da” or “ja”. I’m not sure why Boolos would have that constraint in there unless it was to rule out the kind of solution you’re proposing. Still, I agree the problem is clumsily phrased.
Maybe the question could be patched by adding the possibility that the gods (including Random) don’t respond at all, but also changing Random’s behavior from “randomly answers truthfully or falsely” to “randomly says either ‘da’, ‘ja’ or nothing”. If you patch it in this way, I’m pretty sure a two-question solution isn’t possible.
ETA: Also, I don’t want to downplay the cleverness of your two-question solution. Whether or not it perfectly fulfills the constraints of the problem, it is still very nice.
The patched version requires three questions. In fact it requires asking three people—if you only ask two people any number of questions, Random could pretend that he is the other person and the other person is Random.
First of all, you need a question which lets you determine who any person B is, when asked of Truth.
You want to ask “if B is Truth, then yes, else if B is False, then no, else don’t answer”. Presumably, you can’t directly ask someone not to answer—they can only refuse to answer if they are Random or if yes/no would violate constraints, so this comes out to “if B is Truth, then yes, else if B is False, then no, else tell me if your answer to this question is ‘no’.”
Then you modify this question so that it can be asked either of Truth or False. As before, adding “tell me if the answer to Y is the truthfulness of your answer to this question” will produce a correct answer to a yes/no question from either True or False, so you get “tell me, in the case that B is not Random, if the answer to “if B is Truth, then yes, else no” is the truthfulness of the answer to your question, and in the case that B is Random, if your answer to this question is the negation of the truthfulness of your answer to this question’”.
You now have a question that can determine who one person is, when asked of either True or False.
(The version with da and ja is left as an exercise to the reader.)
Use that question to ask person 1 who person 3 is. Then use it to ask person 2 who person 3 is.
If 1 and 2 give the same answer, then they are either Truth or False giving an informative answer or Random imitating an informative answer. Either way you know the identity of 3, and you also know one non-Random person. Ask this non-Random person the question to find the identity of a second person, which gives you all three.
If 1 and 2 give different answers, then one of them is Random. In that case, you know that 3 is not Random, and you can ask 3 who 1 is. You now know the identity of 1, and you know whether 1 or 2 is Random; the non-Random one told you who 3 was, so you have the identity of 3 as well. This again gives you the identity of two people and so you have all three.