4 ms·
So let’s say I’ve got step 2. figured out with vacuum decay or similar, how do I check if the list is sorted in O(1) to determine if I destroy the universe or n
by karl-j 6y ago
So let’s say I’ve got step 2. figured out with vacuum decay or similar, how do I check if the list is sorted in O(1) to determine if I destroy the universe or not?
And given that the list being sorted is a one in n! chance, often enormously less likely than than hardware malfunction, wouldn’t the algorithm mostly produce malfunctions rather than sorted lists?
(Genuinely curious if I’ve got the right understanding of the CS and potential physics.)
- WJW 6y agoChecking if a list is sorted is O(N) if you do it in a single thread since you'd have to check all the elements. If you can do it with a prefix sum or something, it should be possible to do it in O(log N) over many cores. Btw, the quantum bogosort also assumes that destroying the universe is O(1), which seems unlikely. Clearly, when sorting a bigger list there is more information in the universe (ie the list). Since information and energy seem to have some equivalence in quantum dynamics, is does not seem unreasonable that destroying a universe with more information in it would take longer and so destroying the universe cannot be O(1).
- michaelmior 6y ago> Clearly, when sorting a bigger list there is more information in the universe (ie the list). I don't think this is necessarily true. You could argue that the list is simply a bigger fraction of the information in the universe.
- bmm6o 6y agoDoes it matter how long destroying the universe takes, since that's in the unsorted branch? The universe with the sorted list continues immediately, the cleanup is handled elsewhere.