23
$\begingroup$

On the island of Knights and Knaves, knights can only say true sentences and knaves can only say false sentences. This makes day-to-day life awful, since nobody can truly lie. Mafia games end in five seconds.

So knights and knaves instead speak with gadgets. Instead of saying statement P directly, they embed P in a formulaic sentence. The most famous gadget is

If you asked me, I would say P.

Both knights and knaves can say this, as long as P is true. Saying this "gives away" the value of P. By contrast, the gadget

P is true or I am a knight.

Can be said by knights regardless of the truth-value of P, and by Knaves only if P is false. So if you later find out that P is true, you know for sure the speaker was a knight.

The island council is looking for a gadget has all of these properties:

  1. Anybody can use it to say P or !P, regardless of if they are a knight or a knave (their "alignment").
  2. You cannot determine if P is true or false, even if you know the speaker's alignment.
  3. You cannot determine the speaker's alignment, even if you know the value of P.

Using the gadget should be easy to use and scalable: no asking everyone on the island to memorize a private key!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ "say P or !P" doesn't seem well-defined. does that mean "P" is embedded in the statement? or that "P is ___" is embedded in the statement? or "P" is in the statement and it can be true or false? $\endgroup$
    – Cireo
    Commented Oct 22 at 7:31
  • $\begingroup$ @Cireo The way I interpreted it, P represents the true answer to a question. For instance, if someone was asked, "Is the sky red", the response "No" would act as P, and "Yes" would act as !P (assuming the sky was, in fact, not red). $\endgroup$
    – Blue Herring
    Commented Oct 22 at 9:40

5 Answers 5

Reset to default
19
$\begingroup$

Same idea as Kagami, with the potential advantage of only containing P once:

If I'm a knave, then P and pigs fly!

Explanation

Although it is a bit strange, in logic, a statement of the form "If A, then B" is automatically true if A is false. Thus a knight can always make the statement. Since "P and pigs fly" is false, the statement is "If true, then false" which is false for a knave and thus a knave can say it as well. Since a knight or a knave can always say it, we can learn nothing about the truth of the statement or the status of the individual.

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ I suspect that an even better answer is something like "I am a Knight and P is an utterance," so that these good folk are able to also communicate things that don't have well-defined truthiness. $\endgroup$
    – kagami
    Commented Oct 22 at 0:58
  • $\begingroup$ Good point. I just realized "I am a knight and (P ot true) works", but yours is even better. $\endgroup$
    – Tyler Seacrest
    Commented Oct 22 at 1:45
  • 1
    $\begingroup$ (+1) I was going to answer with "Rvgure V nz n Xavtug naq V nz n Xanir naq C, be V nz n Xavtug," but yours is equivalent (and nicely phrased). $\endgroup$
    – mathmandan
    Commented Oct 22 at 13:32
14
$\begingroup$

I am a knight and (P or not P)

Improve this answer
$\endgroup$
7
$\begingroup$

The following works as long as either there is at least one knave on the island, or that they are aware of the existence of people who are not knights nor knaves.

"I am a knight, and I think someone could say $P$"

This has the benefit of sounding more natural to outsiders and carrying the insinuation that $P$ is true.

Improve this answer
$\endgroup$
5
$\begingroup$
  1. By the laws of the land

We know that the gadget g(is_knight, predicate_is_true) must construct statements that are true for Knights and false for Knaves, if they are to say them.

  1. Anybody can use it to say P or !P, regardless of if they are a knight or a knave (their "alignment").

Thus each combination below must be speakable. 

g(true, true) == true
g(true, false) == true
g(false, true) == false
g(false, false) == false

  1. You cannot determine if P is true or false, even if you know the speaker's alignment.

We already know this, since g(x, true) == g(x, false) above.

  1. You cannot determine the speaker's alignment, even if you know the value of P.

We have the second half already from g(x, true) == g(x, false) above, P has no impact on the statement. Since we require g(x, *) to not disclose any new information about x, it must either be always true, always false, or a statement about x.

However, since we already require g(true, *) == true and g(false, *) == false, it cannot be constant, and is forced to be g(x) = x.

Putting this all together the only statements are ones ...

.. that ultimately reduce to x, e.g. I am a knight, I am not a knave, I tell the truth. The statement must ignore P altogether either by: omitting it, which might fail condition 1; rendering it tautology with P or !P, P or true. If we want a satisfying answer that uses P once in a meaningful way, we seem to be out of luck by design.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Doesn't this fail condition 3 though? $\endgroup$
    – Bass
    Commented Oct 22 at 8:57
  • 2
    $\begingroup$ +1 for most of this answer — a thorough argument that if the gadget is some logical function of P and the alignment, then its truth-value must be equivalent to rot13(“V nz n xavtug”), and independent of P. But your final conclusion is wrong — the gadget-utterance is meant to communicate the statement P, so it has to incorporate P syntactically, as requirement (1) states; but that’s not incompatible with its truth-value being independent of P, as other answers show. So we’re not “out of luck by design”. $\endgroup$
    – Peter LeFanu Lumsdaine
    Commented Oct 22 at 10:43
  • $\begingroup$ I wasn't saying there isn't any answer to the question-as-posed, just that none of them seem likely to be (subjectively) "satisfying", in the way that A knight would say P, a knave would say not P might, because it cannot make any statement that is in any way bound to P's meaning. $\endgroup$
    – Cireo
    Commented Oct 22 at 17:18
  • $\begingroup$ @PeterLeFanuLumsdaine But Cireo qualifies that statement with "If we want a satisfying answer etc.", and then it is really the bottom line: indeed, with the given rules, rot13(gur bayl nyybjrq hggrenaprf ner gubfr gung ner gbgnyyl havasbezngvir). $\endgroup$
    – Julio Di Egidio
    Commented Oct 22 at 17:18
1
$\begingroup$

Taking a more creative approach, the new gadget could be:

(Yes, you read that right)

Explanation:

A gadget doesn't have any minimum length, so technically both Knights and Knaves could simply choose to not respond. Again, a more creative approach, not necessarily meant to be a perfect answer :)

This means that:

  1. Anyone can use/say this gadget and either P or !P could still be true.
  2. One cannot determine if P is true or false, even if the alignment of the speaker is known.
  3. One cannot determine the alignment of the speaker, even if the value of P is known.
Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ By my reading of the rules the gadget must contain P $\endgroup$
    – Jasen
    Commented Oct 24 at 4:42
  • $\begingroup$ The way I interpreted it was sort of like a function (assuming you're referring to rule #1). For example, gadget(p) { return P + " is true or I am a knight." }. In my answer, P would still be passed into this function: gadget(p) { return "" }. $\endgroup$
    – Blue Herring
    Commented Oct 24 at 10:06
  • $\begingroup$ The rules say that the gadget must permit the speaker to "say P or !P". This doesn't fulfil that criteria, because they don't end up ever able to say P or !P. It needs to reach the output. $\endgroup$
    – ConnieMnemonic
    Commented Oct 24 at 10:45
  • $\begingroup$ @ConnieMnemonic I see; I originally thought of "say" as "indicate", not literally say aloud. $\endgroup$
    – Blue Herring
    Commented Oct 24 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.