5 ms·
Oh that makes for a funny part of the ending too then. While going about your work, you suddenly disappear along with your universe and everything in it. Someo
by RyanZAG 11y ago
Oh that makes for a funny part of the ending too then.
While going about your work, you suddenly disappear along with your universe and everything in it. Someone somewhere in the world drank a cup of coffee, which means that he now has an empty cup instead of a full cup. A new universe had to be created with the full cup replaced, and unfortunately your universe had to be thrown away. You continue life as a clone in a new universe with an empty coffee cup somewhere in Nebraska.
Why did this happen? Someone picked a copy-on-write map implementation because it had a slightly faster O(logN) delete behavior and unfortunately the re-use function of the map wasn't implemented yet because the author has gone on to do a series on the use of monads in baking the ultimate croissant.
- TeMPOraL 11y agoHence, Many World Interpretation of quantum mechanics.
- koenigdavidmj 11y agoSorting in O(n) time: 1. Apply a quantum permutation to your list. 2. Check if it's sorted. 3. If not, destroy the universe.
- arethuza 11y agoThat made me think of Greg Egan's Quarantine: https://en.wikipedia.org/wiki/Quarantine_%28Greg_Egan_novel%29 https://en.wikipedia.org/wiki/Quarantine_%28Greg_Egan_novel%...
- moron4hire 11y agoBest-case runtime = 1. Worst-case = infinity.
- AndrewOMartin 11y agoI think the joke is that in all cases but the best-case, you won't be around to observe it, this becomes practical once you can create a universe for every permutation and destroy all but the universe which notifies you that it's the best-case. In all good text books this is left as an exercise for the reader.
- AnimalMuppet 11y agoIn a really good text book, this is left as an exercise that the reader won't do.
- danieldk 11y agoNo, checking whether a list is sorted is O(n) ;). Bogosort is O(n) in the best case and O(inf) in the worst case).
- lisivka 11y agoOptimize out the check, so it will be O(1) in some cases. ;)
- evanpw 11y agoRelated (amazing) paper by Scott Aaronson: "NP-complete Problems and Physical Reality" (http://arxiv.org/abs/quant-ph/0502072 http://arxiv.org/abs/quant-ph/0502072). He proposes "anthropic computing" as a way of solving NP-complete problems in polynomial time: guess an answer, then kill yourself if the answer is wrong.
- dtech 11y agoIt would be very eerie if suddenly all the guesses started being right.
- kragen 11y agoI am worried that someone will actually try this sometime and it will turn out not to work, either because MWI is wrong or because the destruction of the universe was incomplete — for example, collapsing the false vacuum would merely change the state of the things in the universe, not destroy the universe per se. Fortunately, we don't have any currently promising avenues for nucleating a true vacuum or anything like that, so this algorithm is purely theoretical. For now.
- frozenport 11y agoThe convergence of this method depends on the underlying distribution for your random process. It could be O(never).
- jerf 11y agoAs Scott Aaronson points out, the easy solution to this is that you add a slight quantum chance that the algorithm will yield "Reject". As long as that chance is non-zero, but greatly smaller than the probability of any particular successful permutation, you will survive in the universe that says "Reject".
- andrepd 11y agoWhat is a quantum permutation?
- theseoafs 11y agoThis sounds like a joke but this is exactly the proof that sorting is in NP.
- Someone 11y ago"Someone somewhere in the world drank a cup of coffee, which means that he now has an empty cup instead of a full cup" That cannot happen in an immutable world. To fill an empty cup, you cons a cup and its contents. To get an empty cup again, you take the car of the cons. The full cup will only get garbage collected if you do not reference it anymore.
- catnaroek 11y ago> To fill an empty cup, you cons a cup and its contents. That simply has the wrong type in mathematically civilized languages like Standard ML or Haskell. > The full cup will only get garbage collected if you do not reference it anymore. This is orthogonal to functional programming. You can avoid the need for a garbage collector with substructural types.
- ninjakeyboard 11y agoA new chair isn't created - the legs, seat, and back of the old chair are re-used with new screws. If you want to replace a leg, you still need to disassemble the chair and reassemble it with new screws.