A Blue-Eye Paradox: Solution Not Unique

[Demystifier]

You know that it's BBB because you know the initial state...
Let me rephrase it then to be clearer... how would the XBB state evolve with time? X is unknown (B or R)...

What do you mean by "unknown"? Unknown by who? By external observer? By X himself? By one of the two known B's? Without that information, I cannot answer your question.

In particular now we look at the state as seen by the eyes of 1 of the Bs...

That cannot be from the point of view of one of known B's, because they know what is X. So it can only be from the point of view of X himself. Now I, as external observer, know that X=B, so I know that the actual situation is BBB. But of course, X does not know it yet, so this is how his evolution looks like:
Day 0: XBB. X knows that the two B's will not kill themselves at Day 1.
Day 1: XBB. The two B's do not kill themselves, just as X predicted. X hopes that X=R, in which case the two B's will kill themselves at Day 2.
Day 2: The two B's do not kill themselves.
Day 3: X observes that B's did not kill themselves. Therefore BBB. Therefore X has to kill himself at Day 3. All 3 of them kill themselves at Day 3.

 

[ChrisVer]

you just wrote down what the solution actually looks like...
however you said in D3 that "Therefore BBB", how did you deduce that if you didn't had to run back to RBB example?

 

[Demystifier]

you just wrote down what the solution actually looks like...
however you said in D3 that "Therefore BBB", how did you deduce that if you didn't had to run back to RBB example?

I see what you mean. Yes, one needs to run back to RBB, but only for reductio ad absurdum. To prove that something cannot be, one considers the possibility that it can be and derives a contradiction.

But I don't think that there is any disagreement between you and me on that. The only question is whether we really need a prophet at Day 0, for the case BBB. I say we don't.

 

[ChrisVer]

The only question is whether we really need a prophet at Day 0, for the case BBB. I say we don't.

As I said in a previous post, no you don't need a prophet for that case, because it is an extreme... watch out; not needing him does not mean you get something wrong if you include him. We can just say that in that particular case his existence is unecessary...
But in all other cases his presence is needed to reach a reliable answer... (as I mentioned the RRB state, in which without the prophet everybody'd die)...I guess the prophet makes the problem solvable in all cases then, and so he's necessary for the solution, and for some special cases his information is just repeating.

 

[Lord Crc]

The puzzle mentioned in the first stackexhange link cannot be reduced to n=3 without changing the puzzle. The original states there are 100 blue eyed and 100 brown eyed. Thus each non-guru can see several blue eyed and several green eyed people.

That the guru stating she sees at least one blue eyed person changes anything for anyone I don't get, but hey I didn't even take logic at uni.

 

[ChrisVer]

That the guru stating she sees at least one blue eyed person changes anything for anyone I don't get, but hey I didn't even take logic at uni.

try working with 5 blues and 5 reds...

The original states there are 100 blue eyed and 100 brown eyed.

the numbers 100-100 are arbitrary and can be set to whichever value you want... you can also deduce that by the statement that the inhabitants don't know the absolute numbers of blue/brown eyes...

 

[Lord Crc]

try working with 5 blues and 5 reds...

I'll use the more conventional blue and brown: If person X has blue eyes he will see 4 people with blue eyes and 5 with brown eyes.

On day zero the Oracle comes and says she sees someone with blue eyes. Person X says "duh".

The case is symmetrical if you swap blue and brown, so each person sees 4 with their own color and 5 with the other color. They all say "duh" when the oracle shares her insight.

 

[ChrisVer]

I'll use the more conventional blue and brown: If person X has blue eyes he will see 4 people with blue eyes and 5 with brown eyes.

I went with reds because it allows better the single letter representation B and R ... (while both Blue and Brown start with B).

On day zero the Oracle comes and says she sees someone with blue eyes. Person X says "duh".

what would a person X do for the next day then?

my point is that this:

cannot be reduced to n=3 without changing the puzzle.

is wrong, since the number n can be anything (even 1000-1000 with n=2000) by keeping the puzzle the same... that's why I sent you into solving the n=10 one...you'd eventually start building the solution as was built for the n=3.

 

[Lord Crc]

what would a person X do for the next day then?

Well what could X do? X knows each person sees at least two other persons with blue eyes, thus X know that a) the oracle did not give X any new information and crucially b) the oracle did not give anyone else any new information (every person already saw at least one blue eyed before the oracle spoke).

That's why n matters, with n=3 say X cannot make this conclusion.

 

[ChrisVer]

From X's prespective however, he (X) is either Blue or Brown eyed...
What would happen in the case that you had 1 Blue and 9 Brown eyed people [without the input of the prophet]. The answer is that the Browns are going to kill themselves.

 

[Lord Crc]

From X's prespective however, he (X) is either Blue or Brown eyed...
What would happen in the case that you had 1 Blue and 9 Brown eyed people [without the input of the prophet].

That is an entirely different scenario from the one described in the stack exchange post and thus it's hardly surpring it has a different result, no?

 

[maline]

The only question is whether we really need a prophet at Day 0, for the case BBB. I say we don't.

Why not? Please explain in detail what chain of inferences could allow any of the monks to discover his own eye color, without the prophet's input. If you like you can define day zero as when the suicide law was instituted.

 

[Zafa Pi]

I agree that prophet's information is important in RRR, RRB, and RBB cases. However, I think that prophet's information is not important* in the BBB case.

The prophets is not important in the case RBB. Everybody sees a B so no information was imparted by the prophet. Now I know that you have some fancy pants logic that says otherwise, using ten dollar words like "inference", but my logic is a perfectly good solution. I see that you brought up B. Russel, well of course, he is depicted on your icon. Well I told my solution to my mom, and she's a wonderful person and pretty damn smart too, and she agrees with my solution. So in the RBB case after the prophet speaks nothing new happens. That's my solution and I'm sticking to it.

I hope the monitors allow sarcasm.

 

[ChrisVer]

That is an entirely different scenario from the one described in the stack exchange post and thus it's hardly surpring it has a different result, no?

It is the same problem where the numbers are changed a little (ratios of Blue/Brown)... the concepts are still the same, since the inhabitants never knew those ratios to start with... For example for an inhabitant with blue eyes, the numbers could as well be 99 Blues and 101 Browns (considering himself a brown eye) or 100 Blues and 100 Browns... similiarily for a brown-eyed person (after replacing Blue<->Brown).

Someone has to give some numbers in the start, in order to get an answer to the logical question (because the total number of days depend on the total number of blue-eyed). Why would that affect the total logic that leads to the solution? This logic utilizes only what 1 observes and takes as information and the fact that they are robot-like taking decisions.

 

[ChrisVer]

Why not? Please explain in detail what chain of inferences could allow any of the monks to discover his own eye color, without the prophet's input. If you like you can define day zero as when the suicide law was instituted.

I think I understood that objection.. let's call day 0 the day that the rule becomes known to the 3B inhabitants...
Day 0: each B sees BB... he can't say that he is a !B
Day 1: Noone dies. Each B sees BB again... he still can't say that he is a !B
Day 2: Noone dies. Each B sees BB again... however if that B was a !B, the other two Bs would have died by this day***. He becomes certain he is a B.
Day 3: B dies... all of B die...

The prophet's input here is unnecessary as I mentioned to 1 post, I suspect due to the complete symmetry of the setup... In fact, I agree with Demystifier here; that in this special case the outcome is determined just by the rule itself... However, I disagree that this is a complete answer since there are cases where it cannot be applied without inconsistency to the game rules (so it's preferable to add an extra unnecessary to some cases parameter which makes the solution always existent for all, even those that it is not supposed to affect)*** if the mentioned B was a !B, one of the other two Bs would have been seeing a B(!B) and would have died by Day2.

 

[Lord Crc]

It is the same problem where the numbers are changed a little (ratios of Blue/Brown)... the concepts are still the same, since the inhabitants never knew those ratios to start with...

The initial conditions give are that there are 100 blue-eyed and 100 brown-eyed, so we know nobody on the island is thinking maybe he's the only blue-eyed and the other 199 are all brown-eyed. Everyone on the island knows the distribution is either 99 blue-eyed and 101 brown-eyed, or vice versa.

In either of these two cases (as with your 5/5 example), an arbitrary person X can see at least two blue-eyed people, regardless of their own color. This means that an arbitrary person X knows that any other person Y can see at least one blue-eyed person, regardless of Y's color.

This is why I don't see how the Oracle's fact changes anything.

That you can get other solutions by changing the initial conditions is irrelevant, just as the other solutions to \lim_{x \to \infty} a^x are irrelevant if you ask me to find the limit when a \in (0, 1).

 

[ChrisVer]

The initial conditions give are that there are 100 blue-eyed and 100 brown-eyed, so we know nobody on the island is thinking maybe he's the only blue-eyed and the other 199 are all brown-eyed. Everyone on the island knows the distribution is either 99 blue-eyed and 101 brown-eyed, or vice versa.

I am sorry I don't understand your point here...
I believe you turn the "paradox" in something extremely specialized. Well you can find a solution to this, but it won't be the general solution.
In particular the solution: y(x)=5 e^{x} is a solution to the differential equation \frac{dy}{dx} = y but it's a special case of a complete family of solutions that are y(x) = a e^{x}.
Not only that (which has nothing wrong in it), but by just looking at the particular data will lead you to something worse/wrong. As I demonstrated with the alternative initial condition state, you will reach an unreasonable result which violates the game rules.
So the presence of the prophet is 100% necessary to make all the cases solvable and so he well exists in the initial setup. It changes nothing in some cases, but also makes others solvable as well...

In the diff eq example above, you can end up with 5e^x being the solution to \frac{dy}{dx} = y ~~,~~y(0)=5 (taking a particular initial condition), but it's not the solution to \frac{dy}{dx} = y ~~,~~y(0)=1 or \frac{dy}{dx} = y ~~,~~y(0)=9... The y=a e^x is by setting a appropriately.

That you can get other solutions by changing the initial conditions is irrelevant, just as the other solutions to limx→∞axlim_{x \to \infty} a^x are irrelevant if you ask me to find the limit when a∈(0,1)a \in (0, 1).

Well that's like a flaw... I am not going to think a lot about it at the moment, to see whether you would have to approach the limit differently depending on whether a is in (0,1) or !(0,1)... but I could take your example one step further and ask you if you'd find the limit differently if a=0.0001 or a=0.98 (randomly taken numbers).

 

[Lord Crc]

I am sorry I don't understand your point here...

My point is that initial conditions in the original problem means that every person can see at least two other persons with blue eyes, and from that it follows (or at least, my brain tells me so) that every person already knows at least one person has blue eyes. The logic used to deduce this cannot work for all initial conditions, but does (at least, my brain tells me so) for the initial conditions given in the original problem.

Well that's like a flaw... I am not going to think a lot about it at the moment, to see whether you would have to approach the limit differently depending on whether a is in (0,1) or !(0,1)...

Well for non-negative a it has three solutions, 0 for a \in [0, 1), 1 for a = 1 and \infty for a \in (1, \infty). But my point was that if you tell me a \in [0, 1), then the two other cases are irrelevant.

edit: I meant a \in [0, 1), getting a bit tired here.

 

[Dr.AbeNikIanEdL]

That cannot be from the point of view of one of known B's, because they know what is X. So it can only be from the point of view of X himself. Now I, as external observer, know that X=B, so I know that the actual situation is BBB. But of course, X does not know it yet, so this is how his evolution looks like:
Day 0: XBB. X knows that the two B's will not kill themselves at Day 1.
Day 1: XBB. The two B's do not kill themselves, just as X predicted. X hopes that X=R, in which case the two B's will kill themselves at Day 2.
Day 2: The two B's do not kill themselves.
Day 3: X observes that B's did not kill themselves. Therefore BBB. Therefore X has to kill himself at Day 3. All 3 of them kill themselves at Day 3.

Could you proof that in the RBB case it follows that the two B's will kill themselves at Day 2? You seemed to agree that the prophet is needed for that case!

 

[andrewkirk]

another solution (the standard one) is that they will all commit suicides after 100 days

How does suicide come into it? I read carefully over the first link in the OP and glanced over the other two and couldn't see any mention of suicide. The key action is leaving the island. Why the refs to suicide and how do they relate to the problem as stated?

 

[Dr.AbeNikIanEdL]

Apparently, in an alternative formulation the rule is that they have to kill themselves as soon as they are sure they have blue eyes. Of course for the logic problem it is not important what action it actually is as long as it is a unique action visible to the others.

 

[ChrisVer]

How does suicide come into it? I read carefully over the first link in the OP and glanced over the other two and couldn't see any mention of suicide. The key action is leaving the island. Why the refs to suicide and how do they relate to the problem as stated?

The setup was somehow changed from the departing inhabitants of an island, to monks who listen to a prophet and commit suicide.

 

[disregardthat]

The initial conditions give are that there are 100 blue-eyed and 100 brown-eyed, so we know nobody on the island is thinking maybe he's the only blue-eyed and the other 199 are all brown-eyed. Everyone on the island knows the distribution is either 99 blue-eyed and 101 brown-eyed, or vice versa.

Let's say there are 3 blue-eyed monks on the island, A,B and C, and that the prophet has not spoken yet. Then everyone knows that there are either 3 or 2 blue-eyed monks. In the perspective of A, he must consider two cases. Either he has blue eyes, or he has brown eyes. If A has blue eyes, then B and C see two monks with blue eyes. If A has brown eyes, then B and C see one monk with blue eyes. Due to the latter possibility, A concludes that B and C individually can not exclude the possibility that they in fact too have brown eyes.

If we further investigate this last case, then the last monk can not exclude the possibility that he has brown eyes as well. In other words, A further concludes that B cannot conclude that C can exclude the possibility of having brown eyes. Similarly, A concludes that C cannot conclude that B can exclude the possibility of having brown eyes. And of course, B and C will mirror these conclusions.

So everyone does not know that everyone knows there are 3 or 2 blue-eyed monks. The correct statement is that everyone knows that everyone knows that there are 3,2 or 1 blue-eyed monks. And by the argument above, the only correct statement in a further nesting would be that everyone knows that everyone knows that everyone knows that there are 3,2,1 or 0 blue-eyed monks. But once the prophet claims there are at least one blue-eyed monk, everyone strengthens this last statement to everyone knows that everyone knows that everyone knows that there are 3,2,1 blue-eyed monks. This is because everyone knows that everyone heard the prophets claim. And everyone knows that everyone knows that everyone heard the prophets claim. And so on...

This is the explanation of precicely how the prophet is actually giving additional information to everyone. This may be extended to the cases where there are more monks on the island. It is similar, but of course much longer for 100 monks.

 

[andrewkirk]

I think that the problem is not well-specified, and hence has no solution. The reason is the vagueness of the term 'perfect logician'.

I take it that 'perfect logician' is intended to mean something like 'somebody that will deduce from a given set of axioms anything that can be deduced from them using first-order predicate logic (FOPL) in language L' . I choose FOPL because it is the most flexible and expressive logic one can use without having to make a whole bunch of other definitions and constraints in order to avoid paradoxes. We could consider it for other logics such as one of the many varieties of modal logic, but for the sake of concreteness and simplicity, let's stay with FOPL for now. The language L doesn't need to be specified for the purposes of this problem but I think we should assume it is countable, as I think there may be problems with uncountable languages.

The axioms are set out in the first paragraph of the problem statement, and include statements like 'the oracle speaks once a day ...' and 'those who have deduced that they have blue eyes leave on the day they make the deduction'. It also includes the 'perfect logician' statement. Let's denote all the other axioms collectively by B and the 'perfect logician' axiom by C. Then the set of axioms is B+C (where I use '+' here to indicate union). But 'perfect logician' is unclear so let us expand C. It says

'Each person will deduce whatever can be deduced from B+C in FOPL under L'​

Oh dear. There's still a C in there, which we remember was unclear. Let's expand that. that gives us:

'Each person will deduce whatever can be deduced from B+(Each person will deduce whatever can be deduced from B+C in FOPL under L) in FOPL under L'

Bother! There's still a C in there. Let's get rid of it by expanding again:

'Each person will deduce whatever can be deduced from B+(Each person will deduce whatever can be deduced from B+
'Each person will deduce whatever can be deduced from B+(Each person will deduce whatever can be deduced from B+C in FOPL under L) in FOPL under L'
in FOPL under L) in FOPL under L'

... and so on, ad infinitum

The consequence of this infinite regress is that there is no finite statement of the axiom C. Since an axiom must be a well-formed formula (wff) and one of the requirements of being a wff is that it be composed of a finite number of symbols, we find that there is no possible valid axiom C.

So the problem is not well-defined, and hence has no solution.

It's conceivable there may be some way around this using a higher-order logic. But my hunch is that, whatever logic we use, we are going to run into a Godelian problem that one cannot deduce, from inside any sufficiently rich logical theory, which wffs are theorems of the theory.

 

[ChrisVer]

I don't get it, what is wrong in your axiom "C"?
Also I don't see how this goes to infinity since there is a fixed and finite number of possible "each person".

 

[andrewkirk]

I don't get it, what is wrong in your axiom "C"?

It's self-referential and generates an infinite regress in trying to understand what it is saying.

C says 'each person will deduce whatever can be deduced from this set of axioms'

But this set of axioms includes C. So to work out what a person can deduce, we first need to know what they can deduce.

 

[ChrisVer]

I see finiteness in the 3 people example, and I understand that in the BBB case, it's the perfect logician assuming that the others are perfect logicians that leads to the solution. Of course if you keep on trying to divide this up, you will end up interconnecting all people [since they all die on the same day] and start looping between their connections, "repeating the same axiom".
Is a circle something finite or infinite? Seeing it as a circle it's finite (parametrized in x<[0,2pi] )... seeing it as a closed curve it can be infinite (parametrized in x<[-infty, infty] ).

 

[Zafa Pi]

The prophets is not important in the case RBB. Everybody sees a B so no information was imparted by the prophet. Now I know that you have some fancy pants logic that says otherwise, using ten dollar words like "inference", but my logic is a perfectly good solution. I see that you brought up B. Russel, well of course, he is depicted on your icon. Well I told my solution to my mom, and she's a wonderful person and pretty damn smart too, and she agrees with my solution. So in the RBB case after the prophet speaks nothing new happens. That's my solution and I'm sticking to it.

I hope the monitors allow sarcasm.

I see what you mean. Yes, one needs to run back to RBB, but only for reductio ad absurdum. To prove that something cannot be, one considers the possibility that it can be and derives a contradiction.

But I don't think that there is any disagreement between you and me on that. The only question is whether we really need a prophet at Day 0, for the case BBB. I say we don't.

I apologize for being snarky in post #73, but in case RBB and BBB it can be claimed that the prophet creates no new info when she says there is at least one B. So in either case one could claim the solution is that nothing new will happen. But you see them as different. How so (in the fewest words you can)?

 

[andrewkirk]

Another way to see the difficulty is to note that a logical language cannot in general make statements about whether a statement in that language is provable. That's because we get an infinite regress when we try to refer to wffs in the language. To define a wff we need to give a recursive definition that starts with a fixed finite or infinite set of symbols for constants, variables, functions and predicates. But then how do we refer to a wff in the language? We run into the 'naming vs using' problem. A wff like '1+1=2' is not a reference to the wff '1+1=2', just as I am not my name. So we need to generate some new constant symbols to refer to wffs using the original set of language symbols. But that then means that our original assumption that we were starting with the full set of language symbols was incorrect.

Trying to define a formal language that can refer to itself ends up being like trying to define a set of all sets, and we know what sort of a muddle that leads to.

We can refer to our language in ordinary speech in our language, because ordinary speech is informal. But if we are to talk about 'perfect logicians' we can only use formal languages to specify what their perfection means, and then we get stuck in an infinite regress.

 

[Ken G]

The prophet said them something that they already knew, so there is no reason to change anything in their behavior.

Actually, this isn't correct. It is true that the prophet said something they all already knew, but this does not mean new information was not conveyed. The whole crux of the situation is that it is essential that everyone in the tribe witness the prophet speaking to everyone else, so the new information is that the people now know what the other people know. There is no reason to ever have any more than two blue-eyed people, that version of the puzzle makes all clear. If there are two blue-eyed people, the solution really is pretty much unique, but you do have to assume that people can tell when other people are listening, and that the other people will draw the correct conclusions. But that's not a stretch when there are two people with blue eyes.