6 ms·

There are many problems with this puzzle that go against the intuition. - the number of prisoners is infinite, so they will never finish answering the question

by Grue3 10y ago

There are many problems with this puzzle that go against the intuition. - the number of prisoners is infinite, so they will never finish answering the question. At any point in time, only a finite number of prisoners will be freed. - a single prisoner must process an infinite amount of information to reach the decision. In fact, by observing only a finite number of hats he cannot possibly choose the answer. - the number of equivalence classes is uncountable. Not even a countably infinite number of prisoners can possibly have enough time to pick out a single element from every equivalence class.

Tloewald 10y ago
As soon as you start treating the axiom of choice as a superpower for a conscious being you are in conceptual la la land. How do I guess the color of my hat if there's an uncountable number of possible colors? Doesn't that mean that communicating the value of that color involves transmitting an infinite amount of informtion?
- waqf 10y ago
  Quick, tell me your favourite number between 0 and 1. How did you do that? Weren't there an uncountable number of possible numbers? Ah, you may say, but I obviously wasn't going to choose one with an infinite information content, so all but countably many possible numbers had probability 0. Which is true. But in fact it's true that whenever you have a probability measure on an uncountable space then all but countably many elements have probability 0, so that escape clause applies equally well to the hat colours.
  - TheCoelacanth 10y ago
    But the axiom of choice applies to all sets, not just ones that you can easily choose a number from. For instance, what is your favorite non-computable number between 0 and 1?
    - red75prime 10y ago
      Inverse of Kolmogorov complexity of thirteenth bit-string with uncomputable Kolmogorov complexity, of course.
  - Tloewald 10y ago
    When we think of numbers between 0 and 1 we aren't thinking of Real numbers. Name a transcendental number between 0 and 1. Which one springs to mind? Maybe, if you're lucky you can come up with some famous transcendental number and "scale" it to lie within the interval (pi over ten!). The numbers we live with are a finite dimensional vector field over a bounded subset of algebraics - not even countable.
leereeves 10y ago
This puzzle seems rather hand-wavy to me. If we actually define a specific finite number N in the equivalence relation "two such sequences [are] ‘equivalent’ if they are equal after [N] entries", no one is in a position to take advantage of the equivalence classes. Either their position <= N, in which case the equivalence class does not specify the color of their hat... Or their position > N, in which case they cannot see the entire sequence after N entries and thus cannot determine which equivalence class the sequence belongs to. Unless I'm missing something.
- waqf 10y ago
  N is not fixed, so we're always in case (i), position ≤ N. The equivalence class does indeed not specify the colour of the hat. The invocation of the Axiom of Choice was used to tell the prisoner what to guess in that equivalence class, although there is no guarantee that it is correct in their specific case.
  - leereeves 10y ago
    How does a prisoner know where they are in the pre-chosen sequence? Seeing only an infinite number of hats ahead, which match some pre-chosen sequence after an unspecified finite number of hats, how do they know if they are in position, 1, .... i-1, i, i+1, etc? I mean, even if you know which equivalence class the sequence belongs to, you won't be able to guess at the color of your own hat without knowing your position.
jmount 10y ago
I think the intuition that such infinite games make sense requires the axiom of determinacy to be well founded. The axiom of determinacy has been known to contradict the axiom of choice since the early 1960s (i.e. it is inconsistent to have both the axiom of choice and the axiom of determinacy).

by Grue3 10y ago

Tloewald 10y ago

As soon as you start treating the axiom of choice as a superpower for a conscious being you are in conceptual la la land. How do I guess the color of my hat if there's an uncountable number of possible colors? Doesn't that mean that communicating the value of that color involves transmitting an infinite amount of informtion?

waqf 10y ago
Quick, tell me your favourite number between 0 and 1. How did you do that? Weren't there an uncountable number of possible numbers? Ah, you may say, but I obviously wasn't going to choose one with an infinite information content, so all but countably many possible numbers had probability 0. Which is true. But in fact it's true that whenever you have a probability measure on an uncountable space then all but countably many elements have probability 0, so that escape clause applies equally well to the hat colours.
- TheCoelacanth 10y ago
  But the axiom of choice applies to all sets, not just ones that you can easily choose a number from. For instance, what is your favorite non-computable number between 0 and 1?
  - red75prime 10y ago
    Inverse of Kolmogorov complexity of thirteenth bit-string with uncomputable Kolmogorov complexity, of course.
- Tloewald 10y ago
  When we think of numbers between 0 and 1 we aren't thinking of Real numbers. Name a transcendental number between 0 and 1. Which one springs to mind? Maybe, if you're lucky you can come up with some famous transcendental number and "scale" it to lie within the interval (pi over ten!). The numbers we live with are a finite dimensional vector field over a bounded subset of algebraics - not even countable.

leereeves 10y ago

This puzzle seems rather hand-wavy to me. If we actually define a specific finite number N in the equivalence relation "two such sequences [are] ‘equivalent’ if they are equal after [N] entries", no one is in a position to take advantage of the equivalence classes. Either their position <= N, in which case the equivalence class does not specify the color of their hat... Or their position > N, in which case they cannot see the entire sequence after N entries and thus cannot determine which equivalence class the sequence belongs to. Unless I'm missing something.

waqf 10y ago
N is not fixed, so we're always in case (i), position ≤ N. The equivalence class does indeed not specify the colour of the hat. The invocation of the Axiom of Choice was used to tell the prisoner what to guess in that equivalence class, although there is no guarantee that it is correct in their specific case.
- leereeves 10y ago
  How does a prisoner know where they are in the pre-chosen sequence? Seeing only an infinite number of hats ahead, which match some pre-chosen sequence after an unspecified finite number of hats, how do they know if they are in position, 1, .... i-1, i, i+1, etc? I mean, even if you know which equivalence class the sequence belongs to, you won't be able to guess at the color of your own hat without knowing your position.

jmount 10y ago

I think the intuition that such infinite games make sense requires the axiom of determinacy to be well founded. The axiom of determinacy has been known to contradict the axiom of choice since the early 1960s (i.e. it is inconsistent to have both the axiom of choice and the axiom of determinacy).