[HN Gopher] A brief meditation on formal systems and lying goblins
___________________________________________________________________
A brief meditation on formal systems and lying goblins
Author : mprast
Score : 58 points
Date : 2025-03-06 22:00 UTC (1 days ago)
(HTM) web link (the-nerve-blog.ghost.io)
(TXT) w3m dump (the-nerve-blog.ghost.io)
| thaumasiotes wrote:
| 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 wrote:
| _> "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 wrote:
| > 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 wrote:
| 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 wrote:
| 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.
| photonthug wrote:
| https://www.hillelwayne.com/post/knights-knaves/
| ziofill wrote:
| 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 wrote:
| > 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 wrote:
| "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_ wrote:
| * 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?
| ziofill wrote:
| 1. usually in these riddles the entities are oracles, so for
| simplicity let's say they are all-knowing goblins. 2. the
| coin flip is hidden from the player and it only influences
| the goblin being honest or a liar. the coin flipper goblin
| flips the coin _each time_ he 's asked a question. 3. see #1
| 4. each question is to be asked to a specific goblin chosen
| by the player, not to the group.
| cafeinux wrote:
| We can think of the goblins as functions that return either the
| truth, the inverse of the truth, or a random answer.
| // Knight, tells the truth K(a) { return a } //
| Knave, lies k(a) { return !a } // Joker, flips a
| coin J(a) { return random(true, false) }
|
| We can craft a question that will make the Knights and Knaves
| always return the truth. This could be "What would you answer
| if you were asked if $goblin is the $role?". This question will
| be noted Q(recipient,goblin,role), and here's what it returns
| depending if the recipient is a Knight, Knave or Joker.
| $goblin is $role | K | K(K) | k | k(k) | J | J(J) |
| T | T | T | F | T |T/F| T/F |
| F | F | F | T | F |T/F| T/F |
|
| If we didn't have the Joker and wanted to determine the two
| goblins roles, it would be as easy as asking this question to
| one of the two goblins.
|
| Now we add the Joker, but we also can ask two more questions.
| We need to use those two questions to determine who is the
| joker, so we can discard him and use our last question to
| discriminate the two remaining goblins.
|
| The 3 goblins will be noted G1, G2, and G3.
|
| Let's ask Q(G1,G2,J).
|
| Two possibilities:
|
| 1. The answer is "Yes" (true), either G1 is the Joker or G2 is
| the Joker. -> G3 is not the Joker.
|
| 2. The answer is "No" (false), either G1 is the Joker or G2 is
| not the Joker. -> G2 is not the Joker.
|
| Now that we know at least one goblin who is not the Joker
| (whether they are G2 or G3, I'll call them !J), we can ask them
| the question, this time about the first goblin. Q(!J,G1,J) 1.
| The answer is "Yes", G1 is the Joker, the other two are not. 2.
| The answer is "No", the remaining goblin is the Joker.
|
| I now know who is the Joker, meaning the other two goblins are
| either a Knight or a Knave.
|
| Ask Q(!J1,!J2,K) and you'll know who is the Knight and who is
| the Knave.
|
| In summary, the scenarios are as follows:
| Q1 | Q2 | Q3 | G1 | G2 | G3 |
| Q(G1,G2,J) | Q(G3,G1,J) | Q(G3,G2,K) | J | K | k |
| Q(G1,G2,J) | Q(G3,G1,J) | !Q(G3,G2,K) | J | k | K |
| Q(G1,G2,J) | !Q(G3,G1,J) | Q(G3,G1,K) | K | J | k |
| Q(G1,G2,J) | !Q(G3,G1,J) | !Q(G3,G1,K) | k | J | K |
| !Q(G1,G2,J) | Q(G2,G1,J) | Q(G2,G3,K) | J | k | K |
| !Q(G1,G2,J) | Q(G2,G1,J) | !Q(G2,G3,K) | J | K | k |
| !Q(G1,G2,J) | !Q(G2,G1,J) | Q(G2,G1,K) | K | k | J |
| !Q(G1,G2,J) | !Q(G2,G1,J) | !Q(G2,G1,K) | k | K | J |
|
| PS: If we assume that "What would you answer if you were asked
| if $goblin is the $role?" is forbidden because the Joker cannot
| know in advance what he would answer if they were asked if any
| goblin is any role, since it depends on their coin-flip,
| meaning that they wouldn't know what is the truth and what is
| the lie, and thus they cannot lie or tell the truth reliably,
| we can switch the question for "If you were asked if you were
| the truth-teller, or if you were asked if $goblin was the
| $role, would your answer to both questions be the same and
| always the same?".
| ziofill wrote:
| Here is my solution (surely not unique).
|
| The two questions to ask are "Are you the lying coin flipper?"
| and "Are you the honest coin flipper?". These are answered as
| (NO, YES, NO) and (NO, YES, YES), respectively, by the (honest,
| lying, coin flipper) goblins.
|
| In the best case we identify a non-flipper goblin on the first
| try (depending on which question we choose to ask) and then we
| can assign all three identities with just another question. In
| the worst case, we need to ask the same question to a second
| goblin in order to identify a non-flipper goblin, and then the
| other question to one of the two unidentified ones.
| schoen wrote:
| 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 wrote:
| A liar claiming he lies tells the truth?
| Terr_ wrote:
| 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 wrote:
| The always-truth one would surely just say they didn't know
| tomorrow's lottery number?
| SilasX wrote:
| 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.
| Terr_ wrote:
| > what about defining "lying" as "saying something that, if
| accepted, moves the believer away from the liar's
| worldmodel"?
|
| Then the definition becomes kinda-contradictory: The entity
| would _sometimes tell the truth_ , because that would be
| the best choice to divert and ruin your model.
|
| So "always lies in a simple way" would become more like
| "always unhelpful in a superintelligently evil way."
| schoen wrote:
| In Smullyan's formulation, the overall statement uttered by a
| liar must be logically false, even though it might contain
| conjuncts that are true, or might convey large amounts of
| useful and accurate information. For example, Smullyan would
| allow a liar to say "the sky is blue and cats are cute and
| 1+1=3".
|
| I might have phrased that confusingly when I said that they
| lie about everything in every statement. I should probably
| have said that they are never allowed to make any statement
| that they believe is true.
| JohnMakin wrote:
| > You can also assume that both goblins are telling the truth
| right up until the moment they stop explaining the rules.
|
| It says this in the very beginning.
| schoen wrote:
| I remembered that Smullyan usually handles this by having an
| outsider introduce the rules, rather than by having an
| islander (etc.) who is subject to the rules try to explain
| them.
|
| In the movie the goblins themselves are explaining their own
| behavior, which is not very helpful if you take them fully
| literally.
| evil_genius wrote:
| 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
| Godel's Theorems" that uses a twist with Knights and Knaves.
|
| https://www.goodreads.com/book/show/53232141-games-for-your-...
| KSteffensen wrote:
| My preferred solution to this logic problem:
|
| https://www.giantitp.com/comics/oots0327.html
| Jtsummers wrote:
| 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 wrote:
| 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 wrote:
| > 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.
___________________________________________________________________
(page generated 2025-03-07 23:02 UTC)