Timeline for Infinitely many dwarves wearing hats of 2 colours
Current License: CC BY-SA 3.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 19, 2023 at 23:27 | comment | added | Stef | @SteveJessop I laughed out loud when I read "Using the axiom of choice the prisoners pick a representative from each equivalence class." in the other answer. Now I'm imagining a meeting of the Dwarven bureaucracy where they're officially picking representatives from each equivalence class "using the axiom of choice". Maybe in a Greg Egan short story that would work. | |
| Apr 14, 2016 at 17:53 | comment | added | Hubert OG |
The representative is not well defined in your solution. The "difference" is not a property of a single sequence, but a pair of sequences. For any given sequence we can choose another one for which the different part end at an arbitrarily large position, so there's no string for which the difference appear "at the beginning" only. And the class doesn't have the smallest element lexically (except for (0) class), as for any given element you can construct a smaller sequence by changing first 1 to 0. The rest of solution is great, but we need a solid representative choice algorithm.
|
|
| Jan 14, 2015 at 14:27 | comment | added | JiK | I don't understand what "Choice of a representative can be easily defined as choosing the sequence where the differences appear at the beginning of the sequence and are lexicographically smaller." means. The differences to what? Lexicographically smaller than what? | |
| Jan 13, 2015 at 14:35 | comment | added | Trenin | All I would like to know is what theoretical algorithm or method do the dwarves use to recognize the class? I am not arguing about the physical impossibility of the question, only the theoretical solution to the theoretical question. | |
| Jan 13, 2015 at 14:30 | comment | added | Trenin | A solution should show how the class is recognized. To wave your hands and say it is unimportant how this is done because there is no point in arguing about infinities is a bit of a cop out. | |
| Jan 13, 2015 at 14:24 | comment | added | Trenin | @dmg You started this by saying you can recognize PI. My point is there are an uncountable number of sequences here and it is not as simple as recognizing a few irrational number sequences. The majority of the real numbers are transcendental, which means that you can't even express them with algebraic numbers in an equation. | |
| Jan 13, 2015 at 13:53 | comment | added | Steve Jessop | Anyway, this answer is a bit like solving a puzzle "I have one ball and a knife. I need two balls. How do I get them?" by appealing to the Banach-Tarski dissection. Perfectly reasonable as long as the puzzle is about surprising consequences of the axiom of choice, not about actual balls cut up with actual knives. The answer makes a point, but the point is not about what dwarfs in hats can do, it's about uncountable infinities. | |
| Jan 13, 2015 at 13:34 | comment | added | Steve Jessop | @dmg: asphyxiate when the straight line of dwarfs extends beyond the atmosphere ;-) What it means for the universe itself to be infinite can go on physics.stackexchange. No doubt an ultra-finitist mathematician would respond to the question by saying, "sorry, how many dwarfs did you say there are? You made a noise, but that noise wasn't a number". That is to say, they'd be like Trenin but more so, they'd refuse to accept any hypotheticals about infinite objects/operations even if they're countable. | |
| Jan 13, 2015 at 13:33 | comment | added | dmg | @SteveJessop I'm guessing that infinite dwarves, might get squashed into a black hole or something? Possibly devour the universe? Or stop time? Guess that is a solution as well :) | |
| Jan 13, 2015 at 13:29 | comment | added | Steve Jessop | @Trenin: The question is clearly physically impossible. Even if it were possible for infinitely many dwarfs to exist (which it is not), it's not possible for light from an infinite row of dwarfs to reach the first dwarf in finite time, so he can't ever "see all the hats" as stated. The only meaningful way to respond to the problem is to say something interesting about (physically impossible) operations on infinite data, and about what infinite data it is you're operating on, and what operations you're doing. Drawing a line and saying, "too infinite for me" just rules out some of the interest. | |
| Jan 13, 2015 at 13:27 | comment | added | dmg | @Trenin And I don't see how there are infinite dwarves, and infinite hats and so on... Arguing over whether imaginary dwarves can memorize uncountably infinite classes is quite ridiculous. | |
| Jan 13, 2015 at 13:21 | comment | added | Trenin | @dmg You can probably recognize a finite number of classes, and I will concede that the dwarves can recognize a countably infinite number of classes, but there are uncountably infinity number of classes, and I don't see how they could do that. | |
| Jan 13, 2015 at 13:20 | comment | added | Trenin | @dmg If you saw the binary expansion of sqrt(PI-e), would you be able to recognize it? | |
| Jan 13, 2015 at 13:14 | comment | added | dmg | @Trenin What do you mean? We can recognize PI, can't we? | |
| Jan 13, 2015 at 13:08 | comment | added | Trenin | While this is an interesting theory, is it even possible to recognize the class? The number of classes is uncountably infinite, the same as the real numbers. I find it hard to believe that this could work unless the sequence is repeating (i.e. rational, and thus, countable). | |
| Jan 12, 2015 at 20:12 | comment | added | xnor | @njzk2 That's right. It's not a finite algorithm, if that's your concern. It's a function of infinitely many bits. | |
| Jan 12, 2015 at 20:08 | comment | added | njzk2 | @xnor : but then, for a dwarf to recognize the class, he must only look at hats that every dwarfs can see, doesn't he? | |
| Jan 12, 2015 at 19:57 | comment | added | xnor | @njzk2 Yes, exactly. | |
| Jan 12, 2015 at 19:38 | comment | added | njzk2 | How do we choose the class? It is because each dwarf is preceded by a finite number of dwarfs, and therefore can always see the class after him? | |
| Jan 12, 2015 at 19:07 | comment | added | xnor | I think you should mention that the axiom of choice is being used to pick the representative elements. You can't choose the lexicographically smallest element of the class, as there may be no minimum like for rrrrrr... . There is no constructive algorithm to find representatives. | |
| Jan 12, 2015 at 16:31 | comment | added | Doorknob | Whoops, sorry, I tried to move the comments to chat, purged all the comments, and then realized I couldn't undelete my comment with the chatroom link on mobile. My bad; thanks for finding it. | |
| Jan 12, 2015 at 16:25 | comment | added | Steve Jessop | There is discussion at: chat.stackexchange.com/rooms/20187/… | |
| Jan 12, 2015 at 16:11 | history | mod moved comments to chat | |||
| Jan 12, 2015 at 15:59 | history | edited | dmg | CC BY-SA 3.0 |
added 2 characters in body
|
| Jan 12, 2015 at 15:51 | history | edited | dmg | CC BY-SA 3.0 |
added 846 characters in body
|
| Jan 12, 2015 at 14:55 | history | edited | dmg | CC BY-SA 3.0 |
added 25 characters in body
|
| Jan 12, 2015 at 14:19 | history | edited | dmg | CC BY-SA 3.0 |
added 138 characters in body
|
| Jan 12, 2015 at 14:07 | history | edited | dmg | CC BY-SA 3.0 |
added 170 characters in body
|
| Jan 12, 2015 at 13:40 | history | edited | dmg | CC BY-SA 3.0 |
added 150 characters in body
|
| Jan 12, 2015 at 10:14 | history | answered | dmg | CC BY-SA 3.0 |