5 ms·

A brief meditation on formal systems and lying goblins

64 points by mprast 2y ago

thaumasiotes 2y ago
I see this problem differently, as mainly exhibiting a problem that cannot be analyzed without self-reference. Self-reference causes problems. The more obvious solution that the postscript hints at is the question "what would you say if I asked you whether [this door] leads to the castle?". Here, we immediately cancel out the influence of whatever goblin we're speaking to, and we get the right answer, whereas in the movie's solution we immediately incorporate the influence of the lying goblin and get the wrong answer. But the movie's solution is better for the movie, because "what would you say if I asked you X?" is a normal English way to ask "X", and in this case, where the two questions are different, the audience is guaranteed to be confused.
- munificent 2y ago
  > "what would you say if I asked you whether [this door] leads to the castle?". Very clever. If the goblin is lying, the double negation cancels out. If the goblin is telling the truth, the truth remains unchanged. Personally, I didn't find the article very clarifying. Instead, I like to think of the goblins A and B as functions that take in the truth value of a statement and output an answer. One goblin's function yields the boolean not of the result, and the other passes it through unchanged. You don't know which goblin has which functions, so the two ways to get a reliable answer out are: A(A(question)) A(B(question)) The former is your answer here, which does the double negation. The latter is the answer in the movie where you pass it through both goblins which means the answer will reliably have its truth value flipped exactly once. The nice thing about the latter solution is that it scales up to more goblins and an arbitrary ratio of liars. Let's say there are four goblins, Ann, Ben, Cat, and Dan. Two always lie and two always tell the truth. You can ask "Would Ann say that Ben would say that Cat would say that Dan would say that door 1 leads to the castle?" In other words: A(B(C(D(question)))) In this case, the answer tells you if door 1 is correct because there are an even number of liars so the negations cancel out. If the number of liars is odd, you flip the result.
  - thaumasiotes 2y ago
    > The nice thing about the latter solution is that it scales up to more goblins and an arbitrary ratio of liars. Let's say there are four goblins, Ann, Ben, Cat, and Dan. Two always lie and two always tell the truth. You can ask "Would Ann say that Ben would say that Cat would say that Dan would say that door 1 leads to the castle?" > In this case, the answer tells you if door 1 is correct because there are an even number of liars so the negations cancel out. If the number of liars is odd, you flip the result. That's worse scaling than the alternative approach, not better scaling. You need to increase the size of your question every time the number of goblins increases. But "what would you say if I asked you whether [this door] leads to the castle?" shows perfect scaling; it works without changes no matter how many goblins there are. It also isn't necessary to know how many of the goblins are liars.
    - munificent 2y ago
      Good point! I was thinking that if there are multiple goblins, asking a question that only relates to one of them doesn't give you enough information to determine which goblins are liars. But you don't actually need to know that. You just need the truth value of the final answer.
      - thaumasiotes 2y ago
        I should point out that your all-inclusive question also doesn't give you enough information to determine which goblins are liars. In the general case that will always require one question per goblin, plus one more if you also care about the doors.
- deleted 2y ago
  [deleted]
photonthug 2y ago
https://www.hillelwayne.com/post/knights-knaves/ https://www.hillelwayne.com/post/knights-knaves/
ziofill 2y ago
There is another version of this puzzle with a third goblin who flips a coin and depending on the outcome he will lie or tell the truth. The player is allowed 3 yes/no questions and the objective is to assign the three identities unambiguously. I can post the solution in 24h. Have fun! ^^
- thaumasiotes 2y ago
  > There is another version of this puzzle with a third goblin who flips a coin and depending on the outcome he will lie or tell the truth. The player is allowed 3 yes/no questions But this won't work in the context of the puzzle as stated. The puzzle here requires you to ask about what a goblin will say; your puzzle can't allow that because such a question cannot in the general case be answered yes/no.
- Jiro 2y ago
  "If I asked the other two goblins if you are the truthteller and they both gave the same answer, what would that answer be?" If you are talking to the truthteller, the answer is no. If you are talking to the liar, the answer is yes. If you are talking to the coin flipper, he cannot answer because it is not possible for the other two to give the same answer. This or similar was the solution, but I don't believe the solution works. A false proposition implies any proposition--"if (impossible scenario) then what would someone say" can be truthfully answered with either yes or no.
- Terr_ 2y ago
  * Do all goblins know all their roles, or is each one not sure about the other two? (Unlike the two-goblin version, they can't figure it out by the process of elimination.) * Is the coin-flip outcome hidden, or can the player learn a correlation between heads/tails and different reactions? Is the coin flip itself hidden, or are the other two flipping simultaneous decoy coins? * Are the truth/falsehood goblins aware of the outcome of the coin flip? If they are unaware, what rule governs their behavior towards that ambiguity? Can the liar tell the truth by accident? * Are the three questions posed to the group simultaneously, or do you have to target your question to a specific goblin for a single boolean result?
fsfsdfads 2y ago
[dead]
schoen 2y ago
An oddity here (that I think Smullyan is often careful about when introducing his knight and knave puzzles) is that the goblins in the story appeared to agree with each other about the surrounding context (that there is one liar and one truthteller, that there is one door that should be taken, etc.). They didn't contradict each other about that! Smullyan's liars normally lie about everything in every statement, so an official Smullyan liar would not agree that there is one liar and one truthteller, that there is one safe door and one unsafe door, and so on. I just watched the original scene, and the two goblins seem to agree with each other about all of that stuff! How confusing.
- DeathArrow 2y ago
  A liar claiming he lies tells the truth?
- Terr_ 2y ago
  Similarly, can the always-liar state that "I have a penny, it is in my left pocket", when the reality is that it's a penny in the right pocket, or a quarter in the left pocket? Who decides which clauses or aspects are separable? For that matter, if either of them are perfect at their jobs, they are oracles, and could retire by attempting to say something about out the first, second, third, etc. digit of tomorrow's winning lottery number. If they're imperfect at their jobs, then they aren't actually "always" anything.
  - robertlagrant 2y ago
    The always-truth one would surely just say they didn't know tomorrow's lottery number?
  - SilasX 2y ago
    Stupid question: what about defining "lying" as "saying something that, if accepted, moves the believer away from the liar's worldmodel"? (Which I think matches general intuition.) Then you do get information once you know someone always lies (and has a correct worldmodel) because you know to update the opposite direction. I don't know the impact on these puzzles.
fdafdsa 2y ago
[dead]
evil_genius 2y ago
If you find logic puzzles interesting, take a look at "Games for Your Mind: The History and Future of Logic Puzzles" by Jason Rosenhouse. There's a whole chapter on Smullyan and his Knights and Knaves problems and is a generally good guide for getting into formal logic. The part I enjoyed the most in the book was "The Empuzzlement of Gödel's Theorems" that uses a twist with Knights and Knaves. https://www.goodreads.com/book/show/53232141-games-for-your-mind https://www.goodreads.com/book/show/53232141-games-for-your-...
KSteffensen 2y ago
My preferred solution to this logic problem: https://www.giantitp.com/comics/oots0327.html https://www.giantitp.com/comics/oots0327.html
deleted 2y ago
[deleted]
Jtsummers 2y ago
In some of the Smullyan books he extends the knights and knaves puzzles to incorporate beliefs with sane and insane variants. This is common in his Transylvania puzzles, where vampires always lie, humans always tell the truth, the sane believe true things, and the insane believe false things. The sane human and insane vampire always tell the truth, even though it's not the vampire's intent to tell the truth. Meanwhile, the insane human always makes false statements though their intent is to tell the truth (and they do, they tell you what they believe to be true).
- schoen 2y ago
  One cute thing there is that the insane people (and vampires) have immediately inconsistent beliefs. For example, they believe "the sky is red", "the sky is yellow", "the sky is green"... Also, they believe "I am sane" but also "I am insane and 1+1=3". (Or "George Washington is dead" but also "George Washington is still alive and 1+1=3".) I don't think Smullyan ever had the insane people try to reason from their infinite store of false beliefs (as opposed to just knowing individual isolated false assertions). That could have made the puzzles much more confusing because they might conclude true beliefs as well as false ones, although maybe they also always get immediately confused about the results of their reasoning process and invert it? Like, insane humans in the Transylvania puzzles believe "I am sane" but they also believe "I am insane and 1+1=3"; if they could perform the valid logical inference from the conjunct they could also then conclude "I am insane" alongside "I am sane". This would make the puzzles less interesting, because then insane humans could assert anything!
  - thaumasiotes 2y ago
    > if they could perform the valid logical inference from the conjunct they could also then conclude "I am insane" alongside "I am sane". They can conclude that directly; "I am insane and I am sane" is another false belief that they already have.

64 points by mprast 2y ago

I see this problem differently, as mainly exhibiting a problem that cannot be analyzed without self-reference. Self-reference causes problems. The more obvious solution that the postscript hints at is the question "what would you say if I asked you whether [this door] leads to the castle?". Here, we immediately cancel out the influence of whatever goblin we're speaking to, and we get the right answer, whereas in the movie's solution we immediately incorporate the influence of the lying goblin and get the wrong answer. But the movie's solution is better for the movie, because "what would you say if I asked you X?" is a normal English way to ask "X", and in this case, where the two questions are different, the audience is guaranteed to be confused.

munificent 2y ago
> "what would you say if I asked you whether [this door] leads to the castle?". Very clever. If the goblin is lying, the double negation cancels out. If the goblin is telling the truth, the truth remains unchanged. Personally, I didn't find the article very clarifying. Instead, I like to think of the goblins A and B as functions that take in the truth value of a statement and output an answer. One goblin's function yields the boolean not of the result, and the other passes it through unchanged. You don't know which goblin has which functions, so the two ways to get a reliable answer out are: A(A(question)) A(B(question)) The former is your answer here, which does the double negation. The latter is the answer in the movie where you pass it through both goblins which means the answer will reliably have its truth value flipped exactly once. The nice thing about the latter solution is that it scales up to more goblins and an arbitrary ratio of liars. Let's say there are four goblins, Ann, Ben, Cat, and Dan. Two always lie and two always tell the truth. You can ask "Would Ann say that Ben would say that Cat would say that Dan would say that door 1 leads to the castle?" In other words: A(B(C(D(question)))) In this case, the answer tells you if door 1 is correct because there are an even number of liars so the negations cancel out. If the number of liars is odd, you flip the result.
- thaumasiotes 2y ago
  > The nice thing about the latter solution is that it scales up to more goblins and an arbitrary ratio of liars. Let's say there are four goblins, Ann, Ben, Cat, and Dan. Two always lie and two always tell the truth. You can ask "Would Ann say that Ben would say that Cat would say that Dan would say that door 1 leads to the castle?" > In this case, the answer tells you if door 1 is correct because there are an even number of liars so the negations cancel out. If the number of liars is odd, you flip the result. That's worse scaling than the alternative approach, not better scaling. You need to increase the size of your question every time the number of goblins increases. But "what would you say if I asked you whether [this door] leads to the castle?" shows perfect scaling; it works without changes no matter how many goblins there are. It also isn't necessary to know how many of the goblins are liars.
  - munificent 2y ago
    Good point! I was thinking that if there are multiple goblins, asking a question that only relates to one of them doesn't give you enough information to determine which goblins are liars. But you don't actually need to know that. You just need the truth value of the final answer.
    - thaumasiotes 2y ago
      I should point out that your all-inclusive question also doesn't give you enough information to determine which goblins are liars. In the general case that will always require one question per goblin, plus one more if you also care about the doors.
deleted 2y ago
[deleted]

photonthug 2y ago

https://www.hillelwayne.com/post/knights-knaves/ https://www.hillelwayne.com/post/knights-knaves/

ziofill 2y ago

There is another version of this puzzle with a third goblin who flips a coin and depending on the outcome he will lie or tell the truth. The player is allowed 3 yes/no questions and the objective is to assign the three identities unambiguously. I can post the solution in 24h. Have fun! ^^

thaumasiotes 2y ago
> There is another version of this puzzle with a third goblin who flips a coin and depending on the outcome he will lie or tell the truth. The player is allowed 3 yes/no questions But this won't work in the context of the puzzle as stated. The puzzle here requires you to ask about what a goblin will say; your puzzle can't allow that because such a question cannot in the general case be answered yes/no.
Jiro 2y ago
"If I asked the other two goblins if you are the truthteller and they both gave the same answer, what would that answer be?" If you are talking to the truthteller, the answer is no. If you are talking to the liar, the answer is yes. If you are talking to the coin flipper, he cannot answer because it is not possible for the other two to give the same answer. This or similar was the solution, but I don't believe the solution works. A false proposition implies any proposition--"if (impossible scenario) then what would someone say" can be truthfully answered with either yes or no.
Terr_ 2y ago
* Do all goblins know all their roles, or is each one not sure about the other two? (Unlike the two-goblin version, they can't figure it out by the process of elimination.) * Is the coin-flip outcome hidden, or can the player learn a correlation between heads/tails and different reactions? Is the coin flip itself hidden, or are the other two flipping simultaneous decoy coins? * Are the truth/falsehood goblins aware of the outcome of the coin flip? If they are unaware, what rule governs their behavior towards that ambiguity? Can the liar tell the truth by accident? * Are the three questions posed to the group simultaneously, or do you have to target your question to a specific goblin for a single boolean result?

fsfsdfads 2y ago

[dead]

schoen 2y ago

An oddity here (that I think Smullyan is often careful about when introducing his knight and knave puzzles) is that the goblins in the story appeared to agree with each other about the surrounding context (that there is one liar and one truthteller, that there is one door that should be taken, etc.). They didn't contradict each other about that! Smullyan's liars normally lie about everything in every statement, so an official Smullyan liar would not agree that there is one liar and one truthteller, that there is one safe door and one unsafe door, and so on. I just watched the original scene, and the two goblins seem to agree with each other about all of that stuff! How confusing.

DeathArrow 2y ago
A liar claiming he lies tells the truth?
Terr_ 2y ago
Similarly, can the always-liar state that "I have a penny, it is in my left pocket", when the reality is that it's a penny in the right pocket, or a quarter in the left pocket? Who decides which clauses or aspects are separable? For that matter, if either of them are perfect at their jobs, they are oracles, and could retire by attempting to say something about out the first, second, third, etc. digit of tomorrow's winning lottery number. If they're imperfect at their jobs, then they aren't actually "always" anything.
- robertlagrant 2y ago
  The always-truth one would surely just say they didn't know tomorrow's lottery number?
- SilasX 2y ago
  Stupid question: what about defining "lying" as "saying something that, if accepted, moves the believer away from the liar's worldmodel"? (Which I think matches general intuition.) Then you do get information once you know someone always lies (and has a correct worldmodel) because you know to update the opposite direction. I don't know the impact on these puzzles.

fdafdsa 2y ago

[dead]

evil_genius 2y ago

If you find logic puzzles interesting, take a look at "Games for Your Mind: The History and Future of Logic Puzzles" by Jason Rosenhouse. There's a whole chapter on Smullyan and his Knights and Knaves problems and is a generally good guide for getting into formal logic. The part I enjoyed the most in the book was "The Empuzzlement of Gödel's Theorems" that uses a twist with Knights and Knaves. https://www.goodreads.com/book/show/53232141-games-for-your-mind https://www.goodreads.com/book/show/53232141-games-for-your-...

KSteffensen 2y ago

My preferred solution to this logic problem: https://www.giantitp.com/comics/oots0327.html https://www.giantitp.com/comics/oots0327.html

deleted 2y ago

[deleted]

Jtsummers 2y ago

In some of the Smullyan books he extends the knights and knaves puzzles to incorporate beliefs with sane and insane variants. This is common in his Transylvania puzzles, where vampires always lie, humans always tell the truth, the sane believe true things, and the insane believe false things. The sane human and insane vampire always tell the truth, even though it's not the vampire's intent to tell the truth. Meanwhile, the insane human always makes false statements though their intent is to tell the truth (and they do, they tell you what they believe to be true).

schoen 2y ago
One cute thing there is that the insane people (and vampires) have immediately inconsistent beliefs. For example, they believe "the sky is red", "the sky is yellow", "the sky is green"... Also, they believe "I am sane" but also "I am insane and 1+1=3". (Or "George Washington is dead" but also "George Washington is still alive and 1+1=3".) I don't think Smullyan ever had the insane people try to reason from their infinite store of false beliefs (as opposed to just knowing individual isolated false assertions). That could have made the puzzles much more confusing because they might conclude true beliefs as well as false ones, although maybe they also always get immediately confused about the results of their reasoning process and invert it? Like, insane humans in the Transylvania puzzles believe "I am sane" but they also believe "I am insane and 1+1=3"; if they could perform the valid logical inference from the conjunct they could also then conclude "I am insane" alongside "I am sane". This would make the puzzles less interesting, because then insane humans could assert anything!
- thaumasiotes 2y ago
  > if they could perform the valid logical inference from the conjunct they could also then conclude "I am insane" alongside "I am sane". They can conclude that directly; "I am insane and I am sane" is another false belief that they already have.