Two birds and a liar’s game
This post was largely inspired by an image I encountered while browsing the yard sale we call the internet. It’s somewhat contrived, but it’s a play on a classic riddle, which essentially boils down to the following:
You find yourself in a room with four walls, a floor, and a ceiling. In this room there are two doors, one which leads to heaven (paradise), and one which leads to hell (ruin). You do not know which door is which, and once you open a door, you are stuck with that choice. There is no other way to leave the room.
Fortunately, there are two talking birds in the centre of the room, that know which door is which, and can help you in determining your fate. One bird always tells the truth, while the other will always lie. You are allowed to ask one bird one question, and nothing more. After you ask your question and receive your answer, both birds will disappear and you’ll be left to choose the door you will exit through. What question do you ask in order to find the door to heaven (paradise)?
This problem on its own is not particularly interesting. To be frank, 5 or so seconds of Google-fu will net you an answer. However, the image linked above has two interesting restrictions on top of this that make the problem worth talking about. Most notably:
- God mode: Both birds are invisible to one another, and making reference to either of the other birds will yield the answer “What bird?”
- God slayer mode: God wants to appoint a successor, and you get to take his throne if you can break the curse he’s cast upon you. The curse prevents you from making any IF statements, or have any hypothetical statements in your question. (Let’s also assume you need to know which door is heaven with certainty to beat this mode)
You’ll noticed I’ve changed this from “girls” to “birds,” if only to keep this in the same frame as the original problem. Also, it’s going to get really annoying having to reference the two of them as the “good girl” and the “bad girl,” since lying isn’t inherently bad, as I will (hopefully) show below, and lets face it, androgynous birds are better posed as our adversaries, since nobody likes a dirty bird.
Anyways, that’s enough of a digression. What I wanted to say was that God mode, and particularly the God slayer mode outlined above are interesting problems. For example, how do we ask a question without hypothetical statements? So let’s slay God, or at least poke at him with some twisted logic.
The problem
For this, I’d like to outline the problem specifically. In particular, there are some unspoken assumptions we have about the problem that likely need to be cleared up before we can progress. At the very least, I need to define some terms we’ll be using to clarify what we’re trying to solve. First on the list is to talk about the birds themselves:
The birds
The first and most direct problem we face is the problem of the two birds. One will always tell the truth, and one will always lie. But here’s where our unspoken assumptions will trip us up: what does it mean to always tell the truth and what does it mean to always lie?
To always tell the truth is fairly simple, it means you cannot deny something that is true, and you cannot affirm something that is false. This is easy, because it basically acts kind of like a computer. A computer can’t tell you that 1 does not equal 1. (Well, actually it can, but I’m strictly talking about non-quantum computers and also strictly referring to a very low-level comparison of bits. Don’t pick on this one too much)
The main issue is in how we define the action of “always lies.” I’ve thought about this one a lot, but I’ve mainly broken it down into a couple different definitions. This is the biggest part of the problem that is left ambiguous, namely because you have to make assumptions about the liar in order to succeed.
- Chaotic Liar: A chaotic liar is someone who will provide mostly false information in a non-deterministic way in order to mislead you. Basically, this would be someone who can tell the truth, but only will if it ultimately misleads you further. This is not a good definition for this riddle, because that would mean there is no solution.
- Simple Liar: A simple liar is someone who will lie to explicit predicates, but the results of operations are preserved. What I mean by this is for example, if you asked them “Is the sky blue?”, they might be inclined to answer with “false, the sky is not blue.” However, if you asked something along the lines of “is the sky either blue or not blue?”, they would have to answer with true, because true OR false implies that the whole statement is true.
- Complex Liar: A complex liar is someone who will lie to explicit predicates and while tautologies are preserved, the results of operations are not. If you ask “Is the either blue or not blue?”, they will answer false. Thus, this means that the meaning of AND, OR, and NOT statements are likewise not preserved.
So based on these definitions of a “liar,” we can start to approach our problem. Specifically, we need to outline whether or not we’re dealing with a simple, complex, or chaotic liar in order to formulate an answer. If we don’t decide this beforehand, we won’t be able to come up with an answer, since we could otherwise be dealing with a chaotic liar, which is basically a prime example of an unbounded problem, since the chaotic liar will always manage to mess you up.
Intro to Logic: Some basic terminology
Here’s a small reference list of some basic terminology for working with logic, specifically first-order logic. I’m going to use a fair amount of this terminology, and it’ll be important to explicitly label what I mean when I refer to predicates vs. compound expressions.
Predicates
A predicate is basically just some kind of property that characterizes something. Usually, we pose it as a question of some kind. So building off of the sky example from before, we might say that the colour of the sky is an important characteristic. Thus, our predicate could be phrased along the lines of “is the sky blue?”, which we can then evaluate to either true or false, depending on whether the sky is blue or not.
Often times we shorten our predicates to single letters, like A or B, just to make it easier to write. It would be painful to have to write out the same predicate five or six times in the same expression, so it’s easier to just deal with single letters.
AND, OR, XOR, NOT
I mentioned this briefly when talking about the birds, but its important that these definitions are taken care of in advance. Programmers and anyone who has taken a first-order logic course would know the formal definitions I’m going to outline, but for the sake of completeness I’m going to be very explicit with these.
AND - Let us suppose we have two predicates available to us, the first named A, the second named B. A AND B is true if and only if (iff) both predicates are true. We represent AND by using the \(\cap\) symbol. Therefore:
| A | B | A \(\cap\) B |
|---|---|---|
| true | true | true |
| true | false | false |
| false | true | false |
| false | false | false |
OR - Suppose again we have two predicates available to us, the first named A, the second named B. A OR B is true iff either predicate is true. OR is inclusive, so if both are true, the statement is still true. We represent OR by using the \(\cup\) symbol.
| A | B | A \(\cup\) B |
|---|---|---|
| true | true | true |
| true | false | true |
| false | true | true |
| false | false | false |
NOT - Suppose we have one predicate, namely A. NOT A is simply the opposite of A, so if A is true, NOT A is false, and vice versa. You can probably guess where this is going and why it’s important when dealing with birds. We represent NOT using the \(\lnot\) symbol.
| A | \(\lnot\)A |
|---|---|
| true | false |
| false | true |
XOR - This is actually a special operator, because we can derive this operator from the others. If we again assume two predicates, A and B, A XOR B is true iff either A or B is true, but not both. XOR actually stands for exclusive-or, which is different from A \(\cup\) B in that if both are true the statment is false. In truth though, A XOR B is logically equivalent to \((A \cup B) \cap \lnot(A \cap B)\). However, I’m defining it here for the sake of brevity. The symbol we use to express XOR is \(\oplus\), and is basically defined as:
| A | B | A \(\oplus\) B |
|---|---|---|
| true | true | false |
| true | false | true |
| false | true | true |
| false | false | false |
Tautologies
A tautology is a statment that is always true, regardless of the interpretation. I mentioned this before, but we’ll formalize this here. Suppose you one predicate A, we can make a simple tautology by saying: \(A \cup \lnot A\), which is basically saying A or not A. The cool thing about tautologies is that since they’re always true, you’re not assuming anything by stating one. It doesn’t matter what the hypothetical is, since these are always true regardless of the world / universe / imagination you live in.
To be frank, these kinds of statements aren’t particularly informative. I mean, it always evaluates to true, so we can’t garner a whole lot of information from just a single tautology, but we can use tautologies to bend logic in weird ways. More on that later.
Hypotheticals / If statements
One of the conditions for clearing god-slayer mode is that we don’t use any if statements, and assume no hypotheticals. Now, I’m going to interpret this as no direct if statements (such as “if I ask the other bird…” etc) and no direct assumptions about the environment when you phrase your question. You can make assumptions in your head, but you’re not allowed to phrase them (so we can assume for example that the liar bird is a simple liar but we can’t say “if you’re a simple liar then P else Q”).
Fun fact about first order logic: there are no “if” statements. Instead, we can derive “ifs” by using a clever combination of AND and OR operators. However, by realizing this, you’ll notice that we’ve created a loophole. We could basically still ask if-style questions by simply translating our formal language into AND and OR statements. You couldn’t complete this riddle if AND and OR operators are not allowed, because then you could only ask direct questions in the form of predicates (you would have no way of joining statements / predicates together). So while the problem is posed poorly, no explicit if statements are allowed (although we’ll allow different interpretations such as AND and OR, because otherwise this problem in not solvable).
The biggest problem with the hypothetical lockdown is it means we have to decide if we’re dealing with a simple or complex liar before we ask our question. And no, I’ll state off the bad that there’s no single solution for all types of liars. I could try to prove this exhaustively, but it’s a detraction from the problem at hand.
Solving the riddle
It’s extremely important to recognize that we need to come up with a solution that fools the liar but respects honest bird. So we need something that will evaluate to true for some property for the honest bird, as well as the liar, and evaluate to false for the honest bird and false for the liar. It may seem paradoxical that we can receive the same answers to a question from both the liar and the truth-teller, but there are much, much stranger things you can do with first order logic than to prove paradoxes. Besides, we’re slaying God, so a paradox is a somewhat shallow road bump to reach that goal.
Crushing the Complex Liar
So we’re finally going to solve this riddle. Dealing with the complex liar is somewhat of a pain because not only are predicates evaluated to the opposite of their real truth values, but so are our operators. Basically for a complex liar our operators change to:
Complex liar - AND
| A | B | A \(\cap\) B |
|---|---|---|
| true | true | false |
| true | false | true |
| false | true | true |
| false | false | true |
Complex liar - OR
| A | B | A \(\cup\) B |
|---|---|---|
| true | true | false |
| true | false | false |
| false | true | false |
| false | false | true |
Complex liar - NOT
| A | \(\lnot\)A |
|---|---|
| true | true |
| false | false |
Complex liar - XOR
| A | B | A \(\oplus\) B |
|---|---|---|
| true | true | true |
| true | false | false |
| false | true | false |
| false | false | true |
Based on this, it will be difficult to tell the difference between the honest bird and the lying one, because our language changes almost entirely when talking between the two. Nevertheless, lets define a predicate, which will be the base of our question.
We’ll start off by assuming that the doors are located on opposite sides of one another; basically that one door is on the right and one door is on the left. For the sake of clarity just assume the birds know which door we’re referring to when we speak of either the left or right door. The predicate I want to define is based around the question:
“Is the door on the right the door to heaven?”
Let’s call this predicate R, since we’re talking about the right door. Let’s also define a tautology since we can; we’ll call this tautology M. Why M? I’d choose T but when dealing with a liar it’s easier to use symbols that may not be misconstrued with True or False (T or F). Notice how earlier I said we can state a tautology without making assumptions or hypotheticals? This is one way of dealing with the “no hypothetical” rule.
\[M := R \oplus \lnot R \Rightarrow \top\]Which basically says that M is defined as R or not R, and this is a tautology (\(\top\))
From here we need a statement which evaluates to true if R is true, and false if R is false, but for both the honest bird and complex liar. To break this down, let’s think about how we might satisfy the case of just the complex liar. We know for a fact that M will always evaluate to true regardless, so we can construct a statement that only evaluates to true if R is true. You may have to reference the table above to make sense of this, but feel free to write this out on paper if it makes it easier to reason about.
\[(M \cap R)\]We know that M will always be true to the liar, so we only need to consider the first two cases for the complex liar’s OR above. We know if R is true, the liar will tell us false, so \(M \cap R\) returns true if R is actually true. If R is false, then the same statement will return false. So how about the honest bird? The honest bird will reply with true if R is true, and will reply with false if R is false.
So we’re already done with the complex liar. This is pretty much because we can exploit the fact that a tautology is true in every interpretation. The final question you’ll ask is:
Is it the case that the right door leads to heaven AND is it the case that the right door either does or does not lead to the path to heaven?
Pretty confusing to say in one shot. All said and done though, this answer is much, much easier to arrive at than that of the Simple Liar (I mean, we basically did a table lookup).
Slaying the Simple Liar
This is a little harder, but is still solvable. We regrettably can’t use the same statement as before, becasue the complex liar uses a different interpretation of AND, whereas the simple liar uses the true meaning of AND, OR, XOR, and NOT, which stops us from pulling the same trick as before.
However, we’ll still assume the same two things as before: assume R and M refer to the same statements. Then, let’s start again with the liar, and see if we can’t come up with some way for the answer to the question to be true if R is true, and false if R is false.
\[(M \oplus R)\]If the above statement is asked to the simple liar, it evaluates to true when R is true, and false when R is false. How about the honest bird? Well, if R is true, the honest bird will reply with false, and vice-versa if R is false. So we’re left at somewhat of a rough spot, where the honest bird tells us the opposite of the liar. This is expected, since the only thing that’s different here is our R, so we need more information. In the previous case, we could determine the difference between the liar and the honest bird based on the differences in how the operators were applied. Here, however, we can’t know the difference between the two, because the operators are the same, and we don’t know enough with R being an unknown.
In this case, we need to additional information. However, we cannot create any hypothetical situations. So we need a predicate based on our prior knowledge of the situation in order to proceed further. Since we can’t make assumptions, we need to use some property of the room. In this case I’ll choose to define D, which is a predicate specifying the following question / statement:
Are there only two doors in this room?
Of course, we don’t necessarily have to use this property, but this is something the birds must know in order to be able to help you solve the problem, and what’s more, the existence of two doors is stated in the problem, so we are guaranteed to not introduce any more hypotheticals. What’s more, we know that there can only be 2 doors in the room, so while it’s not a tautology, we know that the statement can only be true for this specific interpretation. Let’s try constructing a question again:
\[(M \oplus R) \oplus D\]Now, we have four cases, let’s examine them:
Pick liar and R is true:
\[(M \oplus R) \oplus D \\ \Rightarrow (true \oplus false) \oplus false \\ \Rightarrow true\]Pick liar and R is false:
\[(M \oplus R) \oplus D \\ \Rightarrow (true \oplus true) \oplus false \\ \Rightarrow false\]Pick honest bird and R is true:
\[(M \oplus R) \oplus D \\ \Rightarrow (true \oplus true) \oplus true \\ \Rightarrow true\]Pick honest bird and R is false:
\[(M \oplus R) \oplus D \\ \Rightarrow (true \oplus false) \oplus true \\ \Rightarrow false\]Good, we’ve successfully lied to the liar in order to get them to spill the truth about the right door. If we wanted to ask this question, we would have to phrase it like so:
Is it the case that there are two doors in this room and likewise the case that either the right door leads to heaven or that the right door either does or does not lead to heaven but not both the case that the right door leads to heaven and the right door either does or does not lead to heaven?
No hypotheticals. No if statements. A slain god. Also sprach Zarathustra.