6 ms·
The Hardest Logic Puzzle: A step-by-step guide to true, false, and random
- Rangi42 11y agoSam Hughes implemented this puzzle in Javascript to demonstrate how the solution works, and why some other proposed ones don't: http://qntm.org/gods http://qntm.org/gods
- aidenn0 11y agoNot impossible but makes it slightly harder to do IFF and "is exactly one of these true" I had formulated my yes/no questions when I worked through this as "Is exactly one of these true: Ja means yes, X" Which makes Da yes and Ja no.
- deleted 11y ago[deleted]
- IIAOPSW 11y agoI thought you had to ask exactly one question to each god. This solution uses god B twice.
- FLengyel 11y agoI heard that Norman Steenrod was pacing back and forth in Fine Hall thinking about this puzzle, until he solved it. This was before it was attributed to Boolos, according to my sources. The author might have been Mark Kac, or it might have been communicated to Steenrod through Mark Kac, I was told.
- jsprogrammer 11y agoThe article presents a good technique for handling situations, but I can't help but feel the solution breaks a rule. You are supposed to only be able to ask a single question to each god, but a biconditional question is really two different questions. You can see this simply from the structure of the English question (as well as in the conversion to NAND logic): > “Does ‘da’ mean ‘yes’ if and only if you are True and if and only if B is Random?”
- dullcrisp 11y agoHow would you feel about the more conversational, "If I asked you if B were Random, would you say da?"
- jsprogrammer 11y agoIt's definitely better and much more subtle. Whether or not it is technically two questions per the description of the problem...I'm not sure :)
- masterzora 11y agoWhile you can construct the answer to "Does 'da' mean 'yes' if and only if you are True?" from "Does 'da' mean 'yes' if you are True" and "Does 'da' mean 'yes' only if you are True", you cannot construct the answers to "Does 'da' mean 'yes' if you are True" and "Does 'da' mean 'yes' only if you are True" from "Does 'da' mean 'yes' if and only if you are True?" alone. Note, in particular, that at the end of the three questions in the solution you still have no way of discerning whether 'da' does, in fact, mean 'yes'.
- jsprogrammer 11y agoI'm not arguing that there is a solution that meets all of the constraints of the problem, just that this particular solution does not seem to meet the constraints described.
- masterzora 11y ago
- throwaway000002 11y agoThis is an aside, but somewhat similar in spirit. In high school, ages ago, I remember discussing the following problem and never being satisfied with the solution. If someone could clarify the exact wording and source of the problem I'd appreciate it. What I loosely remember is as follows. A teacher tells her students on a Friday that they are to have a test next week. However, she adds, they won't know the day before that they're going to have a test on the following day. The students, being somewhat savvy, deduce that if it transpires that they don't get tested by the end of the following Thursday then they'd have to be tested on Friday, which would mean that they know this beforehand, so the test cannot possibly be on Friday. And so, inductively, cannot be on Thursday, and so on. This "logic" is very unsatisfying, so I need to find out what the actual form and solution of the problem is. This has bugged me for decades.
- thrwwy77911234 11y agohttps://en.m.wikipedia.org/wiki/Unexpected_hanging_paradox https://en.m.wikipedia.org/wiki/Unexpected_hanging_paradox
- throwaway000002 11y agoThanks oh so very much! :)
- PeterWhittaker 11y agoAnd read this, too: http://www.ams.org/notices/201011/rtx101101454p.pdf http://www.ams.org/notices/201011/rtx101101454p.pdf
- throwaway000002 11y agoWow Peter, thanks for that. I like their analysis. It reminded me of a great article I read years ago that dealt with the issue of self-referential paradox. In fact, at the time I tried applying the techniques therein towards the surprise examination, however I didn't get anywhere. It's a paper by Noson Yanofsky entitled "A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points" (http://arxiv.org/abs/math/0305282 http://arxiv.org/abs/math/0305282) I think you'll enjoy reading it. I read the paper on a long train ride loved working out how given "Ann believes that Bob believes that Ann believes that Bob has a false belief about Ann" asking "does Ann believe that Bob has a false belief about Ann?" results in a paradox. This is supposedly called Brandenburger’s Epistemic Paradox. Anyway, thanks again for your reference.
- n0us 11y agoThe trick resides in how you can ask questions like "if and only if" which in my opinion are really multiple questions masked as one. For example you can formulate iff as "(not q or p) and (not p or q)" where the "not" refers only to the term directly to its right. This is far from a simple assertion like "is it true that if the earth is round then I am a knight?" because you are also asking "is it true that if I am a knight then the earth is round" and thus get the chance to ask two questions in one. It's certainly still a tricky puzzle but you would need to understand the rules on what kinds of questions you are allowed to ask before starting
- shasta 11y agoAsking compound questions isn't the same as asking multiple questions because you can only ever get one bit of information out of each question.
- n0us 11y agoNot exactly because you can combine as many questions as you like and get an answer about whether one of them or all of them is correct, furthermore if you can ask question in first order logic, like "for all x is y true?" as opposed to just "if x then y?" The wording would be come awkward very quickly but you can gain an almost unlimited amount of information from compound questions. I wouldn't be surprised if there were a solution to this problem involving only two questions or even one, though at the moment I don't have the time to work through it so don't take my word for it. In binary terms, let's say you have one bit, 0 or 1 that represents a single propositional statement, "x or y" or "x and y" but with compound questions you can get as many bits as you want "(x or y) and (x and y) and (p and q)" so you can only ever get the truth value of the entire compound statement but you get far more than a single truth value
- shasta 11y agoIf you take an information theory point of view, then a single question could provide more than a single bit of information, but it never will on average (for some suitable meaning of "average"). If I'm speaking to 1 of 1024 possible people and I ask "Are this particular woman?" then 1 time out of 1024 I will learn 10 bits of information, but 1023 out of 1024 times I will learn approximately zero bits of information.
- dkarapetyan 11y agoThe article mentions law of excluded middle which doesn't hold in constructive logic so I wonder what exactly happens in the constructive setting.
- masterzora 11y agoWell, the part where it directly mentions excluded middle is the part where it cites Boolos commenting on just that.
- dkarapetyan 11y agoThat's not what I mean. What is the analog of the hardest puzzle in the constructive setting.
- 885895 11y ago>Suppose that you can’t remember whether Pluto is a dwarf planet, and you need to find out by asking someone nearby—but you don’t know whether that person is a knight or a knave. What’s the one yes-no question you can ask to figure out whether Pluto is a dwarf planet? >"Are you a knight if and only if Pluto is a dwarf planet?" >If the person’s a knight and Pluto is a dwarf planet, then you get the answer “yes,” since both statements on each side of if and only if are true, and knights always speak truly. I don't get how this follows. Surely, the person being a knight or a knave is independent from whether or not Pluto is a dwarf planet so a real knight would say "no" either way since the assumption is bad and a knave would thus say "yes". Thereby, you have not determined whether or not Pluto is a dwarf planet but instead whether the person is a knight or a knave. Please explain my error.
- tromp 11y agoThere is no assumption. There is just "A if-and-only-if B" where A and B are both true and therefore by definition the whole statement is true.
- fineman 11y ago"If and only if" sounds strange to me too. Like asking if he's a knight when Pluto is a dwarf planet. And on second reading it looks like an awkward way to say And... I think "Is one and only one of [A, B] true?" would be better. Or, (A ^ B).
- anon4 11y agoIt's easier if you see it as logical operations, rather than language. A iff B has the same meaning as A == B, but with the added twist that !B negates the answer in the example (knaves always lie). So let's take A = Pluto is a dwarf planet; B = you're a knight, then "are you a knight if and only if Pluto is a dwarf planet" has the formula (B && (A == B)) || !(!B && (A == B)), which after a bit of simplifying you can see is the same as A == True || !(A == False), or A == True. Very often logic formulas, when translated in English, sound absolutely bonkers, not least because the words if, and, or have pretty loose meanings in ordinary language.