Timeline for Why was this question (sorting a countable infinite set) deleted?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Sep 30, 2013 at 1:37 | comment | added | Gottfried Helms | ...(continued) but I think, the discussion of conceptual details were better in the question (if at all, and if the question is not on hold). But here is now late night and I should leave this forum and come back tomorrow... | |
| Sep 30, 2013 at 1:32 | comment | added | Gottfried Helms | @Francois: I think we can only discuss with respect to ordered subsets/partial sets and the time required for the ordering related to their cardinality. The time for Sort/merge is, if I recall right, with n as its cardinality something like $n* \ln(n)$, not even $n^2$, while -if I understand the intention of the phrase "uncountable time" in the question correctly at all- it would mean that the algorithm has something to do with $2^n$ instead (but a definition should explicitely occur in question) Because the input stream is infinite we have of course "never" the "complete order"/stability | |
| Sep 30, 2013 at 1:01 | comment | added | François G. Dorais Mod | @GottfriedHelms: Are you sure the answer is positive? How do you "sort" $\mathbb{Z}$ or $\mathbb{Q}$? If you try to wellorder them, the process won't stabilize. | |
| Sep 30, 2013 at 0:47 | comment | added | Gottfried Helms | The problem reminds me of old computer days, when we were asked for programming an sort-algorithm for arbitrary long streams of input data. This is in essence also the question for infinite sets. Standard solution was Merge/Sort with two tapes (or four, don't exactly remember) and although for an infinite input the overall time is infinite we are still making progress in this process, this shows that the answer must be positive. But is this really a question for this site? | |
| Sep 29, 2013 at 23:27 | comment | added | Gerry Myerson | I note that the question has been undeleted. | |
| Sep 29, 2013 at 21:49 | comment | added | François G. Dorais Mod | @stefankohl: yes. | |
| Sep 29, 2013 at 21:32 | comment | added | Stefan Kohl Mod | @FrançoisG.Dorais: The user in question has number 40619, and has therefore joined just two days ago -- so how can he already have "a background of misbehavior"? -- Maybe with different accounts? | |
| Sep 29, 2013 at 21:07 | comment | added | Noah Schweber | Oh, okay, that's certainly something I didn't know. (Unfortunately, I don't think I have enough reputation to undelete the question.) If you post your comment as an answer, I'll accept it. | |
| Sep 29, 2013 at 21:05 | comment | added | François G. Dorais Mod | The user was deleted in a manner consistent with how we handle users with a background of misbehavior. It's harmless to undelete the question if you want. | |
| Sep 29, 2013 at 21:05 | history | edited | Noah Schweber | CC BY-SA 3.0 |
added 389 characters in body
|
| Sep 29, 2013 at 20:58 | history | asked | Noah Schweber | CC BY-SA 3.0 |